Nombre de bits requis pour représenter un nombre x

Question

J'essaie actuellement d'écrire un algorithme qui détermine combien de bits sont nécessaires pour représenter un nombre x. Ma mise en œuvre sera en c. Il y a quelques captures cependant, je suis limité à peu près les opérateurs au niveau du bit {~, &, ^, |, +, < <, >>}. De plus, je ne peux utiliser aucun type de flux de contrôle (si, while, for). Mon approche originale était d'examiner le nombre en binaire de gauche à droite, et de chercher où il y a une occurrence du premier '1'. Je ne sais pas comment aborder cela compte tenu des restrictions que j'ai. Le numéro 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 une façon beaucoup plus facile/propre de faire cela et que je l'ai manqué? Ou si quelqu'un peut donner quelques conseils?

En fait, je tentais de mettre en œuvre ce sans la boucle while:

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

Answer 1

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

Indique comment le faire sans flux 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++; 

Answer 2

Eh bien, je pense qu'il a besoin d'un compteur de premier bit plutôt que d'un dernier compteur. Étant donné que cet algorithme implique un entier 32 bits, la réparation est nécessaire pour 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; 

Answer 3

J'ai une solution. C'est pas rapide. Il calcule le nombre de bits nécessaires, c'est-à-dire 32 pour 0xFFFFFFFF et 0 pour 0x00000000. Notez que votre code C calcule réellement le bit le plus significatif ou zéro.

Ici, il est:

#define ISSET(x,i) ((x & (1 << i)) >> i) 
#define FILL(x) ((x << 5) | (x << 4) | (x << 3) | (x << 2) | (x << 1) | 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)))))))))))))))))))))))))))))))); 
} 

Note: FILL devrait être prolongée bien que dans ce cas 6 bits suffisent pour représenter la valeur de rendement le plus élevé (32).

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

Answer 4

La réponse acceptée est réellement incorrecte: par ex. il sort 5 pour 32..63 (au lieu de 6), 4 pour 16..31 (au lieu de 5). C'est comme prendre le logarithme de base 2 et arrondir vers le bas.

La bonne solution 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 ++.

Answer 5

S'il vous plaît essayer:

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