Nombre de bit non défini à gauche de la plupart des bits d'ensemble significatif?

Essayez

int countBits(int value)
{
    int result = sizeof(value) * CHAR_BITS;  // should be 64

    while(value != 0)
    {
        --result;
        value = value >> 1; // Remove bottom bits until all 1 are gone.
    }
    return result;
}

en droite C (long longs sont 64 bits sur ma configuration), pris à partir de mises en œuvre similaires de Java: (Mis à jour après un peu plus de lecture sur le poids de Hamming)

Un peu plus d'explication: la partie supérieure vient de définir un peu à le droit du plus important 1, puis la nier ensuite. (c'est-à-dire que tous les 0 à la gauche de la "gauche" du plus important 1 sont maintenant 1 et tout le reste est 0). P>

alors j'ai utilisé un Hamming Poids Mise en œuvre Pour compter les bits. P>

unsigned long long i = 0x0000000000000000LLU;

i |= i >> 1;
i |= i >> 2;
i |= i >> 4;
i |= i >> 8;
i |= i >> 16;
i |= i >> 32;
// Highest bit in input and all lower bits are now set. Invert to set the bits to count.
i=~i;

i -= (i >> 1) & 0x5555555555555555LLU; // each 2 bits now contains a count
i = (i & 0x3333333333333333LLU) + ((i >> 2) & 0x3333333333333333LLU); // each 4 bits now contains a count
i = (i + (i >> 4)) & 0x0f0f0f0f0f0f0f0fLLU; // each 8 bits now contains a count 
i *= 0x0101010101010101LLU; // add each byte to all the bytes above it
i >>= 56; // the number of bits

printf("Leading 0's = %lld\n", i);

Je suis d'accord avec l'idée de recherche binaire. Cependant, deux points sont importants ici:

1. La gamme de réponses valides à votre question est de 0 à 64 inclusive . En d'autres termes - il peut y avoir 65 des réponses différentes à la question. Je pense que tous ceux qui ont affiché la solution "Recherche binaire" ont manqué ce point, par conséquent, ils auront une réponse erronée pour zéro ou un numéro avec le MSB Bit On.
2. Si la vitesse est critique - vous pouvez éviter la boucle. Il y a un moyen élégant d'atteindre cet utilisation de modèles.

   Le modèle de modèle suivant trouve le MSB correctement de toute variable de type non signé. xxx

Vous allez ici, assez trivial pour mettre à jour comme vous avez besoin pour les autres tailles ...

int bits_left(unsigned long long value)
{
  static unsigned long long mask = 0x8000000000000000;
  int c = 64;
  // doh
  if (value == 0)
    return c;

  // check byte by byte to see what has been set
  if (value & 0xFF00000000000000)
    c = 0;
  else if (value & 0x00FF000000000000)
    c = 8;
  else if (value & 0x0000FF0000000000)
    c = 16;
  else if (value & 0x000000FF00000000)
    c = 24;
  else if (value & 0x00000000FF000000)
    c = 32;
  else if (value & 0x0000000000FF0000)
    c = 40;
  else if (value & 0x000000000000FF00)
    c = 48;
  else if (value & 0x00000000000000FF)
    c = 56;

  // skip
  value <<= c;

  while(!(value & mask))
  {
    value <<= 1;
    c++;
  }

  return c;
}

Basé sur: http://www.hackersdelight.org/hdcode/nlz.c.ca .txt xxx pré>

Si vous souhaitez une version qui vous permet de conserver votre déjeuner, vous allez ici: p>

int clz(uint64_t v) {
    int n=64,c=64;
    while (n) {
        n>>=1;
        if (v>>n) c-=n,v>>=n;
    }
    return c-v;
}

// clear all bits except the lowest set bit
x &= -x;     

// if x==0, add 0, otherwise add x - 1. 
// This sets all bits below the one set above to 1.
x+= (-(x==0))&(x - 1);

return 64 - count_bits_set(x);
Where count_bits_set is the fastest version of counting bits you can find. See https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel for various bit counting techniques.