Odwrotny wzór bitowy w C

Question

Konwertuję numer na binarny i muszę użyć numeru putchar, aby wyprowadzić każdy numer.

Problem polega na tym, że otrzymuję zlecenie odwrotnie.

Czy jest jeszcze jakiś sposób odwrócenia wzoru bitowego liczb, zanim zrobię to samemu?

Tak jak w int n ma określony wzór bitowy - jak odwrócić ten wzór bitowy?

Answer 1

Pop bitów off dane wejściowe i wciśnij je na swoje wyjście. Mnożenie i dzielenie przez 2 są operacjami push i pop. W pseudo-kod:

reverse_bits(x) { 
    total = 0 
    repeat n times { 
     total = total * 2 
     total += x % 2 // modulo operation 
     x = x/2 
    } 
    return total 
} 

Zobacz modulo operation na Wikipedii, jeśli nie widzieli tego operatora.

Kolejne punkty:

• Co by się stało, gdybyś zmieniła 2 do 4? Lub do 10?
• Jak to wpływa na wartość n? Co to jest n?
• Jak używać operatorów bitowych (<<, >>, &) zamiast dzielenia i modulo? Czy to przyspieszy?
• Czy możemy użyć innego algorytmu, aby przyspieszyć działanie? Czy tablice informacyjne mogą pomóc?

Answer 2

Pozwól, że zgadnę: masz pętlę, która wypisze 0 bit (n & 1), a następnie przesuwa cyfrę w prawo. Zamiast tego zapisz pętlę, która wypisze 31. bit (n & 0x80000000) i przesunie numer w lewo. Zanim wykonasz tę pętlę, wykonaj kolejną pętlę, która przesuwa liczbę w lewo, aż 31 bit będzie wynosił 1; chyba że to zrobisz, dostaniesz wiodące zera.

Cofanie również jest możliwe. Coś takiego:

unsigned int n = 12345; //Source 
unsigned int m = 0; //Destination 
int i; 
for(i=0;i<32;i++) 
{ 
    m |= n&1; 
    m <<= 1; 
    n >>= 1; 
} 

Answer 3

Jest wiele sposobów na zrobienie tego, niektóre bardzo szybko. Musiałem to sprawdzić.

bitów tylnej w bajcie

b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16; 

odwracać n-bitową równolegle 5 * lg (N) operacjami:

unsigned int v; // 32-bit word to reverse bit order 

// swap odd and even bits 
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1); 
// swap consecutive pairs 
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2); 
// swap nibbles ... 
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4); 
// swap bytes 
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8); 
// swap 2-byte long pairs 
v = (v >> 16   ) | (v    << 16); 

bity reverse słowo po tabela wyszukiwania

static const unsigned char BitReverseTable256[256] = 
{ 
# define R2(n)  n,  n + 2*64,  n + 1*64,  n + 3*64 
# define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16) 
# define R6(n) R4(n), R4(n + 2*4), R4(n + 1*4), R4(n + 3*4) 
    R6(0), R6(2), R6(1), R6(3) 
}; 

unsigned int v; // reverse 32-bit value, 8 bits at time 
unsigned int c; // c will get v reversed 

// Option 1: 
c = (BitReverseTable256[v & 0xff] << 24) | 
    (BitReverseTable256[(v >> 8) & 0xff] << 16) | 
    (BitReverseTable256[(v >> 16) & 0xff] << 8) | 
    (BitReverseTable256[(v >> 24) & 0xff]); 

// Option 2: 
unsigned char * p = (unsigned char *) &v; 
unsigned char * q = (unsigned char *) &c; 
q[3] = BitReverseTable256[p[0]]; 
q[2] = BitReverseTable256[p[1]]; 
q[1] = BitReverseTable256[p[2]]; 
q[0] = BitReverseTable256[p[3]]; 

Aby uzyskać więcej informacji i referencje, patrz: http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel.

Answer 4

Zgaduję, że masz liczbę całkowitą i próbujesz przekonwertować ją na plik binarny?

"Odpowiedź" to ABCDEFG, ale "odpowiedź" to GFEDCBA?

Jeśli tak, to sprawdziłbym dokładnie endiana maszyny, na której ją wykonujesz, i maszyny, z której pochodzi "odpowiedź".

Answer 5

Oto funkcje, których używałem do odwracania bitów w bajtach i bajtach w kwadracie.

inline unsigned char reverse(unsigned char b) { 
    return (b&1 << 7) 
     | (b&2 << 5) 
     | (b&4 << 3) 
     | (b&8 << 1) 
     | (b&0x10 >> 1) 
     | (b&0x20 >> 3) 
     | (b&0x40 >> 5) 
     | (b&0x80 >> 7); 
} 

inline unsigned long wreverse(unsigned long w) { 
    return ((w  &0xFF) << 24) 
     | (((w>>8) &0xFF) << 16) 
     | (((w>>16)&0xFF) << 8) 
     | (((w>>24)&0xFF)); 
} 

Answer 6

wiem: to nie jest dokładnie to, C, ale myślę, że to interesująca odpowiedź:

int reverse(int i) { 
    int output; 
    __asm__(
    "nextbit:" 
     "rcll $1, %%eax;" 
     "rcrl $1, %%ebx;" 
     "loop nextbit;" 
     : "=b" (output) 
     : "a" (i), "c" (sizeof(i)*8)); 
    return output; 
} 

RCL opcode stawia przesunął się nieco w flagi carry, a następnie RCR odzyskuje ten kawałek do innego rejestru w odwrotnej kolejności.