Nombre de bits nécessaires pour représenter un nombre x

J’essaie actuellement d’écrire un algorithme qui détermine le nombre de bits nécessaires pour représenter un nombre x. Ma mise en œuvre sera en c. Il y a quelques sockets cependant, je suis limité aux opérateurs bitwise {~, &, ^, |, +, <>}. De plus, je ne peux utiliser aucun type de stream de contrôle (si, tant que, pour). Mon approche initiale consistait à examiner le nombre en binary de gauche à droite et à rechercher les occurrences du premier «1». Je ne suis pas sûr de savoir comment aborder cela étant donné les ressortingctions que j’ai. Le nombre avec lequel je travaille peut être considéré comme un entier non signé. Donc, 00110 ne nécessiterait que 3 bits.

Je me demande s’il existe un moyen beaucoup plus simple et plus propre de le faire et si je le manque. Ou si quelqu’un peut donner quelques conseils?

En gros, j’essayais d’implémenter ceci sans la boucle while:

int result = 0; while (x >>= 1) { result += 1; } return result; 

http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLog

Montre comment le faire sans stream de contrôle.

 unsigned int v; // 32-bit value to find the log2 of register unsigned int r; // result of log2(v) will go here register unsigned int shift; r = (v > 0xFFFF) << 4; v >>= r; shift = (v > 0xFF ) << 3; v >>= shift; r |= shift; shift = (v > 0xF ) << 2; v >>= shift; r |= shift; shift = (v > 0x3 ) << 1; v >>= shift; r |= shift; r |= (v >> 1); r++; 

La réponse acceptée est en fait fausse: par exemple, elle affiche 5 pour 32..63 (au lieu de 6), 4 pour 16..31 (au lieu de 5). C’est comme si on prenait le logarithme en base 2 et qu’on arrondissait à la baisse.

La solution correcte est la suivante:

 unsigned int v; // 32-bit value to find the log2 of register unsigned int r; // result of log2(v) will go here register unsigned int shift; r = (v > 0xFFFF) << 4; v >>= r; shift = (v > 0xFF ) << 3; v >>= shift; r |= shift; shift = (v > 0xF ) << 2; v >>= shift; r |= shift; shift = (v > 0x3 ) << 1; v >>= shift; r |= shift; r |= (v >> 1); r++; 

Notez le r ++ .

S’il vous plaît essayez:

 // http://www.cs.northwestern.edu/~wms128/bits.c int check_bits_fit_in_2s_complement(signed int x, unsigned int n) { int mask = x >> 31; return !(((~x & mask) + (x & ~mask))>> (n + ~0)); } 

J’ai une solution Ce n’est pas rapide Il calcule le nombre de bits nécessaires, soit 32 pour 0xFFFFFFFF et 0 pour 0x00000000. Notez que votre code C calcule vraiment le bit le plus significatif ou zéro.

C’est ici:

 #define ISSET(x,i) (((x) >> (i)) & 1) #define FILL(x) (-(x)) #define IF(x,y,z) ((FILL(x) & y) | (~FILL(x) & z)) #define R(x,i,y,z) (IF(ISSET(x,i),y,z)) int log2 (uint32_t x) { return R(x,31,32, R(x,30,31, R(x,29,30, R(x,28,29, R(x,27,28, R(x,26,27, R(x,25,26, R(x,24,25, R(x,23,24, R(x,22,23, R(x,21,22, R(x,20,21, R(x,19,20, R(x,18,19, R(x,17,18, R(x,16,17, R(x,15,16, R(x,14,15, R(x,13,14, R(x,12,13, R(x,11,12, R(x,10,11, R(x, 9,10, R(x, 8, 9, R(x, 7, 8, R(x, 6, 7, R(x, 5, 6, R(x, 4, 5, R(x, 3, 4, R(x, 2, 3, R(x, 1, 2, R(x, 0, 1, 0)))))))))))))))))))))))))))))))); } 

Remarque: le principe général peut être utilisé pour d’autres fonctions.

Eh bien, je pense qu’il a besoin d’un compteur de premier bit plutôt que d’un compteur de dernier bit. Puisque cet algorithme implique un entier de 32 bits, il y a une correction nécessaire par le résultat.

 unsigned int v; // 32-bit value to find the log2 of register unsigned int r; // result of log2(v) will go here register unsigned int shift; r = (v > 0xFFFF) << 4; v >>= r; shift = (v > 0xFF ) << 3; v >>= shift; r |= shift; shift = (v > 0xF ) << 2; v >>= shift; r |= shift; shift = (v > 0x3 ) << 1; v >>= shift; r |= shift; r |= (v >> 1); return 32-r;