Jeśli mam jakąś liczbę całkowitą n i chcę poznać położenie najbardziej znaczącego bitu (to znaczy, jeśli najmniej znaczący bit znajduje się po prawej stronie, chcę poznać położenie najdalszego lewego bitu, czyli 1), jaka jest najszybsza / najskuteczniejsza metoda dowiedzenia się?
Wiem, że POSIX obsługuje ffs()
metodę w strings.h, aby znaleźć pierwszy ustawiony bit, ale wydaje się, że nie ma odpowiedniej fls()
metody.
Czy jest jakiś naprawdę oczywisty sposób na zrobienie tego, którego mi brakuje?
A co w przypadkach, gdy nie można używać funkcji POSIX do przenoszenia?
Edycja: A co z rozwiązaniem, które działa zarówno na architekturach 32-bitowych, jak i 64-bitowych (wiele list kodów wydaje się działać tylko na 32-bitowych intach).
Odpowiedzi:
GCC ma :
Spodziewałbym się, że zostaną przetłumaczone na coś w miarę wydajnego dla twojej obecnej platformy, bez względu na to, czy będzie to jeden z tych fantazyjnych algorytmów do zawijania bitów, czy też pojedyncza instrukcja.
Przydatny trik jeśli wejście może być zerowy jest
__builtin_clz(x | 1)
: bezwarunkowo ustawienie niskiej trochę bez modyfikowania żadnych innych sprawia, że wyjście31
dlax=0
bez zmiany wyjścia dla jakiegokolwiek innego wejścia.Aby tego uniknąć, inną opcją są elementy wewnętrzne specyficzne dla platformy, takie jak ARM GCC
__clz
(bez nagłówka) lub x86_lzcnt_u32
na procesorach obsługującychlzcnt
instrukcję. (Uważaj, żelzcnt
dekoduje jakbsr
na starszych procesorach zamiast błędów, co daje 31-lzcnt dla niezerowych wejść.)Niestety nie ma możliwości przenośnego wykorzystania różnych instrukcji CLZ na platformach innych niż x86, które definiują wynik dla input = 0 jako 32 lub 64 (zgodnie z szerokością operandu). x86 też to
lzcnt
robi,bsr
generując indeks bitowy, który kompilator musi odwrócić, chyba że używasz31-__builtin_clz(x)
.(„Niezdefiniowany wynik” nie jest C Undefined Behavior, tylko wartością, która nie jest zdefiniowana. W rzeczywistości jest to wszystko, co znajdowało się w rejestrze docelowym podczas wykonywania instrukcji. AMD to udokumentuje, Intel nie, ale procesory Intela implementują to zachowanie . Ale to nie jest to, co było wcześniej w zmiennej C, do której przypisujesz, zwykle tak nie działa, gdy gcc zamienia C w asm. Zobacz także Dlaczego zerwanie "zależności wyjściowej" LZCNT ma znaczenie? )
źródło
__builtin_ctz
overffs
, który kompiluje się do BSF i CMOV, aby obsłużyć przypadek wejściowy równy zero. Na architekturach bez wystarczająco krótkiej implementacji (np. Stary ARM bezclz
instrukcji), gcc emituje wywołanie funkcji pomocniczej libgcc.Zakładając, że korzystasz z x86 i gry dla trochę wbudowanego asemblera, Intel dostarcza
BSR
instrukcje („odwrotne skanowanie bitowe”). Jest szybki na niektórych x86 (mikrokodowany na innych). Z instrukcji:(Jeśli korzystasz z PowerPC, istnieje podobna
cntlz
instrukcja („liczenie zer wiodących”).)Przykładowy kod dla gcc:
Zobacz także ten samouczek asemblera wbudowanego , który pokazuje (sekcja 9.4), że jest on znacznie szybszy niż kod zapętlony.
źródło
Ponieważ 2 ^ N jest liczbą całkowitą z ustawionym tylko N-tym bitem (1 << N), znalezienie pozycji (N) najwyższego ustawionego bitu jest liczbą całkowitą o podstawie 2 tej liczby.
http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
Ten „oczywisty” algorytm może nie być przezroczysty dla wszystkich, ale gdy zdasz sobie sprawę, że kod przesuwa się w prawo o jeden bit wielokrotnie, aż skrajny lewy bit zostanie przesunięty (zwróć uwagę, że C traktuje każdą niezerową wartość jako prawdę) i zwraca liczbę zmian, ma to sens. Oznacza to również, że działa nawet wtedy, gdy ustawiono więcej niż jeden bit - wynik jest zawsze dla najbardziej znaczącego bitu.
Jeśli przewiniesz w dół na tej stronie, istnieją szybsze, bardziej złożone odmiany. Jeśli jednak wiesz, że masz do czynienia z liczbami z wieloma wiodącymi zerami, naiwne podejście może zapewnić akceptowalną prędkość, ponieważ przesuwanie bitów jest dość szybkie w C, a prosty algorytm nie wymaga indeksowania tablicy.
UWAGA: Używając wartości 64-bitowych, zachowaj szczególną ostrożność podczas korzystania z wyjątkowo sprytnych algorytmów; wiele z nich działa poprawnie tylko dla wartości 32-bitowych.
źródło
>>>
. Plus prawdopodobnie komparator!= 0
i nieokreślona liczba nawiasów.To powinno być błyskawiczne:
źródło
To trochę tak, jakby znaleźć rodzaj logu liczb całkowitych. Są trochę skomplikowane sztuczki, ale stworzyłem do tego własne narzędzie. Celem jest oczywiście szybkość.
Zrozumiałem, że procesor ma już automatyczny detektor bitów, używany do konwersji liczb całkowitych na zmiennoprzecinkowe! Więc użyj tego.
Ta wersja rzutuje wartość na podwójną, a następnie odczytuje wykładnik, który mówi, gdzie znajdował się bit. Fantazyjne przesunięcie i odjęcie polega na wyodrębnieniu odpowiednich części z wartości IEEE.
Nieco szybsze jest użycie pływaków, ale zmiennoprzecinkowe mogą podać tylko pierwsze 24-bitowe pozycje ze względu na mniejszą precyzję.
Aby zrobić to bezpiecznie, bez niezdefiniowanego zachowania w C ++ lub C, użyj
memcpy
zamiast rzutowania wskaźnika do dziurkowania typów. Kompilatorzy wiedzą, jak skutecznie go wbudować.Lub w C99 i nowszych użyj pliku
union {double d; uint32_t u[2];};
. Należy jednak pamiętać, że w C ++ punning typu union jest obsługiwany tylko w niektórych kompilatorach jako rozszerzenie, a nie w ISO C ++.Zwykle będzie to wolniejsze niż specyficzne dla platformy wewnętrzne instrukcje zliczania zer wiodących, ale przenośne ISO C nie ma takiej funkcji. Niektóre procesory nie mają również instrukcji zliczania wiodących zera, ale niektóre z nich mogą skutecznie konwertować liczby całkowite na
double
. Jednak wpisywanie wzorca bitowego FP z powrotem do liczby całkowitej może być powolne (np. Na PowerPC wymaga przechowywania / przeładowania i zwykle powoduje zablokowanie magazynu).Ten algorytm może być potencjalnie przydatny w implementacjach SIMD, ponieważ mniej procesorów ma SIMD
lzcnt
. x86 otrzymał taką instrukcję tylko z AVX512CDźródło
Tutaj Kaz Kylheku
Porównałem dwa podejścia do tych liczb ponad 63-bitowych (długi typ długi na gcc x86_64), trzymając się z dala od bitu znaku.
(Tak się składa, że do czegoś potrzebuję tego „znajdź najwyższy bit”).
Zaimplementowałem wyszukiwanie binarne oparte na danych (ściśle oparte na jednej z powyższych odpowiedzi). Zaimplementowałem również ręcznie całkowicie rozwinięte drzewo decyzyjne, które jest po prostu kodem z natychmiastowymi operandami. Żadnych pętli, żadnych tabel.
Drzewo decyzyjne (upper_bit_unrolled) zostało ocenione jako szybsze o 69%, z wyjątkiem przypadku n = 0, dla którego wyszukiwanie binarne ma jawny test.
Specjalny test wyszukiwania binarnego dla przypadku 0 jest tylko 48% szybszy niż drzewo decyzyjne, które nie ma specjalnego testu.
Kompilator, maszyna: (GCC 4.5.2, -O3, x86-64, 2867 MHz Intel Core i5).
Szybki i brudny program testowy:
Używając tylko -O2, różnica staje się większa. Drzewo decyzyjne jest prawie czterokrotnie szybsze.
Porównałem również z naiwnym kodem przesuwania bitów:
Jest to szybkie tylko dla małych liczb, jak można by się spodziewać. Ustalając, że najwyższy bit to 1 dla n == 1, test porównawczy był szybszy o ponad 80%. Jednak połowa losowo wybranych liczb w przestrzeni 63-bitowej ma ustawiony 63. bit!
Na wejściu 0x3FFFFFFFFFFFFFFF wersja drzewa decyzyjnego jest nieco szybsza niż na 1 i pokazuje, że jest o 1120% szybsza (12,2 razy) niż przesuwnik bitów.
Dokonam również porównania drzewa decyzyjnego z wbudowanymi GCC, a także spróbuję mieszanki danych wejściowych zamiast powtarzania dla tej samej liczby. Mogą występować pewne przewidywania gałęzi i być może nierealistyczne scenariusze buforowania, które sztucznie przyspieszają powtórzenia.
źródło
Co powiesz na
?
źródło
1 rejestr, 13 instrukcji. Wierz lub nie, ale jest to zazwyczaj szybsze niż wspomniana powyżej instrukcja BSR, która działa w czasie liniowym. To jest czas logarytmiczny.
Z http://aggregate.org/MAGIC/#Most%20Ssequant%201%20Bit
źródło
__builtin_clz
jeśli jest włączony z-march=native
czy czymś (ponieważ jest szybki na każdym procesorze, który go obsługuje). Nawet na procesorach, takich jak rodzina AMD Bulldozer, gdzie BSR jest „wolny”, nie jest aż tak wolny: 7 m-operacji z 4-taktowymi opóźnieniami i jedną przepustowością na 4c. Na Atom BSR działa bardzo wolno: 16 cykli. Na Silvermont jest to 10 uopsów z 10 cyklami latencji. To może być nieco mniejsze opóźnienie niż BSR na Silvermont, ale IDK.Oto kilka (prostych) testów porównawczych algorytmów obecnie podanych na tej stronie ...
Algorytmy nie zostały przetestowane na wszystkich wejściach typu unsigned int; więc sprawdź to najpierw, zanim na ślepo użyjesz czegoś;)
Na moim komputerze najlepiej działają clz (__builtin_clz) i asm. asm wydaje się nawet szybszy niż clz ... ale może to wynikać z prostego testu porównawczego ...
źródło
Chociaż prawdopodobnie użyłbym tej metody tylko wtedy, gdybym absolutnie potrzebował najlepszej możliwej wydajności (np. Do pisania jakiejś gry planszowej z użyciem bitboardów), najbardziej wydajnym rozwiązaniem jest użycie wbudowanego ASM. Zobacz sekcję Optymalizacje w tym poście na blogu, aby znaleźć kod z wyjaśnieniem.
źródło
Potrzebowałem rutyny, aby to zrobić i przed przeszukaniem sieci (i znalezieniem tej strony) wymyśliłem własne rozwiązanie oparte na wyszukiwaniu binarnym. Chociaż jestem pewien, że ktoś już to zrobił! Działa w stałym czasie i może być szybsze niż opublikowane "oczywiste" rozwiązanie, chociaż nie zgłaszam żadnych wielkich roszczeń, tylko zamieszczam je dla zainteresowania.
źródło
to jest jakiś rodzaj wyszukiwania binarnego, działa ze wszystkimi typami liczb całkowitych (bez znaku!)
dopełnić:
źródło
typedef
s, ani niczego poza makrami preprocesora. To jest powszechnie przyjęta konwencja.Niektóre zbyt złożone odpowiedzi tutaj. Technika Debruin powinna być używana tylko wtedy, gdy dane wejściowe są już potęgą dwójki, w przeciwnym razie jest lepszy sposób. Dla mocy 2 wejść Debruin jest absolutnie najszybszy, nawet szybszy niż
_BitScanReverse
na każdym testowanym przeze mnie procesorze. Jednak w ogólnym przypadku_BitScanReverse
(lub jakikolwiek element wewnętrzny jest wywoływany w twoim kompilatorze) jest najszybszy (na niektórych procesorach może być jednak mikrokodowany).Jeśli funkcja wewnętrzna nie wchodzi w grę, tutaj jest optymalne rozwiązanie programowe do przetwarzania ogólnych danych wejściowych.
Zauważ, że ta wersja nie wymaga na końcu wyszukiwania Debruin, w przeciwieństwie do większości innych odpowiedzi. Oblicza pozycję w miejscu.
Tabele mogą być jednak lepsze, jeśli wywołujesz je wielokrotnie, ryzyko pominięcia pamięci podręcznej zostanie przyćmione przez przyspieszenie tabeli.
Powinno to zapewnić największą przepustowość spośród wszystkich podanych tutaj odpowiedzi dotyczących oprogramowania, ale jeśli wywołujesz to tylko sporadycznie, preferuj rozwiązanie bez tabel, takie jak mój pierwszy fragment.
źródło
Jak wskazują powyższe odpowiedzi, istnieje wiele sposobów określenia najbardziej znaczącego bitu. Jednak, jak również wskazano, metody te mogą być unikalne dla rejestrów 32- lub 64-bitowych. Strona bitów stanford.edu zawiera rozwiązania, które działają zarówno dla komputerów 32-bitowych, jak i 64-bitowych. Przy odrobinie pracy można je połączyć, aby zapewnić solidne podejście oparte na architekturze do uzyskania MSB. Rozwiązanie, do którego doszedłem, które skompilowałem / pracowałem na komputerach 64 i 32-bitowych, to:
źródło
#ifdef BUILD_64
flagą? W takim przypadku nie będzie potrzebna redefinicja w ramach warunku.Wersja w C przy użyciu kolejnych przybliżeń:
Zaleta: czas działania jest stały niezależnie od podanej liczby, ponieważ liczba pętli jest zawsze taka sama. (4 pętle w przypadku użycia „unsigned int”)
źródło
msb += (n>>msb) ? step : -step;
), prawdopodobnie więcej kompilatorów utworzy asm bez gałęzi, unikając błędnych przewidywań gałęzi na każdym kroku ( stackoverflow.com/questions/11227809/ ... ).Wiem, że to pytanie jest bardzo stare, ale po tym, jak sam zaimplementowałem funkcję msb () , stwierdziłem, że większość rozwiązań przedstawionych tutaj i na innych stronach internetowych niekoniecznie jest najbardziej wydajnych - przynajmniej dla mojej osobistej definicji wydajności (patrz również Aktualizacja poniżej ). Dlatego:
Większość rozwiązań (zwłaszcza tych, które wykorzystują jakiś rodzaj binarnego schematu wyszukiwania lub naiwne podejście, które wykonuje liniowe skanowanie od prawej do lewej) wydaje się pomijać fakt, że w przypadku dowolnych liczb binarnych niewiele jest takich, które zaczynają się od bardzo długiej sekwencji zera. W rzeczywistości dla dowolnej szerokości bitowej połowa wszystkich liczb całkowitych zaczyna się od 1, a jedna czwarta z nich zaczyna się od 01 . Widzisz, dokąd zmierzam? Mój argument jest taki, że skanowanie liniowe zaczynające się od najbardziej znaczącej pozycji bitowej do najmniej znaczącej (od lewej do prawej) nie jest tak „liniowe”, jak mogłoby się wydawać na pierwszy rzut oka.
Można wykazać 1 , że dla dowolnej szerokości bitowej średnia liczba bitów, które należy przetestować, wynosi co najwyżej 2. Przekłada się to na zamortyzowaną złożoność czasową O (1) w odniesieniu do liczby bitów (!) .
Oczywiście najgorszym przypadkiem jest nadal O (n) , gorsze niż O (log (n)), które uzyskuje się przy podejściach podobnych do wyszukiwania binarnego, ale ponieważ jest tak niewiele najgorszych przypadków, są one pomijalne dla większości aplikacji ( Aktualizacja : niezupełnie: może być ich niewiele, ale mogą wystąpić z dużym prawdopodobieństwem - patrz aktualizacja poniżej).
Oto "naiwne" podejście, które wymyśliłem, które przynajmniej na moim komputerze przewyższa większość innych podejść (schematy wyszukiwania binarnego dla 32-bitowych intów zawsze wymagają log 2 (32) = 5 kroków, podczas gdy ten głupi algorytm wymaga mniej średnio niż 2) - przepraszam, że to C ++, a nie czyste C:
Aktualizacja : Podczas gdy to, co tutaj napisałem, jest całkowicie prawdziwe dla dowolnych liczb całkowitych, gdzie każda kombinacja bitów jest równie prawdopodobna (mój test szybkości mierzył po prostu, ile czasu zajęło określenie MSB dla wszystkich 32-bitowych liczb całkowitych), rzeczywistych liczb całkowitych, dla która taka funkcja zostanie wywołana, zwykle postępuje zgodnie z innym wzorcem: na przykład w moim kodzie ta funkcja jest używana do określenia, czy rozmiar obiektu jest potęgą 2, lub do znalezienia następnej potęgi 2 większej lub równej niż rozmiar obiektu . Domyślam się, że większość aplikacji używających MSB zawiera liczby, które są znacznie mniejsze niż maksymalna liczba, jaką może reprezentować liczba całkowita (rozmiary obiektów rzadko wykorzystują wszystkie bity w size_t). W tym przypadku moje rozwiązanie będzie faktycznie działać gorzej niż metoda wyszukiwania binarnego - więc prawdopodobnie powinno być preferowane to drugie, mimo że moje rozwiązanie będzie szybciej przeszukiwać wszystkie liczby całkowite.
TL; DR: Rzeczywiste liczby całkowite prawdopodobnie będą miały odchylenie w kierunku najgorszego przypadku tego prostego algorytmu, co ostatecznie pogorszy jego działanie - pomimo faktu, że jest on amortyzowany O (1) dla naprawdę dowolnych liczb całkowitych.
1 Argument wygląda tak (szkic): Niech n będzie liczbą bitów (szerokość bitu). Łącznie jest 2 n liczb całkowitych, które można przedstawić za pomocą n bitów. Istnieją 2 liczby całkowite n - 1 zaczynające się od 1 (pierwsze 1 jest stałe, pozostałe n - 1 bitów może być dowolnymi). Te liczby całkowite wymagają tylko jednej interakcji pętli, aby określić MSB. Ponadto istnieją 2 n - 2 liczby całkowite zaczynające się od 01 , wymagające 2 iteracji, 2 n - 3 liczby całkowite zaczynające się od 001 , wymagające 3 iteracji i tak dalej.
Jeśli zsumujemy wszystkie wymagane iteracje dla wszystkich możliwych liczb całkowitych i podzielimy je przez 2 n , całkowitą liczbę liczb całkowitych, otrzymamy średnią liczbę iteracji potrzebnych do wyznaczenia MSB dla n- bitowych liczb całkowitych:
(1 * 2 n - 1 + 2 * 2 n - 2 + 3 * 2 n - 3 + ... + n) / 2 n
Ta seria średnich iteracji jest w rzeczywistości zbieżna i ma granicę 2 dla n do nieskończoności
Tak więc naiwny algorytm od lewej do prawej ma w rzeczywistości zamortyzowaną stałą złożoność czasową O (1) dla dowolnej liczby bitów.
źródło
c99dał nam
log2
. Eliminuje to potrzebę stosowania wszystkich specjalnychlog2
implementacji sosów, które widzisz na tej stronie. Możesz użyćlog2
implementacji standardu w następujący sposób:n
Od0UL
potrzeb być chronione przed, jak również, ponieważ:Pisałem przykład z tej kontroli, które arbitralnie określa
Index
sięULONG_MAX
tutaj: https://ideone.com/u26vsiPlik studio wizualnenastępstwem jedynej odpowiedzi w gcc ephemienta jest:
Dokumentacja dla
_BitScanReverse
stanówIndex
to:W praktyce Odkryłam, że jeśli
n
to0UL
, żeIndex
jest ustawiona0UL
tak, jak byłoby to dlan
o1UL
. Ale jedyną rzeczą, zagwarantowane w dokumentacji w przypadkun
o0UL
to, że powrót jest:Tak więc, podobnie jak w przypadku preferowanej
log2
implementacji powyżej, zwrot należyIndex
w tym przypadku sprawdzić ustawiając na oflagowaną wartość. Ponownie napisałem przykład użyciaULONG_MAX
tej wartości flagi tutaj: http://rextester.com/GCU61409źródło
_BitScanReverse
zwraca 0 tylko wtedy, gdy dane wejściowe to0
. Jest to podobne doBSR
instrukcji x86 , która ustawia ZF tylko na podstawie wejścia, a nie wyjścia. Ciekawe, że MS określa dokumenty jako pozostające w stanieindex
nieustawionym, gdy nie1
znaleziono żadnego bitu; który również pasuje do zachowania asm x86 programubsr
. (AMD dokumentuje to jako pozostawienie niezmienionego rejestru docelowego na src = 0, ale Intel po prostu podaje niezdefiniowane dane wyjściowe, mimo że ich procesory implementują zachowanie niezmienione). Jest to w przeciwieństwie do x86lzcnt
, co oznacza,32
że nie znaleziono._BitScanReverse
używa indeksowania od zera, więc jeślin
wynosi 1, to indeks ustawionego bitu wynosi w rzeczywistości 0. Niestety, jak mówisz, jeślin
wynosi 0, to na wyjściu również jest 0 :( Oznacza to, że nie ma sposobu, aby użyć powrotu do rozróżnićn
1 lub 0. Właśnie to próbowałem przekazać. Czy uważasz, że jest lepszy sposób, aby to powiedzieć?Index
. To nie jest powrót wartość. Zwraca wartość logiczną, która jest fałszywa, jeśli wartość wejściowa wynosiła zero (i dlatego Index jest przekazywany przez odwołanie, a nie zwracany normalnie). godbolt.org/g/gQKJdE . I sprawdziłem: pomimo sformułowania dokumentów MS,_BitScanReverse
nie pozostawia indeksu nieustawionegon==0
: po prostu dostajesz jakąkolwiek wartość w rejestrze, którego akurat używał. (Który w twoim przypadku był prawdopodobnie tym samym rejestrem, którego używałIndex
później, co prowadzi do zobaczenia a0
).log2
od C99.Pomyśl o operatorach bitowych.
Za pierwszym razem nie zrozumiałem pytania. Powinieneś utworzyć int z ustawionym najbardziej lewym bitem (pozostałe zero). Zakładając, że cmp jest ustawiony na tę wartość:
źródło
8
Powinno byćCHAR_BIT
. Jest to bardzo mało prawdopodobne, aby był to najszybszy sposób, ponieważ przy wyjściu z pętli wystąpi błędne przewidywanie gałęzi, chyba że jest to używane wielokrotnie z tym samym wejściem. Ponadto w przypadku małych wejść (dużo zer) musi dużo zapętlić. Jest to sposób zastępczy, którego można użyć jako łatwej do zweryfikowania wersji w teście jednostkowym w celu porównania ze zoptymalizowanymi wersjami.Rozwijając benchmark Josha ... można poprawić clz w następujący sposób
Odnośnie asm: zwróć uwagę, że istnieją bsr i bsrl (to jest „długa” wersja). normalny może być nieco szybszy.
źródło
Zwróć uwagę, że to, co próbujesz zrobić, to obliczyć liczbę całkowitą log2 liczby całkowitej,
Zauważ, że możesz próbować przeszukiwać więcej niż 1 bit na raz.
To podejście wykorzystuje wyszukiwanie binarne
Inna metoda wyszukiwania binarnego, być może bardziej czytelna,
A ponieważ zechcesz je przetestować,
źródło
Uwzględnienie tego, ponieważ jest to „jeszcze jedno” podejście, wydaje się różnić od innych już podanych.
zwraca
-1
jeślix==0
, w przeciwnym raziefloor( log2(x))
(maksymalny wynik 31)Zmniejsz problem z 32 do 4 bitów, a następnie użyj tabeli. Może nieeleganckie, ale pragmatyczne.
To jest to, czego używam, gdy nie chcę używać z
__builtin_clz
powodu problemów z przenośnością.Aby uczynić go bardziej zwartym, można zamiast tego użyć pętli do redukcji, dodając 4 do r za każdym razem, maksymalnie 7 iteracji. Lub jakaś hybryda, na przykład (dla 64 bitów): pętla w celu zmniejszenia do 8, test w celu zmniejszenia do 4.
źródło
Woaw, to było wiele odpowiedzi. Nie przepraszam, że odpowiadam na stare pytanie.
Ta odpowiedź jest bardzo podobna do innej odpowiedzi ... no cóż.
źródło
1<<k
jest miłym akcentem. A co z maskami?(1 << (1<<k-1)-1<< (1<<k-1)
? (most optimal
? Porównujesz superlatyw?)&
i&~
.) Możesz zastąpić stałe szesnastkowe takimi jak((type)1<<(1<<k))-1<<(1<<k)
.Kod:
Lub uzyskaj część całkowitą instrukcji FPU FYL2X (Y * Log2 X), ustawiając Y = 1
źródło
double
, co jest prawdopodobnie dobre, jeśli faktycznie przechowuje / przeładowuje zamiast pisania kalambur w inny sposób, np. zmovq
instrukcją, jaką możesz dostać tutaj na x86.[7FFFFFFFFFFFFE00 - 7FFFFFFFFFFFFFFF]
.Inny plakat udostępnił tablicę przeglądową używającą wyszukiwania o szerokości bajtów . Jeśli chcesz uzyskać nieco większą wydajność (kosztem 32 KB pamięci zamiast tylko 256 wpisów wyszukiwania), oto rozwiązanie wykorzystujące 15-bitową tabelę wyszukiwania , w C # 7 dla .NET .
Ciekawą częścią jest inicjalizacja tabeli. Ponieważ jest to stosunkowo mały blok, którego potrzebujemy na cały czas trwania procesu, przydzielam do tego niezarządzaną pamięć przy użyciu
Marshal.AllocHGlobal
. Jak widać, dla maksymalnej wydajności cały przykład jest napisany jako natywny:Tabela wymaga jednorazowej inicjalizacji za pomocą powyższego kodu. Jest tylko do odczytu, więc pojedynczą kopię globalną można udostępniać w celu jednoczesnego dostępu. Dzięki tej tabeli możesz szybko sprawdzić logarytm liczb całkowitych 2 , którego tutaj szukamy, dla wszystkich różnych szerokości całkowitych (8, 16, 32 i 64 bity).
Zwróć uwagę, że wpis w tablicy dla
0
, jedyna liczba całkowita, dla której pojęcie „najwyższego ustawionego bitu” jest niezdefiniowane, otrzymuje wartość-1
. To rozróżnienie jest konieczne do właściwej obsługi górnych słów o wartości 0 w poniższym kodzie. Bez dalszych ceregieli, oto kod dla każdego z różnych prymitywów całkowitych:wersja ulong (64-bitowa)
Wersja uint (32-bitowa)
Różne przeciążenia dla powyższych
Jest to kompletne, działające rozwiązanie, które zapewnia najlepszą wydajność w .NET 4.7.2 dla wielu alternatyw, które porównałem ze specjalistyczną wiązką do testów wydajności. Niektóre z nich są wymienione poniżej. Parametrami testu była jednorodna gęstość wszystkich 65-bitowych pozycji, tj. 0 ... 31/63 plus wartość
0
(co daje wynik -1). Bity poniżej docelowej pozycji indeksu zostały wypełnione losowo. Testy obejmowały tylko x64 , tryb wydania, z włączoną optymalizacją JIT.To koniec mojej formalnej odpowiedzi tutaj; Poniżej znajduje się kilka przypadkowych uwag i linków do kodu źródłowego dla alternatywnych kandydatów do testów, związanych z testami, które przeprowadziłem w celu sprawdzenia wydajności i poprawności powyższego kodu.
Wersja podana powyżej, oznaczona jako Tab16A, była konsekwentnym zwycięzcą w wielu przebiegach. Tych różnych kandydatów w formie aktywnej pracy / od podstaw można znaleźć tutaj , tutaj i tutaj .
Godne uwagi jest to, że straszna wydajność
ntdll.dll!RtlFindMostSignificantBit
via P / Invoke:To naprawdę szkoda, ponieważ oto cała rzeczywista funkcja:
Nie mogę sobie wyobrazić słabej wydajności wynikającej z tych pięciu linii, więc należy winić kary za zarządzane / natywne przejście. Byłem również zaskoczony, że testy naprawdę faworyzowały 32KB (i 64KB)
short
(16-bitowe) tablice bezpośredniego wyszukiwania w porównaniu z 128-bajtowymi (i 256-bajtowymi)byte
(8-bitowymi) tablicami wyszukiwania. Wydawało mi się, że poniższe elementy będą bardziej konkurencyjne w przypadku wyszukiwania 16-bitowego, ale ta ostatnia konsekwentnie przewyższała to:Ostatnią rzeczą, na którą zwróciłem uwagę, było to, że byłem zszokowany, że moja metoda deBruijn nie wypadła lepiej. To jest metoda, której wcześniej używałem powszechnie:
Dużo dyskutuje się o tym, jak doskonałe i świetne metody deBruijna w tym pytaniu SO i zwykle się z tym zgadzam. Spekuluję, że chociaż zarówno metoda deBruijn, jak i metoda tabeli bezpośredniego wyszukiwania (które okazały się najszybsze), obie muszą przeszukiwać tabelę i obie mają bardzo minimalne rozgałęzienia, tylko deBruijn ma 64-bitową operację mnożenia. Przetestowałem tylko
IndexOfMSB
funkcje tutaj - nie deBruijn -IndexOfLSB
ale spodziewam się, że ten drugi będzie miał znacznie większe szanse, ponieważ ma o wiele mniej operacji (patrz powyżej) i prawdopodobnie nadal będę go używać w LSB.źródło
Moja skromna metoda jest bardzo prosta:
MSB (x) = INT [Log (x) / Log (2)]
Tłumaczenie: MSB x jest wartością całkowitą (logarytm z podstawy x podzielony przez logarytm z podstawy 2).
Można to łatwo i szybko dostosować do dowolnego języka programowania. Wypróbuj na swoim kalkulatorze i przekonaj się, że to działa.
źródło
int(math.log((1 << 48) - 1) / math.log(2))
to 48.Oto szybkie rozwiązanie dla C, które działa w GCC i Clang ; gotowy do skopiowania i wklejenia.
I trochę ulepszona wersja dla C ++ .
Kod zakłada, że
value
tak nie będzie0
. Jeśli chcesz zezwolić na 0, musisz to zmodyfikować.źródło
Zakładam, że twoje pytanie dotyczy liczby całkowitej (zwanej poniżej v), a nie liczby całkowitej bez znaku.
Jeśli chcesz, aby działało bez uwzględnienia znaku, możesz dodać dodatkowe 'v << = 1;' przed pętlą (i odpowiednio zmień wartość r na 30). Daj mi znać, jeśli o czymś zapomniałem. Nie testowałem tego, ale powinno działać dobrze.
źródło
v <<= 1
jest niezdefiniowanym zachowaniem (UB), gdyv < 0
.0x8000000
, może masz na myśli dodatkowe 0.