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


121

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!


while ((wartość _N >> (++ pos))! = 0);
Thomas

Odpowiedzi:


170

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:


18
Dlaczego głos przeciw? Jest to prawdopodobnie najszybsza realizacja, w zależności od szybkości mnożenia. Z pewnością jest to kompaktowy kod, a sztuczka (v & -v) jest czymś, czego każdy powinien się nauczyć i zapamiętać.
Adam Davis,

2
+1 bardzo fajnie, ile kosztuje operacja mnożenia w porównaniu z operacją if (X&Y)?
Brian R. Bondy

4
Czy ktoś wie, jak wydajność tego wypada w porównaniu z __builtin_ffsllub ffsl?
Steven Lu

2
@Jim Balter, ale modulo jest bardzo wolne w porównaniu do mnożenia na nowoczesnym sprzęcie. Więc nie nazwałbym tego lepszym rozwiązaniem.
Apriori

2
Wydaje mi się, że obie wartości 0x01 i 0x00 dają w tablicy wartość 0. Najwyraźniej ta sztuczka wskaże, że najniższy bit jest ustawiony, jeśli przekazano 0!
abelenky

80

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


6
FYI, to jest kompilowane do odpowiedniego polecenia assemblera, jeśli jest dostępne.
Jérémie

46

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.


20
@dwc: Rozumiem, ale myślę, że ta klauzula: „Jakieś pomysły, jak wycisnąć z tego kilka cykli?” sprawia, że ​​taka odpowiedź jest całkowicie akceptowalna!
Mehrdad Afshari

5
+1 Jego odpowiedź jest koniecznie zależna od jego architektury z powodu endianizmu, więc przejście do instrukcji montażu jest całkowicie poprawną odpowiedzią.
Chris Lutz,

3
+1 Sprytna odpowiedź, tak, to nie jest C ani C ++, ale jest to odpowiednie narzędzie do tego zadania.
Andrew Hare

1
Czekaj, nieważne. Rzeczywista wartość liczby całkowitej nie ma tutaj znaczenia. Przepraszam.
Chris Lutz,

2
@Bastian: Ustawiają ZF = 1, jeśli operand ma wartość zero.
Mehrdad Afshari

43

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.


18

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

8
Testy porównawcze dla de Bruijn i lookup mogą być mylące - siedząc w takiej wąskiej pętli, po pierwszej operacji tabele wyszukiwania dla każdego typu zostaną przypięte w pamięci podręcznej L1 aż do ostatniej pętli. To raczej nie pasuje do użycia w świecie rzeczywistym.
MattW

1
W przypadku danych wejściowych z zerem w młodszym bajcie pobiera wyższe bajty przez przechowywanie / ponowne ładowanie zamiast przesuwania, z powodu rzutowania wskaźnika. (BTW całkowicie niepotrzebne i sprawia, że ​​jest zależny od endianów, w przeciwieństwie do zmiany nie). Tak czy inaczej, więc mikroznak jest nie tylko nierealistyczny z powodu gorącej pamięci podręcznej, ale ma również przygotowane predyktory gałęzi i testuje dane wejściowe, które przewidują bardzo dobrze i sprawiają, że LUT wykonuje mniej pracy. Wiele rzeczywistych przypadków użycia ma bardziej jednolity rozkład wyników, a nie danych wejściowych.
Peter Cordes,

2
Twoja pętla FFS jest niestety spowolniona przez fałszywą zależność w instrukcji BSF, której nie unika twój stary, stary kompilator ( ale nowszy gcc powinien, to samo dla popcnt / lzcnt / tzcnt . BSFMa fałszywą zależność od swojego wyjścia (ponieważ rzeczywiste zachowanie gdy input = 0 ma pozostawić wyjście niezmienione). gcc niestety zamienia to w zależność przenoszoną w pętli, nie czyszcząc rejestru między iteracjami pętli. Zatem pętla powinna działać z częstotliwością jeden na 5 cykli, wąskie gardło BSF (3) + CMOV (2) opóźnienie
Peter Cordes,

1
Twój test porównawczy wykazał, że LUT ma prawie dwukrotnie większą przepustowość niż metoda FFS, co bardzo dobrze pasuje do moich przewidywań analizy statycznej :). Zwróć uwagę, że mierzysz przepustowość, a nie opóźnienie, ponieważ jedyną zależnością szeregową w pętli jest sumowanie do sumy. Bez fałszywej zależności ffs()powinien mieć przepustowość jednego na zegar (3 uops, 1 dla BSF i 2 dla CMOV i mogą działać na różnych portach). Przy takim samym obciążeniu pętli można uruchomić 7 jednostek ALU Uops (na procesorze) z prędkością 3 na zegar. Nad głową dominuje! Źródło: agner.org/optimize
Peter Cordes,

1
Tak, wykonanie poza kolejnością może nakładać się na wiele iteracji pętli, jeśli bsf ecx, [ebx+edx*4]nie zostanie potraktowane ecxjako dane wejściowe, na które musiało czekać. (ECX został ostatnio napisany przez CMOV poprzedniej iteratonu). Ale procesor zachowuje się w ten sposób, aby zaimplementować zachowanie "pozostaw miejsce docelowe niezmodyfikowane, jeśli źródło jest zerowe" (więc nie jest to naprawdę fałszywa dep, jak w przypadku TZCNT; zależność danych jest wymagana, ponieważ nie ma rozgałęziania + spekulacyjne wykonanie przy założeniu że wejście jest niezerowe). Moglibyśmy temu zaradzić, dodając xor ecx,ecxprzed the bsf, aby zerwać zależność od ECX.
Peter Cordes,

17

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

1
W rzeczywistości jest to najgorszy przypadek z trzech warunków warunkowych :) Ale tak, jest to najszybsze podejście (i zwykle to, czego ludzie szukają w takich pytaniach podczas rozmowy kwalifikacyjnej).
Brian

4
Czy nie chcesz gdzieś tam +8, +16, +24?
Mark Ransom

7
Każda tablica przeglądowa zwiększa prawdopodobieństwo pominięcia pamięci podręcznej i może wiązać się z kosztami dostępu do pamięci, które mogą być o kilka rzędów wielkości wyższe niż wykonywanie instrukcji.
Mehrdad Afshari

1
użyłbym nawet przesunięć bitowych (za każdym razem przesuwając je o 8). wtedy można by to zrobić całkowicie za pomocą rejestrów. używając wskaźników, będziesz musiał uzyskać dostęp do pamięci.
Johannes Schaub - litb

1
Rozsądne rozwiązanie, ale między możliwością, że tabela przeglądowa nie znajduje się w pamięci podręcznej (co można rozwiązać, jak wskazano) a liczbą gałęzi (potencjalne błędne przewidywanie gałęzi), zdecydowanie wolę rozwiązanie polegające na mnożeniu i wyszukiwaniu (brak gałęzi, mniejsza tabela przeglądowa). Oczywiście, jeśli możesz użyć elementów wewnętrznych lub asemblacji liniowej, prawdopodobnie są one lepszym wyborem. Jednak to rozwiązanie nie jest złe.

13

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.


3
Naprawiłem to dla ciebie. Pamiętaj, aby przetestować to, co publikujesz.
Jim Balter

5
Jak można to nazwać „bez gałęzi”, skoro zawiera w sobie operator trójskładnikowy?
BoltBait

2
To ruch warunkowy. Pojedyncza instrukcja języka asemblera, która przyjmuje obie możliwe wartości jako parametry i wykonuje operację mov w oparciu o ocenę warunku. I tak jest „wolne od gałęzi”. nie ma skoku na inny nieznany lub prawdopodobnie nieprawidłowy adres.
Dan

FWIW gcc generuje gałęzie nawet na -O3 godbolt.org/z/gcsUHd
Qix - MONICA BYŁA BŁĘDNA

7

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


1
Ciekawe - nadal boję się używać podwójnych do arytmetyki bitów, ale będę o tym pamiętać
peterchen

Korzystanie z funkcji frexp () może uczynić ją nieco bardziej przenośną
aka.nice

1
Znakowanie typu przez rzutowanie wskaźników nie jest bezpieczne w C lub C ++. Użyj memcpy w C ++ lub unii w C. (Lub unii w C ++, jeśli Twój kompilator gwarantuje, że jest bezpieczny. Na przykład rozszerzenia GNU do C ++ (obsługiwane przez wiele kompilatorów) gwarantują, że używanie typu unii jest bezpieczne.)
Peter Cordes

1
Starsze gcc również tworzy lepszy kod z sumą zamiast rzutowania wskaźnika: przenosi się bezpośrednio z regu FP (xmm0) do rax (z movq) zamiast przechowywać / przeładowywać. Nowsze gcc i clang używają movq w obu przypadkach. Zobacz godbolt.org/g/x7JBiL, aby uzyskać wersję unii. Czy to celowe, że wykonujesz arytmetyczną zmianę o 20? Twoje założenia powinny również lista, że intjest int32_t, i że podpisał prawo przesunięcia jest przesunięcie arytmetyczne (w C ++ To realizacji zdefiniowane)
Peter Cordes

1
Przy okazji, Visual Studio (przynajmniej 2013) również używa podejścia test / setcc / sub. Sam bardziej lubię cmp / adc.
DocMax,

5

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

+1 ode mnie. Nie jest najszybszy, ale jest szybszy niż oryginał, o co chodziło ...
Andrew Grant

@ onebyone.livejournal.com: Nawet jeśli w kodzie był błąd, to koncepcja grupowania jest punktem, który próbowałem rozwiązać. Rzeczywisty przykład kodu nie ma większego znaczenia i można go uczynić bardziej zwartym, ale mniej wydajnym.
Brian R. Bondy

Zastanawiam się tylko, czy jest naprawdę zła część mojej odpowiedzi, czy też ludziom nie podobało się to, że napisałem ją w całości?
Brian R. Bondy

@ onebyone.livejournal.com: Kiedy porównujesz 2 algorytmy, powinieneś porównać je takimi, jakimi są, nie zakładając, że jeden zostanie magicznie przekształcony w fazie optymalizacji. Nigdy też nie twierdziłem, że mój algorytm jest „szybszy”. Tyle że to mniej operacji.
Brian R. Bondy,

@ onebyone.livejournal.com: ... Nie muszę profilować powyższego kodu, żeby wiedzieć, że jest mniej operacji. Widzę to wyraźnie. Nigdy nie zgłosiłem żadnych roszczeń wymagających profilowania.
Brian R. Bondy,

4

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

+1 To jest bardzo podobne do mojej odpowiedzi. Najlepszy czas wykonania przypadku jest gorszy niż moja sugestia, ale czas uruchomienia najgorszego przypadku jest lepszy.
Brian R. Bondy,

2

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

1
modjest wolny. Zamiast tego można użyć oryginalnej metody mnożenia i wyszukiwania i odejmowania !vod, raby obsłużyć przypadki skrajne.
Eitan T

3
@EitanT optymalizator może równie dobrze przekształcić ten mod w szybkie mnożenie, jak w radości hakerów
phuclv

2

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

To (v ^ (v-1))działa pod warunkiem v != 0. W takim przypadku v == 0zwraca 0xFF .... FF, a jednocześnie (v & -v)daje zero (co zresztą też jest błędne, buf przynajmniej prowadzi do rozsądnego wyniku).
CiaPan

@CiaPan: To dobra uwaga, wspomnę o tym. Domyślam się, że istnieje inna liczba De Bruijna, która rozwiązałaby ten problem, umieszczając 0 na 63. indeksie.
jnm2

Nie, to nie jest problem. 0 i 0x8000000000000000 skutkują 0xFFFFFFFFFFFFFFFF po v ^ (v-1), więc nie ma możliwości ich rozróżnienia. W moim scenariuszu zero nigdy nie zostanie wprowadzone.
jnm2

1

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.


1

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.


1

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

aby uzyskać wszystkie 1s od najmniej znaczącej 1 do LSB, użyj ((x & -x) - 1) << 1zamiast tego
phuclv

jeszcze szybszy sposób:x ^ (x-1)
phuclv

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


3
I najgorszy przypadek pomyłki w 32 gałęziach :)

1
Czy nie można tego przynajmniej zmienić w przełącznik ...?
Steven Lu,

- Czy nie można tego przynajmniej zmienić w przełącznik…? Czy próbowałeś to zrobić, zanim zasugerowałeś, że jest to możliwe? Od kiedy możesz wykonywać obliczenia w przypadku przełącznika? To tabela przeglądowa, a nie klasa.
j riv

1

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

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.


1
Sprytne, ale kompiluje się do katastrofalnie złego zestawu, gdy dane wejściowe nie są stałą czasu kompilacji. godbolt.org/g/7ajMyT . (Głupia pętla nad bitami z gcc lub rzeczywiste wywołanie funkcji rekurencyjnej z clang). Gcc / clang może oceniać ffs()w czasie kompilacji, więc nie musisz go używać do pracy ciągłej propagacji. (Trzeba unikać inline asm, oczywiście). Jeśli naprawdę potrzebują czegoś, co działa jak C ++ 11 constexpr, nadal można używać GNU C __builtin_ffs.
Peter Cordes

0

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

0

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

-3

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 .. :)


1
To izoluje najniższy bit, ale nie podaje jego pozycji, o którą jest to pytanie.
rhashimoto

Nie sądzę, żeby to działało w przypadku znalezienia ostatniego kawałka.
yyny

wartość & ~ wartość wynosi 0.
khw

Ups, moje oczy się psują. Pomyliłem minus z tyldą. zignoruj ​​mój komentarz
khw

-8

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.


1
Zakres danych wejściowych jest już określony przez typ parametru - „unsigned” to wartość 32-bitowa, więc nie, nic ci nie jest.
Brian

3
umm ... czy twój mityczny system i system operacyjny mają koncepcję pamięci stronicowanej? Ile czasu to będzie kosztować?
Mikeage

14
To jest brak odpowiedzi. Twoje rozwiązanie jest całkowicie nierealistyczne we WSZYSTKICH rzeczywistych aplikacjach i nazywanie go „kompromisem” jest nieszczere. Twój mityczny system, który ma 16 GB pamięci RAM, którą można przeznaczyć na jedną funkcję, po prostu nie istnieje. Równie dobrze odpowiadałbyś „użyj komputera kwantowego”.
Brian

3
Poświęcić pamięć dla szybkości? Tabela wyszukiwania 4 GB + nigdy nie zmieści się w pamięci podręcznej na żadnej obecnie istniejącej maszynie, więc wyobrażam sobie, że jest to prawdopodobnie wolniejsze niż prawie wszystkie inne odpowiedzi tutaj.

1
Argh. Ta okropna odpowiedź wciąż mnie prześladuje :)@Dan: Masz rację co do buforowania pamięci. Zobacz komentarz Mikeage powyżej.
e.James
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.