Pozycja najmniejszego znaczącego bitu, który jest ustawiony

Dlaczego nie użyć wbudowanego ffs ? (Chwyciłem stronę podręcznika z Linuksa, ale jest ona szerzej dostępna.)

Ffs ( 3) - Linuksowa strona man

Nazwa

Ffs-znajdź pierwszy bit w słowie

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

Opis

Funkcja FFS () Zwraca pozycję pierwszego (najmniej znaczącego) bitu ustawionego w słowie i. najmniej znaczącym bitem jest pozycja 1, a najbardziej znaczącym np. 32 lub 64. Funkcje ffsll() i ffsl () robią to samo, ale przyjmują argumenty o prawdopodobnie różnej wielkości.

Return Value

Funkcje te zwracają pozycję pierwszego zestawu bitów lub 0, jeśli w i nie są ustawione żadne bity.

Zgodne z

4.3 BSD, POSIX.1-2001.

Uwagi

Systemy BSD mają prototyp w <string.h>.

Istnieje instrukcja montażu x86 (bsf), która to zrobi. :)

Bardziej zoptymalizowany?!

Uwaga Boczna:

Optymalizacja na tym poziomie jest z natury zależna od architektury. Dzisiejsze procesory są zbyt złożone (pod względem przewidywania gałęzi, braków pamięci podręcznej, pipeliningu), że tak trudno przewidzieć, który kod jest wykonywany szybciej na jakiej architekturze. Zmniejszenie operacji z 32 do 9 lub takie rzeczy mogą nawet zmniejszyć wydajność na niektórych architekturach. Zoptymalizowany kod na jednej architekturze może skutkować gorszym kodem w drugiej. Myślę, że albo zoptymalizujesz to dla konkretnego procesora, albo zostawisz to tak, jak jest i pozwolisz kompilatorowi wybrać to, co uważa za lepsze.

Większość nowoczesnych architektur będzie miała instrukcję znajdowania pozycji najniższego ustawionego bitu lub najwyższego ustawionego bitu, lub zliczania liczby zer wiodących itp.

Jeśli masz jedną instrukcję tej klasy, możesz tanio naśladować inne.

Poświęć chwilę, aby przejrzeć to na papierze i zdaj sobie sprawę, że x & (x-1) wyczyści najniższy bit W x, A ( x & ~(x-1) ) zwróci tylko najniższy bit, niezależnie od architektury, długości słowa itp. Wiedząc o tym, jest trywialne jest użycie hardware count-leading-zero / highest-set-bit, aby znaleźć najniższy Bit, jeśli nie ma wyraźnej instrukcji, aby to zrobić.

Jeśli nie ma odpowiedniego wsparcia sprzętowego, implementacja multiply-and-lookup count-leading-zer podana tutaj lub jedna z tych na stronie bit Twidling Hacki może być trywialnie przekonwertowana do podania najniższego zestawu bitów przy użyciu powyższych tożsamości i ma tę zaletę, że jest bez rozgałęzień.

Najszybszym rozwiązaniem tego problemu jest znalezienie najniższego bajtu i użycie go w 256-wejściowej tabeli wyszukiwania. Daje to najgorszy przypadek wykonania czterech instrukcji warunkowych i najlepszy przypadek 1. Jest to nie tylko najmniejsza ilość instrukcji, ale także najmniejsza ilość gałęzi, która jest bardzo ważna na nowoczesnym sprzęcie.

Twoja tabela (256 8-bitowych wpisów) powinna zawierać indeks LSB dla każdej liczby z zakresu 0-255. Sprawdzasz każdy bajt Twojej wartości i znajdź najniższy niezerowy bajt, a następnie użyj tej wartości, aby wyszukać prawdziwy indeks.

Wymaga to 256 bajtów pamięci, ale jeśli prędkość tej funkcji jest tak ważna, to 256 bajtów jest tego warte,

Np.

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

Weee, mnóstwo rozwiązań, a nie punkt odniesienia w zasięgu wzroku. Powinniście się wstydzić; -)

$ 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

Mój kod:

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

OMG ma to właśnie spirala.

Większości z tych przykładów brakuje odrobiny zrozumienia, jak działa cały sprzęt.

Za każdym razem, gdy masz gałąź, procesor musi odgadnąć, która gałąź zostanie pobrana. Rura instrukcji jest ładowana instrukcjami, które prowadzą w dół odgadniętej ścieżki. Jeśli procesor pomylił się, to rura instrukcji zostaje przepłukana, a druga gałąź musi zostać załadowana.

Rozważ prostą pętlę while na górze. Zgadywanka będzie do bądź na bieżąco. Będzie źle przynajmniej raz, gdy opuści pętlę. Spowoduje to spłukanie rury instrukcji. To zachowanie jest nieco lepsze niż zgadywanie, że opuści pętlę, w którym to przypadku przepuści rurę instrukcji na każdej iteracji.

Ilość traconych cykli procesora różni się znacznie w zależności od typu procesora. Ale możesz spodziewać się od 20 do 150 utraconych cykli procesora.

Następna gorsza grupa to miejsce, w którym myślisz, że uratujesz kilka iteracji, dzieląc wartość na mniejsze kawałki i dodając kilka kolejnych gałęzi. Każda z tych gałęzi dodaje dodatkową możliwość spłukania rury instrukcji i kosztuje kolejne 20 do 150 cykli zegara.

Rozważmy, co się dzieje, gdy wyszukujesz wartość w tabeli. Są szanse, że wartość nie jest obecnie w pamięci podręcznej, przynajmniej nie po raz pierwszy funkcja jest wywoływana. Oznacza to, że procesor zostaje zatrzymany podczas ładowania wartości z pamięci podręcznej. Ponownie różni się to od jedna maszyna do drugiej. Nowe chipy Intela faktycznie wykorzystać to jako okazję do wymiany wątków, podczas gdy aktualny wątek czeka na załadowanie pamięci podręcznej, aby zakończyć. Może to być z łatwością droższe niż spłukiwanie rury instrukcji, jednak jeśli wykonujesz tę operację wiele razy, prawdopodobnie wystąpi tylko raz.

Oczywiście najszybsze rozwiązanie w czasie stałym to takie, które obejmuje deterministyczną matematykę. Czyste i eleganckie rozwiązanie.

Każdy kompilator, którego używam, oprócz Xcode AFAIK, ma wbudowane funkcje kompilatora zarówno dla forward bitscan, jak i reverse bitscan. Będą one kompilowane do jednej instrukcji montażu na większości sprzętu bez braków pamięci podręcznej, bez przewidywania braków gałęzi i żadnych innych programistów generowanych potykaczy.

Dla kompilatorów Microsoft użyj _BitScanForward & _BitScanReverse.
Dla GCC użyj _ _ builtin _ ffs, _ _ builtin _ clz, _ _ builtin _ ctz.

Dodatkowo prosimy o powstrzymanie się od publikowanie odpowiedzi i potencjalnie wprowadzające w błąd nowicjusze, jeśli nie masz wystarczającej wiedzy na temat omawianego tematu.

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

Rzeczą do zrozumienia jest to, że to nie porównanie jest drogie, ale gałąź, która występuje po porównaniu. Porównanie w tym przypadku jest wymuszone do wartości 0 LUB 1 z .. == 0, a wynik jest używany do połączenia matematyki, która miałaby miejsce po obu stronach gałęzi.

Edit:

Powyższy kod jest całkowicie zepsuty. Ten kod działa i nadal jest wolny od gałęzi (jeśli jest zoptymalizowany):

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

Zwraca -1 jeśli podano 0. Jeśli nie zależy ci na 0 lub jesteś szczęśliwy, aby uzyskać 31 za 0, Usuń obliczenie i0, oszczędzając kawałek czasu.

Zainspirowany tym podobnym postem , który wiąże się z poszukiwaniem określonego bitu, proponuję:

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

Plusy:

• brak pętli
• brak rozgałęzień
• działa w stałym czasie
• obsługuje wartość = 0 zwracając wynik poza granicami
• tylko dwie linijki kodu

Wady:

• zakłada małą endianess jako zakodowaną (można ją naprawić zmieniając stałe)
• zakłada, że double jest rzeczywistym * 8 IEEE float (IEEE 754)

Aktualizacja: Jak zaznaczono w komentarzach, Unia jest czystszą implementacją (przynajmniej dla C) i wyglądałaby następująco:

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

Zakłada to 32-bitowe ints z little-endian storage dla wszystkiego (pomyśl o procesorach x86).

Można to zrobić w najgorszym przypadku poniżej 32 operacji:

Zasada: sprawdzanie 2 lub więcej bitów jest tak samo efektywne jak sprawdzanie 1 bitów.

Więc na przykład nic nie stoi na przeszkodzie, aby sprawdzić, które zgrupowanie jest najpierw, a następnie sprawdzić każdy bit od najmniejszego do największego w tej grupie.

Optymalne byłoby sprawdzenie w grupach po 4 osoby. Co wymagałoby w najgorszym przypadku 11 operacji zamiast 32.

Najlepszy przypadek przechodzi od sprawdzania 1 algorytmów do sprawdzania 2, Jeśli używasz tego pomysłu grupowania. Ale ten dodatkowy czek 1 w najlepszym przypadku jest tego wart dla najgorszych oszczędności.

Uwaga: piszę to w całości zamiast używać pętli, ponieważ jest to bardziej wydajne w ten sposób.

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

Dlaczego nie użyć wyszukiwania binarnego? To zawsze zakończy się po 5 operacjach (zakładając Rozmiar int 4 bajtów):

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 { ...

Inna metoda (podział modułów i wyszukiwanie) zasługuje tutaj na szczególną uwagę z tego samego linku podanego przez @anton-tykhyy. metoda ta jest bardzo podobna pod względem wydajności do metody debruijn multiply i lookup z niewielką, ale istotną różnicą.

Podział modułu i wyszukiwanie

 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];

Podział modułu i metoda lookup zwraca różne wartości dla v = 0x00000000 i v = FFFFFFFF, podczas gdy DeBruijn multiply i metoda lookup zwraca zero na obu wejścia.

Test:-

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 */

Według strony Chess Programming BitScan i moich własnych pomiarów, odjąć i xor jest szybszy niż negować i mask.

(zauważ, że jeśli zamierzasz policzyć końcowe zera w 0, metoda jak mam zwraca 63 podczas gdy negate i maska zwracają 0.)

Oto 64-bitowy odejmowanie i xor:

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];

Dla odniesienia, oto 64-bitowa wersja metody negate i mask:

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];

Możesz sprawdzić, czy któryś z bitów niższego rzędu jest ustawiony. Jeśli tak, to spójrz na niższą kolejność pozostałych bitów. np.:

32bit int-sprawdza czy któraś z pierwszych 16 jest ustawiona. Jeśli tak, sprawdź, czy którakolwiek z pierwszych 8 jest ustawiona. jeśli tak, to....

Jeśli nie, sprawdź, czy którykolwiek z górnych 16 jest ustawiony..

Zasadniczo jest to wyszukiwanie binarne.

Zobacz moją odpowiedź tutaj, aby dowiedzieć się, jak to zrobić z pojedynczą instrukcją x86, z tym wyjątkiem, że aby znaleźć najmniejszy znaczący bit set, potrzebujesz instrukcji BSF ("Bit scan forward") zamiast BSR tam opisanej.

Jeszcze jedno rozwiązanie, nie najszybsze, ale wydaje się całkiem dobre.
Przynajmniej nie ma gałęzi. ;)

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% wszystkich liczb powróci w pierwszej linii kodu.

75% wszystkich liczb powróci w dwóch pierwszych linijkach kodu.

87% wszystkich liczb powróci w pierwszych 3 linijkach kodu.

94% wszystkich liczb powróci w pierwszych 4 linijkach kodu.

97% wszystkich liczb powróci w pierwszych 5 linijkach kodu.

Itd.

Odkryłem tę sprytną sztuczkę za pomocą " magicznych masek "w" sztuce programowania, część 4", która robi to w czasie o(log(N)) dla n-bitowej liczby. [z logiem (N) extra spacja]. Typowe rozwiązania sprawdzające dla ustawionego bitu to O (n) lub potrzebują O (N) dodatkowego miejsca na tabelę wyszukiwania, więc jest to dobry kompromis.

Magiczne maski:

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

Idea klucza: Liczba zer końcowych w 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);
}

Jeśli C++11 jest dostępny dla Ciebie, kompilator czasami może wykonać zadanie za ciebie:)

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

Wynik jest indeksem opartym na 1.

To jest w odniesieniu do @ Anton Tykhyy odpowiedz

Oto moja implementacja C++11 constexpr rezygnująca z odlewów i usuwająca Ostrzeżenie NA VC++17 poprzez obcięcie 64-bitowego wyniku do 32 bitów:

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];
}

Aby obejść problem 0x1 i 0x0 oba zwracające 0 możesz zrobić:

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

Ale jeśli kompilator nie może lub nie przetworzy połączenia, doda kilka cykli do obliczeń.

Wreszcie, jeśli zainteresowany, oto lista twierdzeń statycznych, aby sprawdzić, że kod robi to, co jest zamierzone:

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.");

Tutaj jest jedna prosta alternatywa, mimo że znalezienie logów jest trochę kosztowne.

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

Ostatnio widzę, że premier Singapuru opublikował na facebook program, który napisał, jest jedna linijka, aby o tym wspomnieć..

Logika jest po prostu "wartość & - wartość", Załóżmy, że masz 0x0FF0, to, 0FF0 & (F00F + 1), co jest równe 0x0010, co oznacza, że najniższy 1 znajduje się w 4-tym bitie.. :)

Jeśli masz zasoby, możesz poświęcić pamięć w celu poprawy szybkości:

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

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

Uwaga: Ta tabela pochłonie co najmniej 4 GB(16 GB, jeśli pozostawimy Typ powrotu jako unsigned). Jest to przykład wymiany jednego ograniczonego zasobu (pamięci RAM) na inny (szybkość realizacji).

Jeśli twoja funkcja musi pozostać przenośna i działać tak szybko, jak to możliwe za wszelką cenę, to jest to droga do zrobienia. W większości rzeczywistych aplikacji stół 4GB jest nierealne.