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

Szukam skutecznego sposobu na określenie pozycji najmniej znaczącego bitu, który jest ustawiony jako liczba całkowita, np. Dla 0x0FF0 byłoby to 4.

Prosta implementacja jest taka:

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

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

Jakieś pomysły, jak wycisnąć z tego kilka cykli?

(Uwaga: to pytanie jest dla ludzi, którzy lubią takie rzeczy, a nie dla ludzi, którzy mówią mi, że xyzoptimization jest zła).

[edytuj] Dziękuję wszystkim za pomysły! Nauczyłem się też kilku innych rzeczy. Chłodny!

Bit Twiddling Hacks oferuje doskonałą kolekcję, eee, nieco krętych hacków, z dołączoną dyskusją na temat wydajności / optymalizacji. Moim ulubionym rozwiązaniem twojego problemu (z tej strony) jest «pomnóż i wyszukaj»:

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

Pomocne referencje:

• „ Używanie sekwencji de Bruijn do indeksowania 1 w słowie komputerowym ” - Wyjaśnienie, dlaczego powyższy kod działa.
• " Reprezentacja planszy> Bitboards> BitScan " - Szczegółowa analiza tego problemu, ze szczególnym uwzględnieniem programowania szachowego

Dlaczego nie skorzystać z wbudowanego ffs ? (Wziąłem stronę podręcznika systemowego z Linuksa, ale jest ona szerzej dostępna).

ffs (3) - strona podręcznika systemu Linux

Imię

ffs - znajdź pierwszy bit ustawiony w słowie

Streszczenie

#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 w słowie i. Najmniej znaczący bit to pozycja 1, a najbardziej znacząca pozycja, np. 32 lub 64. Funkcje ffsll () i ffsl () robią to samo, ale pobierają argumenty o możliwie różnej wielkości.

Wartość zwracana

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

Zgodne z

4.3BSD, POSIX.1-2001.

Uwagi

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

Istnieje instrukcja asemblera x86 ( bsf), która to zrobi. :)

Bardziej zoptymalizowany ?!

Dygresja:

Optymalizacja na tym poziomie jest z natury zależna od architektury. Dzisiejsze procesory są zbyt złożone (pod względem przewidywania gałęzi, błędów pamięci podręcznej, przetwarzania potokowego), więc tak trudno jest przewidzieć, który kod jest wykonywany szybciej na jakiej architekturze. Zmniejszenie liczby operacji z 32 do 9 lub podobnych rzeczy może nawet zmniejszyć wydajność na niektórych architekturach. Zoptymalizowany kod w jednej architekturze może spowodować gorszy kod w drugiej. Myślę, że albo zoptymalizowałbyś to dla konkretnego procesora, albo zostawiłbyś to tak, jak jest i pozwolił kompilatorowi wybrać to, co uważa za lepsze.

Większość współczesnych architektur będzie zawierała instrukcje dotyczące znalezienia pozycji najniższego ustawionego bitu lub najwyższego ustawionego bitu lub zliczania wiodących zer itp.

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

Poświęć chwilę, aby popracować nad tym na papierze i zdaj sobie sprawę, że x & (x-1)wyczyści najniższy ustawiony bit w x i ( x & ~(x-1) )zwróci tylko najniższy ustawiony bit, niezależnie od architektury, długości słowa itp. Wiedząc o tym, używanie sprzętowego licznika początkowego jest trywialne -zeroes / najwyższy-ustawiony-bit, aby znaleźć najniższy ustawiony bit, jeśli nie ma wyraźnej instrukcji, aby to zrobić.

Jeśli w ogóle nie ma odpowiedniego wsparcia sprzętowego, implementacja mnożenia i wyszukiwania zer wiodących podana tutaj lub jedna z tych na stronie Bit Twiddling Hacks można w trywialny sposób przekonwertować, aby uzyskać najniższy ustawiony bit przy użyciu powyższych tożsamości i ma tę zaletę, że jest bez gałęzi.

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

Mój komputer to Intel i530 (2,9 GHz) z systemem Windows 7 w wersji 64-bitowej. Skompilowałem z 32-bitową wersją 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

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

Najszybszym rozwiązaniem (nie wewnętrznym / asemblerowym) jest znalezienie najniższego bajtu, a następnie użycie tego bajtu w 256-wpisowej tablicy wyszukiwania. Daje to najgorszy wynik z czterech instrukcji warunkowych, a w najlepszym przypadku 1. Jest to nie tylko najmniejsza liczba instrukcji, ale także najmniejsza liczba rozgałęzień, co jest bardzo ważne 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 swojej wartości i znajdujesz najniższy niezerowy bajt, a następnie używasz tej wartości do wyszukiwania rzeczywistego indeksu.

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

Na przykład

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 ma to po prostu spiralne.

W większości tych przykładów brakuje odrobiny zrozumienia działania całego sprzętu.

Za każdym razem, gdy masz gałąź, procesor musi odgadnąć, która gałąź zostanie wybrana. Potok instrukcji jest ładowany instrukcjami prowadzącymi w dół odgadniętej ścieżki. Jeśli CPU źle odgadł, potok instrukcji zostanie opróżniony, a druga gałąź musi zostać załadowana.

Rozważ prostą pętlę while na górze. Domyślam się, że pozostanie w pętli. Przynajmniej raz będzie źle, gdy opuści pętlę. Spowoduje to przepłukanie rury instrukcji. To zachowanie jest nieco lepsze niż zgadywanie, że opuści pętlę, w którym to przypadku będzie przepłukiwał potok z instrukcją przy każdej iteracji.

Ilość utraconych 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 ta, w której myślisz, że zamierzasz zaoszczędzić kilka iteracji, dzieląc wartość na mniejsze części i dodając kilka kolejnych gałęzi. Każda z tych gałęzi daje dodatkową możliwość przepłukania potoku instrukcji i kosztuje kolejne 20 do 150 cykli zegara.

Zastanówmy się, co się stanie, gdy wyszukasz wartość w tabeli. Prawdopodobnie wartość nie znajduje się obecnie w pamięci podręcznej, a przynajmniej nie przy pierwszym wywołaniu funkcji. Oznacza to, że procesor zatrzymuje się, gdy wartość jest ładowana z pamięci podręcznej. Znowu różni się to w zależności od maszyny. Nowe chipy Intela wykorzystują to w rzeczywistości jako okazję do zamiany wątków, podczas gdy bieżący wątek oczekuje na zakończenie ładowania pamięci podręcznej. Może to być z łatwością droższe niż przepłukiwanie rur z instrukcjami, jednak jeśli wykonujesz tę operację kilka razy, prawdopodobnie nastąpi to tylko raz.

Najwyraźniej najszybszym rozwiązaniem ze stałym czasem jest to, które obejmuje matematykę deterministyczną. Czyste i eleganckie rozwiązanie.

Przepraszam, jeśli to już zostało uwzględnione.

Każdy kompilator, którego używam, z wyjątkiem XCODE AFAIK, ma wbudowane funkcje kompilatora zarówno dla skanowania bitowego w przód, jak i skanowania wstecznego. Będą one kompilować się do pojedynczej instrukcji asemblera na większości sprzętu bez pomijania pamięci podręcznej, bez przewidywania błędów gałęzi i żadnych innych przeszkód generowanych przez programistę.

W przypadku kompilatorów firmy Microsoft użyj _BitScanForward i _BitScanReverse.
W przypadku GCC użyj __builtin_ffs, __builtin_clz, __builtin_ctz.

Ponadto prosimy o powstrzymanie się od publikowania odpowiedzi i potencjalnie wprowadzających w błąd nowoprzybyłych, jeśli nie masz wystarczającej wiedzy na temat omawianego tematu.

Przepraszam, całkowicie zapomniałem podać rozwiązanie. Oto kod, którego używam na iPadzie, który nie ma instrukcji na poziomie asemblera dla tego zadania:

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

Należy tutaj zrozumieć, że to nie porównanie jest drogie, ale gałąź, która pojawia się po porównaniu. Porównanie w tym przypadku jest zmuszane do wartości 0 lub 1 za pomocą .. == 0, a wynik jest używany do łączenia matematyki, która wystąpiłaby po obu stronach gałęzi.

Edytować:

Powyższy kod jest całkowicie uszkodzony. Ten kod działa i nadal jest wolny od gałęzi (jeśli został 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 wartość -1, jeśli otrzymujesz 0. Jeśli nie zależy ci na 0 lub jesteś szczęśliwy, jeśli masz 31 za 0, usuń obliczenie i0, oszczędzając trochę czasu.

Zainspirowany tym podobnym postem, który dotyczy wyszukiwania zestawu bitów, oferuję co następuje:

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

Plusy:

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

Cons:

• zakłada mały endianness zgodnie z kodem (można to naprawić, zmieniając stałe)
• zakłada, że ​​double jest prawdziwym * 8 IEEE float (IEEE 754)

Aktualizacja: Jak wskazano w komentarzach, związek jest czystszą implementacją (przynajmniej dla C) i wyglądałby 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 się 32-bitowe inte z pamięcią little-endian na wszystko (pomyśl o procesorach x86).

Można to zrobić w najgorszym przypadku z mniej niż 32 operacjami:

Zasada: sprawdzenie 2 lub więcej bitów jest tak samo wydajne, jak sprawdzenie 1 bitu.

Na przykład nic nie powstrzymuje Cię przed sprawdzeniem, które grupowanie jest w pierwszej kolejności, a następnie sprawdzeniem każdego bitu od najmniejszego do największego w tej grupie.

Więc ...
jeśli sprawdzasz 2 bity na raz, masz w najgorszym przypadku (Nbits / 2) + 1 sprawdzenie łącznie.
jeśli sprawdzasz 3 bity naraz, masz w najgorszym przypadku (Nbity / 3) + 2 kontrole łącznie.
...

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

Najlepszym przypadkiem jest przejście od 1 testu algorytmów do 2 sprawdzeń, jeśli używasz tego pomysłu na grupowanie. Ale ten dodatkowy 1 czek w najlepszym przypadku jest tego wart, aby uzyskać oszczędności w najgorszym przypadku.

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 skorzystać z wyszukiwania binarnego ? To zawsze zakończy się po 5 operacjach (zakładając rozmiar int 4 bajty):

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 (dzielenie modułu i wyszukiwanie) zasługuje na specjalną wzmiankę z tego samego linku, który udostępnił @ anton-tykhyy. ta metoda jest bardzo podobna pod względem wydajności do metody mnożenia i wyszukiwania DeBruijn z niewielką, ale istotną różnicą.

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

metoda dzielenia modułu i wyszukiwania zwraca różne wartości dla v = 0x00000000 i v = FFFFFFFF, podczas gdy metoda mnożenia i wyszukiwania DeBruijn zwraca zero na obu wejściach.

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, odejmowanie i xor jest szybsze niż negowanie i maskowanie.

(Zauważ, że jeśli zamierzasz liczyć końcowe zera w 0, metoda, którą mam, zwraca, 63podczas gdy negacja i maska ​​powracają 0.)

Oto 64-bitowe 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 porównania, oto 64-bitowa wersja metody negacji i maski:

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, spójrz na niższą kolejność pozostałych bitów. na przykład,:

32bit int - sprawdź, czy któreś z pierwszych 16 jest ustawione. Jeśli tak, sprawdź, czy ustawiono którykolwiek z pierwszych 8. jeśli tak, ....

jeśli nie, sprawdź, czy któreś z 16 górnych są ustawione.

Zasadniczo jest to wyszukiwanie binarne.

Zobacz moją odpowiedź tutaj, aby dowiedzieć się, jak to zrobić za pomocą pojedynczej instrukcji x86, z wyjątkiem tego, że aby znaleźć najmniej znaczący zestaw bitów, będziesz potrzebować instrukcji BSF(„skanowanie bitów do przodu”) zamiast BSRopisanej w tym miejscu.

Jeszcze inne rozwiązanie, nie najszybsze możliwe, 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 wróci w pierwszym wierszu kodu.

75% wszystkich liczb powróci w pierwszych 2 wierszach kodu.

87% wszystkich liczb wróci w pierwszych 3 wierszach kodu.

94% wszystkich liczb wróci w pierwszych 4 wierszach kodu.

97% wszystkich liczb wróci w pierwszych 5 wierszach kodu.

itp.

Myślę, że ludzie, którzy narzekają na to, jak nieefektywny jest najgorszy scenariusz dla tego kodu, nie rozumieją, jak rzadki będzie ten stan.

Znalazłem tę sprytną sztuczkę przy użyciu „magicznych masek” w „Sztuce programowania, część 4”, która robi to w czasie O (log (n)) dla liczby n-bitowej. [z log (n) dodatkową spacją]. Typowe rozwiązania sprawdzające ustawiony bit to O (n) lub wymagające O (n) dodatkowej przestrzeni na tablicę przeglądową, więc jest to dobry kompromis.

Magiczne maski:

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

Kluczowa idea: liczba końcowych zer 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 dla Ciebie dostępny, kompilator czasami może wykonać to 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 od 1.

Dotyczy to odpowiedzi @Anton Tykhyy

Oto moja implementacja constexpr w C ++ 11 eliminująca rzutowanie i usuwająca ostrzeżenie w VC ++ 17 przez obcięcie wyniku 64-bitowego 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 zwracających 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 może wstępnie przetworzyć wywołania, doda kilka cykli do obliczenia.

Na koniec, jeśli jesteś zainteresowany, oto lista statycznych potwierdzeń, które sprawdzają, czy kod robi to, co ma:

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

Oto jedna prosta alternatywa, mimo że znajdowanie dzienników jest trochę kosztowne.

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

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

Logika to po prostu „wartość i -wartość”, przypuśćmy, że masz 0x0FF0, a następnie 0FF0 i (F00F + 1), co równa się 0x0010, co oznacza, że ​​najniższa 1 znajduje się w czwartym bicie .. :)

Jeśli masz zasoby, możesz poświęcić pamięć, aby poprawić prędkość:

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 zużyłaby co najmniej 4 GB (16 GB, jeśli pozostawimy zwracany typ jakounsigned ). To jest przykład wymiany jednego ograniczonego zasobu (RAM) na inny (szybkość wykonywania).

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