Position du bit le moins significatif défini

Je recherche un moyen efficace de déterminer la position du bit le moins significatif qui est défini dans un entier, par exemple pour 0x0FF0, ce serait 4.

Une implémentation triviale est la suivante:

unsigned GetLowestBitPos(unsigned value)
{
   assert(value != 0); // handled separately

   unsigned pos = 0;
   while (!(value & 1))
   {
      value >>= 1;
      ++pos;
   }
   return pos;
}

Avez-vous des idées pour en extraire certains cycles?

(Remarque: cette question s'adresse aux personnes qui aiment de telles choses, et non aux personnes qui me disent que l'optimisation xyz est maléfique.)

[modifier] Merci à tous pour les idées! J'ai aussi appris quelques autres choses. Cool!

Bit Twiddling Hacks offre une excellente collection de hacks de twiddling, avec une discussion sur les performances / optimisation en annexe. Ma solution préférée pour votre problème (à partir de ce site) est «multiplier et rechercher»:

unsigned int v;  // find the number of trailing zeros in 32-bit v 
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

Références utiles:

• " Utilisation des séquences de Bruijn pour indexer un 1 dans un mot d'ordinateur " - Explication de la raison pour laquelle le code ci-dessus fonctionne.
• " Représentation du plateau> Bitboards> BitScan " - Analyse détaillée de ce problème, avec un accent particulier sur la programmation d'échecs

Pourquoi ne pas utiliser les ffs intégrés ? (J'ai récupéré une page de manuel de Linux, mais elle est plus largement disponible que cela.)

ffs (3) - Page de manuel Linux

Nom

ffs - trouve le premier bit défini dans un mot

Synopsis

#include <strings.h>
int ffs(int i);
#define _GNU_SOURCE
#include <string.h>
int ffsl(long int i);
int ffsll(long long int i);

La description

La fonction ffs () renvoie la position du premier bit (le moins significatif) défini dans le mot i. Le bit le moins significatif est la position 1 et la position la plus significative, par exemple 32 ou 64. Les fonctions ffsll () et ffsl () font la même chose mais prennent des arguments de taille éventuellement différente.

Valeur de retour

Ces fonctions renvoient la position du premier ensemble de bits, ou 0 si aucun bit n'est défini dans i.

Se conformer à

4.3BSD, POSIX.1-2001.

Remarques

Les systèmes BSD ont un prototype au format <string.h>.

Il existe une instruction d'assemblage x86 ( bsf) qui le fera. :)

Plus optimisé?!

Note latérale:

L'optimisation à ce niveau est intrinsèquement dépendante de l'architecture. Les processeurs actuels sont trop complexes (en termes de prédiction de branchement, d'erreurs de cache, de pipelining) qu'il est si difficile de prédire quel code est exécuté plus rapidement sur quelle architecture. Diminuer les opérations de 32 à 9 ou des choses comme ça peut même diminuer les performances sur certaines architectures. Un code optimisé sur une seule architecture peut entraîner un code plus mauvais dans l'autre. Je pense que vous optimiseriez cela pour un processeur spécifique ou le laisseriez tel quel et laisser le compilateur choisir ce qu'il pense être le meilleur.

La plupart des architectures modernes auront des instructions pour trouver la position du bit de jeu le plus bas, ou du bit de jeu le plus élevé, ou pour compter le nombre de zéros en tête, etc.

Si vous avez une instruction de cette classe, vous pouvez imiter les autres à moindre coût.

Prenez un moment pour le parcourir sur papier et réalisez que x & (x-1)cela effacera le bit le plus bas de x et ( x & ~(x-1) )ne renverra que le bit le plus bas, quelle que soit l'architecture, la longueur du mot, etc. -zeroes / bit le plus élevé pour trouver le bit le plus bas s'il n'y a pas d'instruction explicite pour le faire.

S'il n'y a pas du tout de support matériel pertinent, l'implémentation de multiplication et de recherche de count-Leading-zeroes donnée ici ou l'un de ceux de la page Bit Twiddling Hacks peut être convertie de manière triviale pour donner le bit le plus bas en utilisant les identités ci-dessus et a l'avantage d'être sans succursales.

Weee, des tas de solutions et pas une référence en vue. Vous devriez avoir honte de vous ;-)

Ma machine est un Intel i530 (2,9 GHz), exécutant Windows 7 64 bits. J'ai compilé avec une version 32 bits de MinGW.

$ gcc --version
gcc.exe (GCC) 4.7.2

$ gcc bench.c -o bench.exe -std=c99 -Wall -O2
$ bench
Naive loop.         Time = 2.91  (Original questioner)
De Bruijn multiply. Time = 1.16  (Tykhyy)
Lookup table.       Time = 0.36  (Andrew Grant)
FFS instruction.    Time = 0.90  (ephemient)
Branch free mask.   Time = 3.48  (Dan / Jim Balter)
Double hack.        Time = 3.41  (DocMax)

$ gcc bench.c -o bench.exe -std=c99 -Wall -O2 -march=native
$ bench
Naive loop.         Time = 2.92
De Bruijn multiply. Time = 0.47
Lookup table.       Time = 0.35
FFS instruction.    Time = 0.68
Branch free mask.   Time = 3.49
Double hack.        Time = 0.92

Mon code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


#define ARRAY_SIZE 65536
#define NUM_ITERS 5000  // Number of times to process array


int find_first_bits_naive_loop(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned value = nums[i];
            if (value == 0)
                continue;
            unsigned pos = 0;
            while (!(value & 1))
            {
                value >>= 1;
                ++pos;
            }
            total += pos + 1;
        }
    }

    return total;
}


int find_first_bits_de_bruijn(unsigned nums[ARRAY_SIZE])
{
    static const int MultiplyDeBruijnBitPosition[32] = 
    {
       1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9, 
       32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10
    };

    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned int c = nums[i];
            total += MultiplyDeBruijnBitPosition[((unsigned)((c & -c) * 0x077CB531U)) >> 27];
        }
    }

    return total;
}


unsigned char lowestBitTable[256];
int get_lowest_set_bit(unsigned num) {
    unsigned mask = 1;
    for (int cnt = 1; cnt <= 32; cnt++, mask <<= 1) {
        if (num & mask) {
            return cnt;
        }
    }

    return 0;
}
int find_first_bits_lookup_table(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned int value = nums[i];
            // note that order to check indices will depend whether you are on a big 
            // or little endian machine. This is for little-endian
            unsigned char *bytes = (unsigned char *)&value;
            if (bytes[0])
                total += lowestBitTable[bytes[0]];
            else if (bytes[1])
              total += lowestBitTable[bytes[1]] + 8;
            else if (bytes[2])
              total += lowestBitTable[bytes[2]] + 16;
            else
              total += lowestBitTable[bytes[3]] + 24;
        }
    }

    return total;
}


int find_first_bits_ffs_instruction(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            total +=  __builtin_ffs(nums[i]);
        }
    }

    return total;
}


int find_first_bits_branch_free_mask(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned value = nums[i];
            int i16 = !(value & 0xffff) << 4;
            value >>= i16;

            int i8 = !(value & 0xff) << 3;
            value >>= i8;

            int i4 = !(value & 0xf) << 2;
            value >>= i4;

            int i2 = !(value & 0x3) << 1;
            value >>= i2;

            int i1 = !(value & 0x1);

            int i0 = (value >> i1) & 1? 0 : -32;

            total += i16 + i8 + i4 + i2 + i1 + i0 + 1;
        }
    }

    return total;
}


int find_first_bits_double_hack(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned value = nums[i];
            double d = value ^ (value - !!value); 
            total += (((int*)&d)[1]>>20)-1022; 
        }
    }

    return total;
}


int main() {
    unsigned nums[ARRAY_SIZE];
    for (int i = 0; i < ARRAY_SIZE; i++) {
        nums[i] = rand() + (rand() << 15);
    }

    for (int i = 0; i < 256; i++) {
        lowestBitTable[i] = get_lowest_set_bit(i);
    }


    clock_t start_time, end_time;
    int result;

    start_time = clock();
    result = find_first_bits_naive_loop(nums);
    end_time = clock();
    printf("Naive loop.         Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_de_bruijn(nums);
    end_time = clock();
    printf("De Bruijn multiply. Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_lookup_table(nums);
    end_time = clock();
    printf("Lookup table.       Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_ffs_instruction(nums);
    end_time = clock();
    printf("FFS instruction.    Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_branch_free_mask(nums);
    end_time = clock();
    printf("Branch free mask.   Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_double_hack(nums);
    end_time = clock();
    printf("Double hack.        Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
}

La solution la plus rapide (non intrinsèque / non assembleur) à ce problème consiste à rechercher l'octet le plus bas, puis à utiliser cet octet dans une table de recherche à 256 entrées. Cela vous donne une performance dans le pire des cas de quatre instructions conditionnelles et un meilleur cas de 1. Non seulement il s'agit du moins d'instructions, mais aussi du moins de branches, ce qui est très important sur le matériel moderne.

Votre table (256 entrées 8 bits) doit contenir l'index du LSB pour chaque nombre compris entre 0 et 255. Vous vérifiez chaque octet de votre valeur et trouvez l'octet non nul le plus bas, puis utilisez cette valeur pour rechercher l'index réel.

Cela nécessite 256 octets de mémoire, mais si la vitesse de cette fonction est si importante alors que 256 octets en valent la peine,

Par exemple

byte lowestBitTable[256] = {
.... // left as an exercise for the reader to generate
};

unsigned GetLowestBitPos(unsigned value)
{
  // note that order to check indices will depend whether you are on a big 
  // or little endian machine. This is for little-endian
  byte* bytes = (byte*)value;
  if (bytes[0])
    return lowestBitTable[bytes[0]];
  else if (bytes[1])
      return lowestBitTable[bytes[1]] + 8;
  else if (bytes[2])
      return lowestBitTable[bytes[2]] + 16;
  else
      return lowestBitTable[bytes[3]] + 24;  
}

OMG vient de faire une spirale.

Ce qui manque à la plupart de ces exemples, c'est un peu de compréhension du fonctionnement de tout le matériel.

Chaque fois que vous avez une branche, le CPU doit deviner quelle branche sera prise. Le tube d'instructions est chargé avec les instructions qui mènent sur le chemin deviné. Si le CPU a mal deviné, le tube d'instructions est vidé et l'autre branche doit être chargée.

Considérez la simple boucle while en haut. La supposition sera de rester dans la boucle. Ce sera faux au moins une fois quand il sortira de la boucle. Cela va rincer le tuyau d'instructions. Ce comportement est légèrement meilleur que de supposer qu'il quittera la boucle, auquel cas il viderait le tube d'instructions à chaque itération.

La quantité de cycles CPU perdus varie fortement d'un type de processeur à l'autre. Mais vous pouvez vous attendre entre 20 et 150 cycles CPU perdus.

Le pire groupe suivant est celui où vous pensez que vous allez économiser quelques itérations en divisant la valeur en plus petits morceaux et en ajoutant plusieurs branches supplémentaires. Chacune de ces branches ajoute une opportunité supplémentaire de rincer le tuyau d'instructions et coûte encore 20 à 150 cycles d'horloge.

Voyons ce qui se passe lorsque vous recherchez une valeur dans une table. Il y a de fortes chances que la valeur ne soit pas actuellement en cache, du moins pas la première fois que votre fonction est appelée. Cela signifie que le processeur est bloqué pendant que la valeur est chargée à partir du cache. Là encore, cela varie d'une machine à l'autre. Les nouvelles puces Intel utilisent en fait cette opportunité pour permuter les threads pendant que le thread actuel attend la fin du chargement du cache. Cela pourrait facilement être plus coûteux qu'un rinçage de tuyau d'instructions, mais si vous effectuez cette opération plusieurs fois, elle ne se produira probablement qu'une seule fois.

Il est clair que la solution à temps constant la plus rapide est celle qui implique des mathématiques déterministes. Une solution pure et élégante.

Mes excuses si cela était déjà couvert.

Chaque compilateur que j'utilise, à l'exception de XCODE AFAIK, a des caractéristiques intrinsèques de compilateur pour le scan de bits avant et le scan de bits inverse. Celles-ci seront compilées en une seule instruction d'assemblage sur la plupart des matériels sans cache manquant, sans prédiction de branchement et aucun autre programmeur n'a généré de blocages.

Pour les compilateurs Microsoft, utilisez _BitScanForward et _BitScanReverse.
Pour GCC, utilisez __builtin_ffs, __builtin_clz, __builtin_ctz.

En outre, veuillez vous abstenir de publier une réponse et de tromper les nouveaux arrivants si vous ne connaissez pas suffisamment le sujet discuté.

Désolé j'ai totalement oublié de fournir une solution. C'est le code que j'utilise sur l'IPAD qui n'a pas d'instructions de niveau d'assemblage pour la tâche:

unsigned BitScanLow_BranchFree(unsigned value)
{
    bool bwl = (value & 0x0000ffff) == 0;
    unsigned I1 = (bwl * 15);
    value = (value >> I1) & 0x0000ffff;

    bool bbl = (value & 0x00ff00ff) == 0;
    unsigned I2 = (bbl * 7);
    value = (value >> I2) & 0x00ff00ff;

    bool bnl = (value & 0x0f0f0f0f) == 0;
    unsigned I3 = (bnl * 3);
    value = (value >> I3) & 0x0f0f0f0f;

    bool bsl = (value & 0x33333333) == 0;
    unsigned I4 = (bsl * 1);
    value = (value >> I4) & 0x33333333;

    unsigned result = value + I1 + I2 + I3 + I4 - 1;

    return result;
}

La chose à comprendre ici est que ce n'est pas la comparaison qui coûte cher, mais la branche qui se produit après la comparaison. La comparaison dans ce cas est forcée à une valeur de 0 ou 1 avec le .. == 0, et le résultat est utilisé pour combiner les calculs qui se seraient produits de chaque côté de la branche.

Éditer:

Le code ci-dessus est totalement cassé. Ce code fonctionne et est toujours sans branche (s'il est optimisé):

int BitScanLow_BranchFree(ui value)
{
    int i16 = !(value & 0xffff) << 4;
    value >>= i16;

    int i8 = !(value & 0xff) << 3;
    value >>= i8;

    int i4 = !(value & 0xf) << 2;
    value >>= i4;

    int i2 = !(value & 0x3) << 1;
    value >>= i2;

    int i1 = !(value & 0x1);

    int i0 = (value >> i1) & 1? 0 : -32;

    return i16 + i8 + i4 + i2 + i1 + i0;
}

Cela renvoie -1 s'il est donné 0. Si vous ne vous souciez pas de 0 ou êtes heureux d'obtenir 31 pour 0, supprimez le calcul i0, économisant ainsi un morceau de temps.

Inspiré par cet article similaire qui consiste à rechercher un peu d'ensemble, je propose ce qui suit:

unsigned GetLowestBitPos(unsigned value)
{
   double d = value ^ (value - !!value); 
   return (((int*)&d)[1]>>20)-1023; 
}

Avantages:

• pas de boucles
• pas de ramification
• s'exécute en temps constant
• gère value = 0 en renvoyant un résultat autrement hors limites
• seulement deux lignes de code

Les inconvénients:

• suppose peu d'endianness comme codé (peut être corrigé en changeant les constantes)
• suppose que double est un vrai flotteur IEEE * 8 (IEEE 754)

Mettre à jour: comme indiqué dans les commentaires, une union est une implémentation plus propre (au moins pour C) et ressemblerait à:

unsigned GetLowestBitPos(unsigned value)
{
    union {
        int i[2];
        double d;
    } temp = { .d = value ^ (value - !!value) };
    return (temp.i[1] >> 20) - 1023;
}

Cela suppose des entiers 32 bits avec un stockage little-endian pour tout (pensez aux processeurs x86).

Cela peut être fait avec le pire des cas de moins de 32 opérations:

Principe: la vérification de 2 bits ou plus est tout aussi efficace que la vérification de 1 bit.

Ainsi, par exemple, rien ne vous empêche de vérifier dans quel groupe il se trouve en premier, puis de vérifier chaque bit du plus petit au plus grand dans ce groupe.

Donc ...
si vous cochez 2 bits à la fois, vous avez dans le pire des cas (Nbits / 2) + 1 chèque au total.
si vous cochez 3 bits à la fois, vous avez dans le pire des cas (Nbits / 3) + 2 chèques au total.
...

L'optimal serait de vérifier par groupes de 4. Ce qui nécessiterait dans le pire des cas 11 opérations au lieu de 32.

Le meilleur cas va de 1 vérification de vos algorithmes à 2 vérifications si vous utilisez cette idée de regroupement. Mais ce chèque supplémentaire dans le meilleur des cas en vaut la peine pour les pires économies.

Remarque: je l'écris en entier au lieu d'utiliser une boucle car c'est plus efficace de cette façon.

int getLowestBitPos(unsigned int value)
{
    //Group 1: Bits 0-3
    if(value&0xf)
    {
        if(value&0x1)
            return 0;
        else if(value&0x2)
            return 1;
        else if(value&0x4)
            return 2;
        else
            return 3;
    }

    //Group 2: Bits 4-7
    if(value&0xf0)
    {
        if(value&0x10)
            return 4;
        else if(value&0x20)
            return 5;
        else if(value&0x40)
            return 6;
        else
            return 7;
    }

    //Group 3: Bits 8-11
    if(value&0xf00)
    {
        if(value&0x100)
            return 8;
        else if(value&0x200)
            return 9;
        else if(value&0x400)
            return 10;
        else
            return 11;
    }

    //Group 4: Bits 12-15
    if(value&0xf000)
    {
        if(value&0x1000)
            return 12;
        else if(value&0x2000)
            return 13;
        else if(value&0x4000)
            return 14;
        else
            return 15;
    }

    //Group 5: Bits 16-19
    if(value&0xf0000)
    {
        if(value&0x10000)
            return 16;
        else if(value&0x20000)
            return 17;
        else if(value&0x40000)
            return 18;
        else
            return 19;
    }

    //Group 6: Bits 20-23
    if(value&0xf00000)
    {
        if(value&0x100000)
            return 20;
        else if(value&0x200000)
            return 21;
        else if(value&0x400000)
            return 22;
        else
            return 23;
    }

    //Group 7: Bits 24-27
    if(value&0xf000000)
    {
        if(value&0x1000000)
            return 24;
        else if(value&0x2000000)
            return 25;
        else if(value&0x4000000)
            return 26;
        else
            return 27;
    }

    //Group 8: Bits 28-31
    if(value&0xf0000000)
    {
        if(value&0x10000000)
            return 28;
        else if(value&0x20000000)
            return 29;
        else if(value&0x40000000)
            return 30;
        else
            return 31;
    }

    return -1;
}

Pourquoi ne pas utiliser la recherche binaire ? Cela se terminera toujours après 5 opérations (en supposant une taille int de 4 octets):

if (0x0000FFFF & value) {
    if (0x000000FF & value) {
        if (0x0000000F & value) {
            if (0x00000003 & value) {
                if (0x00000001 & value) {
                    return 1;
                } else {
                    return 2;
                }
            } else {
                if (0x0000004 & value) {
                    return 3;
                } else {
                    return 4;
                }
            }
        } else { ...
    } else { ...
} else { ...

Une autre méthode (division du module et recherche) mérite une mention spéciale ici à partir du même lien fourni par @ anton-tykhyy. cette méthode est très similaire en termes de performances à la méthode de multiplication et de recherche DeBruijn avec une légère mais importante différence.

division du module et recherche

 unsigned int v;  // find the number of trailing zeros in v
    int r;           // put the result in r
    static const int Mod37BitPosition[] = // map a bit value mod 37 to its position
    {
      32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
      7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
      20, 8, 19, 18
    };
    r = Mod37BitPosition[(-v & v) % 37];

La méthode de division et de recherche du module renvoie des valeurs différentes pour v = 0x00000000 et v = FFFFFFFF tandis que la méthode de multiplication et de recherche DeBruijn renvoie zéro sur les deux entrées.

tester:-

unsigned int n1=0x00000000, n2=0xFFFFFFFF;

MultiplyDeBruijnBitPosition[((unsigned int )((n1 & -n1) * 0x077CB531U)) >> 27]); /* returns 0 */
MultiplyDeBruijnBitPosition[((unsigned int )((n2 & -n2) * 0x077CB531U)) >> 27]); /* returns 0 */
Mod37BitPosition[(((-(n1) & (n1))) % 37)]); /* returns 32 */
Mod37BitPosition[(((-(n2) & (n2))) % 37)]); /* returns 0 */

Selon la page BitScan de programmation d'échecs et mes propres mesures, soustraire et xor est plus rapide que nier et masquer.

(Notez que si vous comptez les zéros de fin 0, la méthode telle que je l'ai renvoie 63alors que la négation et le masque retournent0 .)

Voici une soustraction et un xor 64 bits:

unsigned long v;  // find the number of trailing zeros in 64-bit v 
int r;            // result goes here
static const int MultiplyDeBruijnBitPosition[64] = 
{
  0, 47, 1, 56, 48, 27, 2, 60, 57, 49, 41, 37, 28, 16, 3, 61,
  54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11, 4, 62,
  46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
  25, 39, 14, 33, 19, 30, 9, 24, 13, 18, 8, 12, 7, 6, 5, 63
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v ^ (v-1)) * 0x03F79D71B4CB0A89U)) >> 58];

Pour référence, voici une version 64 bits de la méthode de négation et de masque:

unsigned long v;  // find the number of trailing zeros in 64-bit v 
int r;            // result goes here
static const int MultiplyDeBruijnBitPosition[64] = 
{
  0, 1, 48, 2, 57, 49, 28, 3, 61, 58, 50, 42, 38, 29, 17, 4,
  62, 55, 59, 36, 53, 51, 43, 22, 45, 39, 33, 30, 24, 18, 12, 5,
  63, 47, 56, 27, 60, 41, 37, 16, 54, 35, 52, 21, 44, 32, 23, 11,
  46, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x03F79D71B4CB0A89U)) >> 58];

Vous pouvez vérifier si l'un des bits d'ordre inférieur est défini. Si tel est le cas, regardez l'ordre inférieur des bits restants. par exemple,:

32 bits int - vérifiez si l'un des 16 premiers est défini. Si tel est le cas, vérifiez si l'un des 8 premiers est défini. si c'est le cas, ....

sinon, vérifiez si l'un des 16 supérieurs est défini.

C'est essentiellement une recherche binaire.

Voir ma réponse ici pour savoir comment le faire avec une seule instruction x86, sauf que pour trouver le bit défini le moins significatif, vous aurez besoin de l' BSFinstruction ("bit scan forward") au lieu d'être BSRdécrite ici.

Encore une autre solution, pas la plus rapide possible, mais qui semble assez bonne.
Au moins, il n'a pas de succursales. ;)

uint32 x = ...;  // 0x00000001  0x0405a0c0  0x00602000
x |= x <<  1;    // 0x00000003  0x0c0fe1c0  0x00e06000
x |= x <<  2;    // 0x0000000f  0x3c3fe7c0  0x03e1e000
x |= x <<  4;    // 0x000000ff  0xffffffc0  0x3fffe000
x |= x <<  8;    // 0x0000ffff  0xffffffc0  0xffffe000
x |= x << 16;    // 0xffffffff  0xffffffc0  0xffffe000

// now x is filled with '1' from the least significant '1' to bit 31

x = ~x;          // 0x00000000  0x0000003f  0x00001fff

// now we have 1's below the original least significant 1
// let's count them

x = x & 0x55555555 + (x >>  1) & 0x55555555;
                 // 0x00000000  0x0000002a  0x00001aaa

x = x & 0x33333333 + (x >>  2) & 0x33333333;
                 // 0x00000000  0x00000024  0x00001444

x = x & 0x0f0f0f0f + (x >>  4) & 0x0f0f0f0f;
                 // 0x00000000  0x00000006  0x00000508

x = x & 0x00ff00ff + (x >>  8) & 0x00ff00ff;
                 // 0x00000000  0x00000006  0x0000000d

x = x & 0x0000ffff + (x >> 16) & 0x0000ffff;
                 // 0x00000000  0x00000006  0x0000000d
// least sign.bit pos. was:  0           6          13

unsigned GetLowestBitPos(unsigned value)
{
    if (value & 1) return 1;
    if (value & 2) return 2;
    if (value & 4) return 3;
    if (value & 8) return 4;
    if (value & 16) return 5;
    if (value & 32) return 6;
    if (value & 64) return 7;
    if (value & 128) return 8;
    if (value & 256) return 9;
    if (value & 512) return 10;
    if (value & 1024) return 11;
    if (value & 2048) return 12;
    if (value & 4096) return 13;
    if (value & 8192) return 14;
    if (value & 16384) return 15;
    if (value & 32768) return 16;
    if (value & 65536) return 17;
    if (value & 131072) return 18;
    if (value & 262144) return 19;
    if (value & 524288) return 20;
    if (value & 1048576) return 21;
    if (value & 2097152) return 22;
    if (value & 4194304) return 23;
    if (value & 8388608) return 24;
    if (value & 16777216) return 25;
    if (value & 33554432) return 26;
    if (value & 67108864) return 27;
    if (value & 134217728) return 28;
    if (value & 268435456) return 29;
    if (value & 536870912) return 30;
    return 31;
}

50% de tous les nombres reviendront sur la première ligne de code.

75% de tous les nombres reviendront sur les 2 premières lignes de code.

87% de tous les nombres reviendront dans les 3 premières lignes de code.

94% de tous les nombres reviendront dans les 4 premières lignes de code.

97% de tous les nombres reviendront dans les 5 premières lignes de code.

etc.

Je pense que les gens qui se plaignent de l'inefficacité du pire des cas pour ce code ne comprennent pas à quel point cette condition se produira.

J'ai trouvé cette astuce en utilisant des 'masques magiques' dans "L'art de la programmation, partie 4", qui le fait en temps O (log (n)) pour un nombre de n bits. [avec log (n) espace supplémentaire]. Les solutions typiques vérifiant le bit défini sont soit O (n), soit nécessitent un espace supplémentaire O (n) pour une table de consultation, c'est donc un bon compromis.

Masques magiques:

m0 = (...............01010101)  
m1 = (...............00110011)
m2 = (...............00001111)  
m3 = (.......0000000011111111)
....

Idée clé: Nombre de zéros de fin dans x = 1 * [(x & m0) = 0] + 2 * [(x & m1) = 0] + 4 * [(x & m2) = 0] + ...

int lastSetBitPos(const uint64_t x) {
    if (x == 0)  return -1;

    //For 64 bit number, log2(64)-1, ie; 5 masks needed
    int steps = log2(sizeof(x) * 8); assert(steps == 6);
    //magic masks
    uint64_t m[] = { 0x5555555555555555, //     .... 010101
                     0x3333333333333333, //     .....110011
                     0x0f0f0f0f0f0f0f0f, //     ...00001111
                     0x00ff00ff00ff00ff, //0000000011111111 
                     0x0000ffff0000ffff, 
                     0x00000000ffffffff };

    //Firstly extract only the last set bit
    uint64_t y = x & -x;

    int trailZeros = 0, i = 0 , factor = 0;
    while (i < steps) {
        factor = ((y & m[i]) == 0 ) ? 1 : 0;
        trailZeros += factor * pow(2,i);
        ++i;
    }
    return (trailZeros+1);
}

Si C ++ 11 est disponible pour vous, un compilateur peut parfois faire la tâche pour vous :)

constexpr std::uint64_t lssb(const std::uint64_t value)
{
    return !value ? 0 : (value % 2 ? 1 : lssb(value >> 1) + 1);
}

Le résultat est un index basé sur 1.

Ceci concerne la réponse de @Anton Tykhyy

Voici mon implémentation C ++ 11 constexpr supprimant les casts et supprimant un avertissement sur VC ++ 17 en tronquant un résultat 64 bits à 32 bits:

constexpr uint32_t DeBruijnSequence[32] =
{
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
constexpr uint32_t ffs ( uint32_t value )
{
    return  DeBruijnSequence[ 
        (( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF)
            >> 27];
}

Pour contourner le problème de 0x1 et 0x0 renvoyant tous les deux 0, vous pouvez faire:

constexpr uint32_t ffs ( uint32_t value )
{
    return (!value) ? 32 : DeBruijnSequence[ 
        (( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF)
            >> 27];
}

mais si le compilateur ne peut pas ou ne prétraite pas l'appel, il ajoutera quelques cycles au calcul.

Enfin, si vous êtes intéressé, voici une liste d'assertions statiques pour vérifier que le code fait ce qui est prévu:

static_assert (ffs(0x1) == 0, "Find First Bit Set Failure.");
static_assert (ffs(0x2) == 1, "Find First Bit Set Failure.");
static_assert (ffs(0x4) == 2, "Find First Bit Set Failure.");
static_assert (ffs(0x8) == 3, "Find First Bit Set Failure.");
static_assert (ffs(0x10) == 4, "Find First Bit Set Failure.");
static_assert (ffs(0x20) == 5, "Find First Bit Set Failure.");
static_assert (ffs(0x40) == 6, "Find First Bit Set Failure.");
static_assert (ffs(0x80) == 7, "Find First Bit Set Failure.");
static_assert (ffs(0x100) == 8, "Find First Bit Set Failure.");
static_assert (ffs(0x200) == 9, "Find First Bit Set Failure.");
static_assert (ffs(0x400) == 10, "Find First Bit Set Failure.");
static_assert (ffs(0x800) == 11, "Find First Bit Set Failure.");
static_assert (ffs(0x1000) == 12, "Find First Bit Set Failure.");
static_assert (ffs(0x2000) == 13, "Find First Bit Set Failure.");
static_assert (ffs(0x4000) == 14, "Find First Bit Set Failure.");
static_assert (ffs(0x8000) == 15, "Find First Bit Set Failure.");
static_assert (ffs(0x10000) == 16, "Find First Bit Set Failure.");
static_assert (ffs(0x20000) == 17, "Find First Bit Set Failure.");
static_assert (ffs(0x40000) == 18, "Find First Bit Set Failure.");
static_assert (ffs(0x80000) == 19, "Find First Bit Set Failure.");
static_assert (ffs(0x100000) == 20, "Find First Bit Set Failure.");
static_assert (ffs(0x200000) == 21, "Find First Bit Set Failure.");
static_assert (ffs(0x400000) == 22, "Find First Bit Set Failure.");
static_assert (ffs(0x800000) == 23, "Find First Bit Set Failure.");
static_assert (ffs(0x1000000) == 24, "Find First Bit Set Failure.");
static_assert (ffs(0x2000000) == 25, "Find First Bit Set Failure.");
static_assert (ffs(0x4000000) == 26, "Find First Bit Set Failure.");
static_assert (ffs(0x8000000) == 27, "Find First Bit Set Failure.");
static_assert (ffs(0x10000000) == 28, "Find First Bit Set Failure.");
static_assert (ffs(0x20000000) == 29, "Find First Bit Set Failure.");
static_assert (ffs(0x40000000) == 30, "Find First Bit Set Failure.");
static_assert (ffs(0x80000000) == 31, "Find First Bit Set Failure.");

Voici une alternative simple, même si la recherche de journaux est un peu coûteuse.

if(n == 0)
  return 0;
return log2(n & -n)+1;   //Assuming the bit index starts from 1

Récemment, je vois que le premier ministre de Singapour a publié un programme qu'il a écrit sur Facebook, il y a une ligne pour le mentionner.

La logique est simplement "valeur et valeur", supposons que vous ayez 0x0FF0, puis 0FF0 & (F00F + 1), ce qui équivaut à 0x0010, cela signifie que le 1 le plus bas est dans le 4ème bit .. :)

Si vous avez les ressources, vous pouvez sacrifier de la mémoire pour améliorer la vitesse:

static const unsigned bitPositions[MAX_INT] = { 0, 0, 1, 0, 2, /* ... */ };

unsigned GetLowestBitPos(unsigned value)
{
    assert(value != 0); // handled separately
    return bitPositions[value];
}

Remarque: cette table consommerait au moins 4 Go (16 Go si nous laissons le type de retour commeunsigned ). Ceci est un exemple d'échange d'une ressource limitée (RAM) contre une autre (vitesse d'exécution).

Si votre fonction doit rester portable et fonctionner aussi vite que possible à tout prix, ce serait la voie à suivre. Dans la plupart des applications du monde réel, une table de 4 Go est irréaliste.