Comment trouver le nombre de zéro dans un nombre à l’aide de C

Par exemple, si j’ai le numéro 64, sa représentation binary serait 0000 0000 0000 0000 0000 0000 0000 0100 0000 donc le nombre de zéros de 25 est 25.

Dites-moi s’il vous plaît la bonne façon de le faire. Même si votre complexité est> O (1), merci de poster votre réponse. merci

Je viens de trouver ce problème en haut des résultats de recherche et ce code:

 int pop(unsigned x) { unsigned n; n = (x >> 1) & 033333333333; x = x - n; n = (n >> 1) & 033333333333; x = x - n; x = (x + (x >> 3)) & 030707070707; return x % 63; } int nlz(unsigned x) { x = x | (x >> 1); x = x | (x >> 2); x = x | (x >> 4); x = x | (x >> 8); x = x | (x >>16); return pop(~x); } 

où pop compte 1 bits, est plusieurs fois plus rapide que la première réponse (votée).

Je n’ai pas remarqué, la question portait sur les nombres 64 bits, alors voici:

 int nlz(unsigned long x) { unsigned long y; long n, c; n = 64; c = 32; do { y = x >> c; if (y != 0) { n = n - c; x = y; } c = c >> 1; } while (c != 0); return n - x; } 

est un algorithme 64 bits, encore plusieurs fois plus rapide que celui mentionné ci-dessus.

Le bon changement est ton ami.

  int input = 64; int sample = ( input < 0 ) ? 0 : input; int leadingZeros = ( input < 0 ) ? 0 : 32; while(sample) { sample >>= 1; --leadingZeros; } printf("Input = %d, leading zeroes = %d\n",input, leadingZeros); 

Voir ici pour la version 32 bits et autres super bidouilles.

 // this is like doing a sign-extension // if original value was 0x00.01yyy..y // then afterwards will be 0x00.01111111 x |= (x >> 1); x |= (x >> 2); x |= (x >> 4); x |= (x >> 8); x |= (x >> 16); x |= (x >> 32); 

et après cela, il vous suffit de renvoyer 64 – numOnes (x). Un moyen simple de le faire est numOnes32 (x) + numOnes32 (x >> 32), où numOnes32 est défini comme suit:

 int numOnes32(unsigned int x) { x -= ((x >> 1) & 0x55555555); x = (((x >> 2) & 0x33333333) + (x & 0x33333333)); x = (((x >> 4) + x) & 0x0f0f0f0f); x += (x >> 8); x += (x >> 16); return(x & 0x0000003f); } 

Je n’ai pas essayé ce code, mais cela devrait faire numOnes64 directement (en moins de temps):

 int numOnes64(unsigned long int x) { x = ((x >> 1) & 0x5555555555555555L) + (x & 0x5555555555555555L); x = ((x >> 2) & 0x3333333333333333L) + (x & 0x3333333333333333L); // collapse: unsigned int v = (unsigned int) ((x >>> 32) + x); v = ((v >> 4) + v) & 0x0f0f0f0f) + (v & 0x0f0f0f0f); v = ((v >> 8) & 0x00ff00ff) + (v & 0x00ff00ff); return ((v >> 16) & 0x0000ffff) + (v & 0x0000ffff); } 

J’irais avec:

 unsigned long clz(unsigned long n) { unsigned long result = 0; unsigned long mask = 0; mask = ~mask; auto size = sizeof(n) * 8; auto shift = size / 2; mask >>= shift; while (shift >= 1) { if (n <= mask) { result += shift; n <<= shift; } shift /= 2; mask <<= shift; } return result; } 

Parce que le logarithme en base 2 représente approximativement le nombre de bits requirejs pour représenter un nombre, il peut être utile dans la réponse:

 irb(main):012:0> 31 - (Math::log(64) / Math::log(2)).floor() => 25 irb(main):013:0> 31 - (Math::log(65) / Math::log(2)).floor() => 25 irb(main):014:0> 31 - (Math::log(127) / Math::log(2)).floor() => 25 irb(main):015:0> 31 - (Math::log(128) / Math::log(2)).floor() => 24 

Bien sûr, l’un des inconvénients de l’utilisation de log(3) est qu’il s’agit d’une routine à virgule flottante; il existe probablement des astuces extrêmement astucieuses pour trouver le nombre de bits zéros non significatifs dans les nombres entiers, mais je ne peux en penser à personne par cœur …

Utiliser des points flottants n’est pas la bonne réponse ….

Voici un algo que j’utilise pour compter le TRAILING 0 … change le pour Leading … Cet algo est en O (1) (s’exécutera toujours en même temps, ou même en même temps, sur certains CPU).

 int clz(unsigned int i) { int zeros; if ((i&0xffff)==0) zeros= 16, i>>= 16; else zeroes= 0; if ((i&0xff)==0) zeros+= 8, i>>= 8; if ((i&0xf)==0) zeros+= 4, i>>= 4; if ((i&0x3)==0) zeros+= 2, i>>= 2; if ((i&0x1)==0) zeros+= 1, i>>= 1; return zeroes+i; }