Indice du bit de poids le plus bas

Question

Je veux trouver le moyen le plus rapide d'obtenir l'indice du bit de poids le plus bas d'une longueur longue. à savoir:

00101001001000 -> 3 

Les solutions impliquant un bouclage et un décalage sont trop lentes. à savoir:

int i; 
if(bits == 0ULL) { 
    i = 64; 
} else { 
    for(i = 0;!(bits & 1ULL);i++) 
    bits >>= 1; 
} 

EDIT: Informations sur l'utilisation

La fonction qui utilise ffsll ne peut pas vraiment réduire son utilisation, mais ici il est (simplifié bien sûr). Il parcourt simplement les indices et fait quelque chose avec eux. Cette fonction est peut-être la plus utilisée dans toute mon application malgré une mise en cache de sa valeur. C'est un générateur de mouvement légal dans mon moteur de recherche alpha-beta.

while(bits){ 
    index = ffsll(bits); 
    doSomething(index); 
    index &= index-1; 
} 

Answer 1

Intel a des instructions spécialisées pour trouver le bit de consigne le plus bas ou le plus élevé. BSF semble être ce dont vous avez besoin. aussi loin que le faire en C simple, peut-être le bit twiddling hacks page a ce dont vous avez besoin. À tout le moins, vous pouvez utiliser une table de quartets ou d'octets pour accélérer les choses. Quelque chose comme ça (démontré pour int, mais facilement modifiable à longlong comme nécessaire).

/* 
0000 - 0 
0001 - 1 
0010 - 2 
0011 - 1 
0100 - 3 
0101 - 1 
0110 - 2 
0111 - 1 
1000 - 4 
1001 - 1 
1010 - 2 
1011 - 1 
1100 - 3 
1101 - 1 
1110 - 2 
1111 - 1 
*/ 

int ffs(int i) { 
    int ret = 0; 
    int j = 0; 
    static const int _ffs_tab[] = 
     { 0, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 }; 

    while((i != 0) && (ret == 0)) { 
     ret = _ffs_tab[i & 0x0f]; 

     if(ret > 0) { 
      break; 
     } 

     i >>= 4; 
     j += 4; 

     /* technically the sign bit could stay, so we mask it out to be sure */ 
     i &= INT_MAX; 
    } 

    if(ret != 0) { 
     ret += j; 
    } 

    return ret; 
} 

Answer 2

Le plus rapide que j'ai trouvé est ffsll(long long) dans string.h.

Answer 3

Pourquoi ne pas implémenter un type de recherche binaire?

Examinez les bits faibles résultant d'un bit sage et d'une valeur de masque qui sont tous les uns dans la moitié inférieure. Si cette valeur est zéro, vous savez que le plus petit bit est dans la moitié supérieure du nombre. D'autre part, coupez la chose en deux et recommencez.

Answer 4

Que diriez-vous de quelque chose comme ceci? Il réduit considérablement le nombre de boucles.

int shifts = 0; 
if ((bits & 0xFFFFFFFFFFFFULL) == 0) // not in bottom 48 bits 
{ 
    shifts = 48; 
} 
else if ((bits & 0xFFFFFFFFFFULL == 0) // not in bottom 40 bits 
{ 
    shifts = 40; 
} 
else 
// etc 

bits >>= shifts; // do all the shifts at once 

// this will loop at most 8 times 
for(i = 0;!(bits & 1ULL);i++) 
    bits >>= 1; 

index = shifts + i; 

Answer 5

Vous pouvez isoler le bit le plus bas avec x & (~x + 1); cela vous donne la valeur de bit la plus basse, pas l'index (par exemple, si x = 01101000, le résultat est 00001000). La façon la plus rapide que je connaisse pour obtenir de là un indice est probablement une instruction switch:

switch(x & (~x + 1)) 
{ 
    case  0ULL: index = -1; break; 
    case  1ULL: index = 0; break; 
    case  2ULL: index = 1; break; 
    case  4ULL: index = 2; break; 
    ... 
    case 9223372036854775808ULL: index = 63; break; 
} 

laid, mais pas looping impliqué.

Answer 6

J'ai écrit deux fonctions, elles retournent le même résultat que ffsll().

int func1(uint64_t n){ 
    if(n == 0) return 0; 
    n ^= n-1; 
    int i = 0; 
    if(n >= 1ull<<32){ n>>=32; i+=32; } 
    if(n >= 1ull<<16){ n>>=16; i+=16; } 
    if(n >= 1ull<< 8){ n>>= 8; i+= 8; } 
    if(n >= 1ull<< 4){ n>>= 4; i+= 4; } 
    if(n >= 1ull<< 2){ n>>= 2; i+= 2; } 
    if(n >= 1ull<< 1){   i+= 1; } 
    return i+1; 
} 

int func2(uint64_t n){ 
    return n? ((union ieee754_float)((float)(n^(n-1)))).ieee.exponent-126: 0; 
} 

Je ne sais pas qui est le plus rapide: ffsll(), func1() ou func2()?

Answer 7

Vous pouvez réduire de moitié la complexité de votre algorithme en vérifiant d'abord si votre numéro est impair ou pair. S'il est égal, vous avez le bit le plus bas est le premier.

Pour les cas bizarres que vous pouvez mettre en œuvre une telle recherche binaire ...

Answer 8

Cela pourrait fonctionner pour 32 bits. Devrait être assez facile à étendre à 64.

// all bits left of lsb become 1, lsb & right become 0 
y = x^(-x); 

// XOR a shifted copy recovers a single 1 in the lsb's location 
u = y^(y >> 1); 

// .. and isolate the bit in log2 of number of bits 
i0 = (u & 0xAAAAAAAA) ? 1 : 0; 
i1 = (u & 0xCCCCCCCC) ? 2 : 0; 
i2 = (u & 0xF0F0F0F0) ? 4 : 0; 
i3 = (u & 0xFF00FF00) ? 8 : 0; 
i4 = (u & 0xFFFF0000) ? 16 : 0; 
index = i4 | i3 | i2 | i1 | i0; 

Il est évident que, s'il y a un moyen d'avoir le matériel le faire, à savoir, si les instructions CPU spéciales sont disponibles, qui est le chemin à parcourir.

Answer 9

Si vous utilisez Visual Studio, _BitScanForward:

• http://msdn.microsoft.com/en-us/library/wfd9z0bb(VS.80).aspx (_BitScanForward)

Pour gcc, essayez __builtin_ctz ou __builtin_ffs:

• http://developer.apple.com/mac/library/documentation/DeveloperTools/gcc-4.0.1/gcc/Other-Builtins.html (random gcc intrinsics documentation)

Comme toujours le code généré doit être consulté pour s'assurer que les instructions correctes sont générées.

Answer 10

Voici deux implémentations, d'abord par intrinsics/assemblage, le second est par c/C++ (indice commence à partir de 0)

unsigned int bsf_asm(unsigned int b) 
{ 

    // b == 0 is undefined 

#if defined(\__GNUC__) 

    return __builtin_ctz(b); 

#else 

    __asm bsf eax, b; 

#endif 

} 


unsigned int bsf(unsigned int b) 
{ 

    // b == 0 is undefined 

    static const unsigned char btal[] = {0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0}; 

    int i = 0; 
    if(!(b & 0x0000ffff)) 
    { 
     b>>=16; 
     i+=16; 
    } 

    if(!(b & 0x000000ff)) 
    { 
     b>>=8; 
     i+=8; 
    } 

    if(!(b & 0x0000000f)) 
    { 
     b>>=4; 
     i+=4; 
    } 

    return i+btal[b&0x0f]; 

} 

Answer 11

Pour obtenir le droit le plus défini bit l'expression suivante peut être utilisée

Tenez compte des variable X

x (x & ~ - 1) donne un nombre binaire qui ne contient que le bit de jeu avec le reste des zéros

Exemple

x  = 0101 
x-1 = 0100 
~(x-1) = 1011 

x & ~ (x - 1) = 0100 

maintenant passer sans cesse ce nombre binaire à droite jusqu'à ce que le nombre est égal à zéro et compter le nombre de quarts de travail qui donne le numéro de droite bit le plus défini.