Inversion de bit d'un entier, ignorant la taille et l'endianité de l'entier
https://stackoverflow.com/questions/63776
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Étant donné un typedef entier:
typedef unsigned int TYPE;
ou
typedef unsigned long TYPE;
J'ai le code suivant pour inverser les bits d'un entier:
TYPE max_bit= (TYPE)-1;
void reverse_int_setup()
{
TYPE bits= (TYPE)max_bit;
while (bits <<= 1)
max_bit= bits;
}
TYPE reverse_int(TYPE arg)
{
TYPE bit_setter= 1, bit_tester= max_bit, result= 0;
for (result= 0; bit_tester; bit_tester>>= 1, bit_setter<<= 1)
if (arg & bit_tester)
result|= bit_setter;
return result;
}
Il suffit d’exécuter reverse_int_setup (), qui stocke un entier dont le bit le plus élevé est activé, puis tout appel à reverse_int ( arg ) renvoie arg avec son bits inversés (à utiliser comme clé d'un arbre binaire, extrait d'un compteur croissant, mais c'est plus ou moins inutile).
Existe-t-il un moyen, indépendant de la plate-forme, d’avoir au moment de la compilation la valeur correcte pour max_int après l’appel de reverse_int_setup (); Sinon, y a-t-il un algorithme que vous considérez comme meilleur / plus léger que celui que j’ai pour reverse_int ()?
Merci.
La solution
#include<stdio.h>
#include<limits.h>
#define TYPE_BITS sizeof(TYPE)*CHAR_BIT
typedef unsigned long TYPE;
TYPE reverser(TYPE n)
{
TYPE nrev = 0, i, bit1, bit2;
int count;
for(i = 0; i < TYPE_BITS; i += 2)
{
/*In each iteration, we swap one bit on the 'right half'
of the number with another on the left half*/
count = TYPE_BITS - i - 1; /*this is used to find how many positions
to the left (and right) we gotta move
the bits in this iteration*/
bit1 = n & (1<<(i/2)); /*Extract 'right half' bit*/
bit1 <<= count; /*Shift it to where it belongs*/
bit2 = n & 1<<((i/2) + count); /*Find the 'left half' bit*/
bit2 >>= count; /*Place that bit in bit1's original position*/
nrev |= bit1; /*Now add the bits to the reversal result*/
nrev |= bit2;
}
return nrev;
}
int main()
{
TYPE n = 6;
printf("%lu", reverser(n));
return 0;
}
Cette fois, j'ai utilisé l'idée du "nombre de bits" de TK, mais je l'ai rendue un peu plus portable en ne supposant pas qu'un octet contienne 8 bits et en utilisant plutôt la macro CHAR_BIT. Le code est plus efficace maintenant (avec la boucle for interne supprimée). J'espère que le code est aussi légèrement moins crypté cette fois-ci. :)
La nécessité d'utiliser count est que le nombre de positions pour lesquelles nous devons décaler un bit varie à chaque itération - nous devons déplacer le bit le plus à droite de 31 positions (en supposant un nombre de 32 bits), le second bit le plus à droite de 29 positions et ainsi de suite. Par conséquent, le nombre doit diminuer à chaque itération à mesure que i augmente.
J'espère que ces informations vous aideront à comprendre le code ...
Autres conseils
Le programme suivant sert à illustrer un algorithme plus simple d’inversion de bits, qui peut facilement être étendu pour gérer des nombres 64 bits.
#include <stdio.h>
#include <stdint.h>
int main(int argc, char**argv)
{
int32_t x;
if ( argc != 2 )
{
printf("Usage: %s hexadecimal\n", argv[0]);
return 1;
}
sscanf(argv[1],"%x", &x);
/* swap every neigbouring bit */
x = (x&0xAAAAAAAA)>>1 | (x&0x55555555)<<1;
/* swap every 2 neighbouring bits */
x = (x&0xCCCCCCCC)>>2 | (x&0x33333333)<<2;
/* swap every 4 neighbouring bits */
x = (x&0xF0F0F0F0)>>4 | (x&0x0F0F0F0F)<<4;
/* swap every 8 neighbouring bits */
x = (x&0xFF00FF00)>>8 | (x&0x00FF00FF)<<8;
/* and so forth, for say, 32 bit int */
x = (x&0xFFFF0000)>>16 | (x&0x0000FFFF)<<16;
printf("0x%x\n",x);
return 0;
}
Ce code ne devrait pas contenir d’erreurs. Il a été testé avec 0x12345678 pour produire 0x1e6a2c48, ce qui est la réponse correcte.
typedef unsigned long TYPE;
TYPE reverser(TYPE n)
{
TYPE k = 1, nrev = 0, i, nrevbit1, nrevbit2;
int count;
for(i = 0; !i || (1 << i && (1 << i) != 1); i+=2)
{
/*In each iteration, we swap one bit
on the 'right half' of the number with another
on the left half*/
k = 1<<i; /*this is used to find how many positions
to the left (or right, for the other bit)
we gotta move the bits in this iteration*/
count = 0;
while(k << 1 && k << 1 != 1)
{
k <<= 1;
count++;
}
nrevbit1 = n & (1<<(i/2));
nrevbit1 <<= count;
nrevbit2 = n & 1<<((i/2) + count);
nrevbit2 >>= count;
nrev |= nrevbit1;
nrev |= nrevbit2;
}
return nrev;
}
Cela fonctionne bien dans gcc sous Windows, mais je ne suis pas sûr que ce soit complètement indépendant de la plate-forme. Quelques sujets de préoccupation sont:
-
la condition dans la boucle for - il suppose que lorsque vous quittez le décalage 1 au-delà du bit le plus à gauche, vous obtenez soit un 0 avec le 1 "tombant" (ce à quoi je m'attendais et quel bon vieux Turbo C donne iirc), ou le 1 tourne autour et vous obtenez un 1 (ce qui semble être le comportement de gcc).
-
la condition dans la boucle while interne: voir ci-dessus. Mais il se passe une chose étrange: dans ce cas, gcc semble laisser le 1 tomber et ne pas tourner en rond!
Le code peut s'avérer cryptique: si cela vous intéresse et si vous avez besoin d'une explication, n'hésitez pas à demander, je le mettrai quelque part.
@ ??O?????
En réponse aux commentaires de ??O, je présente une version modifiée de ce qui précède, qui dépend d’une limite supérieure de largeur de bit.
#include <stdio.h>
#include <stdint.h>
typedef int32_t TYPE;
TYPE reverse(TYPE x, int bits)
{
TYPE m=~0;
switch(bits)
{
case 64:
x = (x&0xFFFFFFFF00000000&m)>>16 | (x&0x00000000FFFFFFFF&m)<<16;
case 32:
x = (x&0xFFFF0000FFFF0000&m)>>16 | (x&0x0000FFFF0000FFFF&m)<<16;
case 16:
x = (x&0xFF00FF00FF00FF00&m)>>8 | (x&0x00FF00FF00FF00FF&m)<<8;
case 8:
x = (x&0xF0F0F0F0F0F0F0F0&m)>>4 | (x&0x0F0F0F0F0F0F0F0F&m)<<4;
x = (x&0xCCCCCCCCCCCCCCCC&m)>>2 | (x&0x3333333333333333&m)<<2;
x = (x&0xAAAAAAAAAAAAAAAA&m)>>1 | (x&0x5555555555555555&m)<<1;
}
return x;
}
int main(int argc, char**argv)
{
TYPE x;
TYPE b = (TYPE)-1;
int bits;
if ( argc != 2 )
{
printf("Usage: %s hexadecimal\n", argv[0]);
return 1;
}
for(bits=1;b;b<<=1,bits++);
--bits;
printf("TYPE has %d bits\n", bits);
sscanf(argv[1],"%x", &x);
printf("0x%x\n",reverse(x, bits));
return 0;
}
Notes:
- gcc avertira sur les constantes 64 bits
- le printfs générera aussi des avertissements
- Si vous avez besoin de plus de 64 bits, le code doit être assez simple pour être étendu
Je m'excuse par avance pour les crimes de codage que j'ai commis ci-dessus - merci mon Dieu!
Il y a une belle collection de "Bit Twiddling Hacks", comprenant une variété d’algorithmes d’inversion de bits simples et pas si simples codés en C à http://graphics.stanford.edu/~seander/bithacks.html .
Personnellement, j’aime bien l’option "Évident". algorigthm ( http://graphics.stanford.edu/~seander/bithacks.html# BitReverseObvious ), parce que c'est évident. Certains des autres peuvent nécessiter moins d’instructions à exécuter. Si j'ai vraiment besoin d'optimiser quelque chose, je peux choisir des versions moins évidentes, mais plus rapides. Sinon, pour des raisons de lisibilité, de maintenabilité et de portabilité, je choisirais Evident.
Voici une variante plus utile. Son avantage réside dans sa capacité à fonctionner dans des situations où la longueur en bits de la valeur à inverser (mot codé) est inconnue mais qu'il est garanti de ne pas dépasser une valeur que nous appellerons maxLength. Un bon exemple de ce cas est la décompression de code de Huffman.
Le code ci-dessous fonctionne avec les mots de code d'une longueur de 1 à 24 bits. Il a été optimisé pour une exécution rapide sur un Pentium D. Notez qu'il accède à la table de recherche jusqu'à 3 fois par utilisation. J'ai expérimenté de nombreuses variantes qui réduisaient ce nombre à 2 au détriment d'un tableau plus volumineux (4096 et 65 536 entrées). Cette version, avec la table de 256 octets, était clairement gagnante, en partie parce qu’il est très avantageux que les données de la table se trouvent dans les caches et peut-être aussi parce que le processeur dispose d’une instruction de recherche / traduction de table à 8 bits.
const unsigned char table[] = {
0x00,0x80,0x40,0xC0,0x20,0xA0,0x60,0xE0,0x10,0x90,0x50,0xD0,0x30,0xB0,0x70,0xF0,
0x08,0x88,0x48,0xC8,0x28,0xA8,0x68,0xE8,0x18,0x98,0x58,0xD8,0x38,0xB8,0x78,0xF8,
0x04,0x84,0x44,0xC4,0x24,0xA4,0x64,0xE4,0x14,0x94,0x54,0xD4,0x34,0xB4,0x74,0xF4,
0x0C,0x8C,0x4C,0xCC,0x2C,0xAC,0x6C,0xEC,0x1C,0x9C,0x5C,0xDC,0x3C,0xBC,0x7C,0xFC,
0x02,0x82,0x42,0xC2,0x22,0xA2,0x62,0xE2,0x12,0x92,0x52,0xD2,0x32,0xB2,0x72,0xF2,
0x0A,0x8A,0x4A,0xCA,0x2A,0xAA,0x6A,0xEA,0x1A,0x9A,0x5A,0xDA,0x3A,0xBA,0x7A,0xFA,
0x06,0x86,0x46,0xC6,0x26,0xA6,0x66,0xE6,0x16,0x96,0x56,0xD6,0x36,0xB6,0x76,0xF6,
0x0E,0x8E,0x4E,0xCE,0x2E,0xAE,0x6E,0xEE,0x1E,0x9E,0x5E,0xDE,0x3E,0xBE,0x7E,0xFE,
0x01,0x81,0x41,0xC1,0x21,0xA1,0x61,0xE1,0x11,0x91,0x51,0xD1,0x31,0xB1,0x71,0xF1,
0x09,0x89,0x49,0xC9,0x29,0xA9,0x69,0xE9,0x19,0x99,0x59,0xD9,0x39,0xB9,0x79,0xF9,
0x05,0x85,0x45,0xC5,0x25,0xA5,0x65,0xE5,0x15,0x95,0x55,0xD5,0x35,0xB5,0x75,0xF5,
0x0D,0x8D,0x4D,0xCD,0x2D,0xAD,0x6D,0xED,0x1D,0x9D,0x5D,0xDD,0x3D,0xBD,0x7D,0xFD,
0x03,0x83,0x43,0xC3,0x23,0xA3,0x63,0xE3,0x13,0x93,0x53,0xD3,0x33,0xB3,0x73,0xF3,
0x0B,0x8B,0x4B,0xCB,0x2B,0xAB,0x6B,0xEB,0x1B,0x9B,0x5B,0xDB,0x3B,0xBB,0x7B,0xFB,
0x07,0x87,0x47,0xC7,0x27,0xA7,0x67,0xE7,0x17,0x97,0x57,0xD7,0x37,0xB7,0x77,0xF7,
0x0F,0x8F,0x4F,0xCF,0x2F,0xAF,0x6F,0xEF,0x1F,0x9F,0x5F,0xDF,0x3F,0xBF,0x7F,0xFF};
const unsigned short masks[17] =
{0,0,0,0,0,0,0,0,0,0X0100,0X0300,0X0700,0X0F00,0X1F00,0X3F00,0X7F00,0XFF00};
unsigned long codeword; // value to be reversed, occupying the low 1-24 bits
unsigned char maxLength; // bit length of longest possible codeword (<= 24)
unsigned char sc; // shift count in bits and index into masks array
if (maxLength <= 8)
{
codeword = table[codeword << (8 - maxLength)];
}
else
{
sc = maxLength - 8;
if (maxLength <= 16)
{
codeword = (table[codeword & 0X00FF] << sc)
| table[codeword >> sc];
}
else if (maxLength & 1) // if maxLength is 17, 19, 21, or 23
{
codeword = (table[codeword & 0X00FF] << sc)
| table[codeword >> sc] |
(table[(codeword & masks[sc]) >> (sc - 8)] << 8);
}
else // if maxlength is 18, 20, 22, or 24
{
codeword = (table[codeword & 0X00FF] << sc)
| table[codeword >> sc]
| (table[(codeword & masks[sc]) >> (sc >> 1)] << (sc >> 1));
}
}
Que diriez-vous de:
long temp = 0;
int counter = 0;
int number_of_bits = sizeof(value) * 8; // get the number of bits that represent value (assuming that it is aligned to a byte boundary)
while(value > 0) // loop until value is empty
{
temp <<= 1; // shift whatever was in temp left to create room for the next bit
temp |= (value & 0x01); // get the lsb from value and set as lsb in temp
value >>= 1; // shift value right by one to look at next lsb
counter++;
}
value = temp;
if (counter < number_of_bits)
{
value <<= counter-number_of_bits;
}
(Je suppose que vous savez combien de bits la valeur contient et qu'elle est stockée dans number_of_bits)
Il est évident que temp doit être le type de données le plus long imaginable et lorsque vous recopiez temp en valeur, tous les bits superflus de temp devraient disparaître comme par magie (je pense!).
Ou bien, la méthode "c" consisterait à dire:
while(value)
votre choix
Nous pouvons stocker les résultats de l'inversion de toutes les séquences possibles d'un octet dans un tableau (256 entrées distinctes), puis utiliser une combinaison de recherches dans cette table et une certaine logique oring pour obtenir l'inverse de l'entier.
Voici une variante et une correction de la solution de TK qui pourraient être plus claires que les solutions de Sundar. Il prend des bits de t et les place dans return_val:
typedef unsigned long TYPE;
#define TYPE_BITS sizeof(TYPE)*8
TYPE reverser(TYPE t)
{
unsigned int i;
TYPE return_val = 0
for(i = 0; i < TYPE_BITS; i++)
{/*foreach bit in TYPE*/
/* shift the value of return_val to the left and add the rightmost bit from t */
return_val = (return_val << 1) + (t & 1);
/* shift off the rightmost bit of t */
t = t >> 1;
}
return(return_val);
}
L’approche générique qui conviendrait aux objets de tout type, quelle que soit leur taille, consiste à inverser le nombre d’octets de l’objet et à inverser l’ordre des bits dans chaque octet. Dans ce cas, l'algorithme de niveau de bits est lié à un nombre concret de bits (un octet), tandis que la "variable" la logique (en ce qui concerne la taille) est élevée au niveau des octets entiers.
Voici ma généralisation de la solution de freespace (au cas où nous aurions un jour des machines 128 bits). Il en résulte un code sans sauts lors de la compilation avec gcc -O3, et est évidemment insensible à la définition de foo_t sur des machines saines. Malheureusement, cela dépend du fait que shift soit une puissance de 2!
#include <limits.h>
#include <stdio.h>
typedef unsigned long foo_t;
foo_t reverse(foo_t x)
{
int shift = sizeof (x) * CHAR_BIT / 2;
foo_t mask = (1 << shift) - 1;
int i;
for (i = 0; shift; i++) {
x = ((x & mask) << shift) | ((x & ~mask) >> shift);
shift >>= 1;
mask ^= (mask << shift);
}
return x;
}
int main() {
printf("reverse = 0x%08lx\n", reverse(0x12345678L));
}
Dans le cas où l’inversion de bit est critique en temps et principalement en conjonction avec FFT, le mieux est de stocker le tableau inversé de bit en entier. Dans tous les cas, la taille de ce tableau sera plus petite que celle des racines d'unité devant être précalculées dans l'algorithme FFT Cooley-Tukey. Un moyen simple de calculer le tableau est le suivant:
int BitReverse[Size]; // Size is power of 2
void Init()
{
BitReverse[0] = 0;
for(int i = 0; i < Size/2; i++)
{
BitReverse[2*i] = BitReverse[i]/2;
BitReverse[2*i+1] = (BitReverse[i] + Size)/2;
}
} // end it's all
