Modèle de bits inversé en C

Je convertis un nombre en binary et dois utiliser putchar pour afficher chaque nombre.

Le problème, c’est que l’ordre est inversé.

Y a-t-il un moyen d’inverser un modèle de bits de nombres avant de faire ma propre tentative

Comme dans int n a un modèle de bits spécifique – comment puis-je inverser ce modèle de bits?

Il y a plusieurs façons de le faire, certaines très rapidement. Je devais le chercher.

Inverser des bits dans un octet

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

Inverser une quantité de N bits en parallèle dans des opérations de 5 * lg (N):

 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); 

Inverser les bits dans le mot par la table de recherche

 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]]; 

Veuillez consulter http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel pour plus d'informations et des références.

Retirez des bits de votre entrée et poussez-les sur votre sortie. La multiplication et la division par 2 correspondent aux opérations push et pop. En pseudo-code:

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

Voir le fonctionnement modulo sur Wikipedia si vous n’avez pas vu cet opérateur.

Autres points:

  • Que se passerait-il si vous changiez de 2 à 4? Ou à 10?
  • Comment cela affecte-t-il la valeur de n? Qu’est ce que n?
  • Comment utiliser des opérateurs au niveau des bits ( << , >> , & ) au lieu de divide et modulo? Est-ce que cela le rendrait plus rapide?
  • Pourrions-nous utiliser un algorithme différent pour le rendre plus rapide? Les tables de recherche pourraient-elles aider?

Laissez-moi deviner: vous avez une boucle qui affiche le 0ème bit (n & 1), puis décale le nombre à droite. À la place, écrivez une boucle qui imprime le 31e bit (n & 0x80000000) et décale le nombre à gauche. Avant de faire cette boucle, faites une autre boucle qui décale le nombre à gauche jusqu’à ce que le 31ème bit soit à 1; à moins que vous ne le fassiez, vous aurez des zéros non significatifs.

L’inversion est possible aussi. Quelque chose comme ça:

 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; } 

Je sais: ce n’est pas exactement C, mais je pense que c’est une réponse intéressante:

 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; } 

L’opcode rcl place le bit décalé dans l’indicateur de report, puis rcr récupère ce bit dans un autre registre dans l’ordre inverse.

Je suppose que vous avez un entier et que vous essayez de le convertir en binary?

Et la “réponse” est ABCDEFG, mais votre “réponse” est GFEDCBA?

Si tel est le cas, je revérifierais l’endian de la machine sur laquelle vous le faites et la machine d’où provient la “réponse”.

Voici les fonctions que j’ai utilisées pour inverser des bits dans un octet et inverser des octets dans un quad.

 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) ); }