Znajdź pierwszy zestaw

W oprogramowaniu komputerowym i sprzęcie komputerowym znajdź pierwszy zestaw ( ffs ) lub znajdź pierwszy to operacja bitowa , która przy danym słowie maszynowym bez znaku wyznacza indeks lub pozycję najmniej znaczącego zestawu bitów na jeden w słowie licząc od najmniej znaczącego bitu pozycja. Niemal równoważną operacją jest zliczanie końcowych zer ( ctz ) lub liczba końcowych zer ( ntz ), która zlicza liczbę bitów zerowych następujących po najmniej znaczącym bicie. Operacją uzupełniającą, która znajduje indeks lub pozycję najbardziej znaczącego ustawionego bitu, jest logarytm o podstawie 2 , tak zwany, ponieważ oblicza logarytm binarny ⌊log 2 (x)⌋ . Jest to ściśle związane z liczeniem zer wiodących ( clz ) lub liczbą zer wiodących ( nlz ), która zlicza liczbę bitów zerowych poprzedzających najbardziej znaczący bit. Istnieją dwa popularne warianty znajdowania pierwszego zestawu, POSIX , która rozpoczyna indeksowanie bitów od 1, tutaj oznaczona jako ffs, oraz wariant, który rozpoczyna indeksowanie bitów od zera, co jest równoważne z ctz i dlatego będzie nazywane tą nazwą.

Większość nowoczesnych architektur zestawów instrukcji procesora zapewnia jedną lub więcej z nich jako operatorów sprzętowych; emulacja oprogramowania jest zwykle zapewniana dla tych, które nie są dostępne, albo jako elementy wewnętrzne kompilatora, albo w bibliotekach systemowych.

Przykłady

Biorąc pod uwagę następujące 32-bitowe słowo:

0000 0000 0000 0000 1000 0000 0000 1000

Operacja zliczania zer na końcu zwróci 3, podczas gdy operacja zliczania zer na początku zwraca 16. Operacja zliczania zer na początku zależy od rozmiaru słowa: gdyby to 32-bitowe słowo zostało obcięte do słowa 16-bitowego, zliczanie zer na początku zwróciłoby zero . Operacja znajdowania pierwszego zestawu zwróci 4, wskazując czwartą pozycję od prawej. Podstawa logarytmu 2 to 15.

Podobnie, biorąc pod uwagę następujące 32-bitowe słowo, bitowa negacja powyższego słowa:

1111 1111 1111 1111 0111 1111 1111 0111

Operacja liczenia kończących jedynek zwróciłaby 3, operacja liczenia wiodących jedynek zwróciłaby 16, a operacja znalezienia pierwszego zera ffz zwróciłaby 4.

Jeśli słowo ma wartość zero (brak ustawionych bitów), zarówno zliczanie zer wiodących, jak i zer końcowych zwracają liczbę bitów w słowie, podczas gdy ffs zwraca zero. Implementacje find first set zarówno o podstawie logarytmicznej 2, jak i opartej na zerach generalnie zwracają niezdefiniowany wynik dla słowa zerowego.

Wsparcie sprzętowe

Wiele architektur zawiera instrukcje szybkiego wykonywania operacji znajdowania pierwszego zestawu i/lub powiązanych operacji, wymienionych poniżej. Najczęstszą operacją jest zliczanie wiodących zer (clz), prawdopodobnie dlatego, że wszystkie inne operacje mogą być efektywnie realizowane w tym zakresie (zobacz Właściwości i relacje ).

Platforma Mnemoniczny Nazwa Szerokości operandów Opis Na wniosek do 0

ARM ( architektura ARMv5T i nowsze ) z wyjątkiem Cortex-M0/M0+/M1/M23 		klz Policz wiodące zera 32 klz 32
ARM ( architektura ARMv8-A ) klz Policz wiodące zera 32, 64 klz Szerokość argumentu
AVR32 klz Policz wiodące zera 32 klz 32
DEC alfa ctlz Policz wiodące zera 64 klz 64
cttz Policz końcowe zera 64 ctz 64
Intel 80386 i nowsze bsf Skanowanie bitów do przodu 16, 32, 64 ctz Nieokreślony; ustawia flagę zerową
bsr Skanowanie bitów do tyłu 16, 32, 64 Baza dziennika 2 Nieokreślony; ustawia flagę zerową
x86 obsługujący BMI1 lub ABM lzcnt Policz wiodące zera 16, 32, 64 klz szerokość operandu; zestawy niosą flagę
x86 obsługujący BMI1 tzcnt Policz końcowe zera 16, 32, 64 ctz szerokość operandu; zestawy niosą flagę
Itanium klz Policz wiodące zera 64 klz 64
MIPS32/MIPS64 klz Policz wiodące zera w programie Word 32, 64 klz Szerokość argumentu
klo Policz wiodące jedynki w programie Word 32, 64 klo Szerokość argumentu
Motorola 68020 i nowsze bfffo Znajdź pierwszy w Bit Field Arbitralny Baza dziennika 2 Przesunięcie pola + szerokość pola
PDP-10 jffo Skocz, jeśli Znajdź pierwszy 36 ctz 0; bez operacji
ZASILANIE / PowerPC / Power ISA cntlz/cntlzw/cntlzd Policz wiodące zera 32, 64 klz Szerokość argumentu
Power ISA 3.0 i nowsze cnttzw/cnttzd Policz końcowe zera 32, 64 ctz Szerokość argumentu
RISC-V (rozszerzenie „B”) (wersja robocza) klz Policz wiodące zera 32, 64 klz Szerokość argumentu
ctz Policz końcowe zera 32, 64 ctz Szerokość argumentu
SPARC Oracle Architecture 2011 i nowsze lzcnt (synonim: lzd) Wiodąca liczba zerowa 64 klz 64
VAX ffs Znajdź pierwszy zestaw 0–32 ctz szerokość operandu; ustawia flagę zerową
IBM z/Architektura biczować Znajdź skrajnie lewy 64 klz 64
vclz Liczba wiodących zer wektorów 8, 16, 32, 64 klz Szerokość argumentu
vctz Zliczanie wektorów końcowych zer 8, 16, 32, 64 ctz Szerokość argumentu

Na niektórych platformach Alpha CTLZ i CTTZ są emulowane programowo.

Obsługa narzędzi i bibliotek

Wielu dostawców kompilatorów i bibliotek dostarcza wewnętrzne elementy kompilatora lub funkcje biblioteczne do wykonywania operacji znajdowania pierwszego zestawu i / lub powiązanych operacji, które często są implementowane zgodnie z powyższymi instrukcjami sprzętowymi:

Narzędzie/biblioteka Nazwa Typ Rodzaje wejść Notatki Na wniosek do 0


POSIX .1 libc 4.3BSD libc OS X 10.3 libc 		ffs Funkcja biblioteki int Zawiera glibc . POSIX nie dostarcza komplementarnej bazy logów 2 / clz. 0

FreeBSD 5.3 libc OS X 10.4 libc

ffsl fls flsl 		Funkcja biblioteki
int, długi 		fls("znajdź ostatni zestaw") oblicza (podstawa logarytmu 2) + 1. 0
FreeBSD 7.1 libc
ffsll flsll 		Funkcja biblioteki długo długo 0

GCC 3.4.0 Clang 5.x

__wbudowany_ffs[l,ll,imax] __wbudowany_clz[l,ll,imax] __wbudowany_ctz[l,ll,imax]
Wbudowane funkcje


unsigned int, unsigned long, unsigned long long, uintmax_t 		Dokumentacja GCC uwzględnia wynik niezdefiniowany clz i ctz na 0. 0 (ffs)
Visual Studio 2005
_BitScanForward _BitScanReverse 		Elementy wewnętrzne kompilatora
długi bez znaku, bez znaku __int64 		Oddzielna wartość zwracana, aby wskazać wejście zerowe Nieokreślony
Visual Studio 2008 __lzcnt Wewnętrzny kompilator

bez znaku krótki, bez znaku int, bez znaku __int64 		Opiera się na sprzętowej obsłudze instrukcji lzcnt wprowadzonej w BMI1 lub ABM . Szerokość argumentu
Visual Studio 2012 _arm_clz Wewnętrzny kompilator bez znaku wewn Opiera się na sprzętowej obsłudze instrukcji clz wprowadzonej w architekturze ARMv5T i późniejszych . ?
Kompilator Intel C++
_bit_scan_forward _bit_scan_reverse 		Elementy wewnętrzne kompilatora int Nieokreślony
NVIDIA CUDA __clz Funkcje 32-bitowy, 64-bitowy Kompiluje się do mniejszej liczby instrukcji na kartach z serii GeForce 400 32
__ffs 0
LLVM
llvm.ctlz.* llvm.cttz.* 		Wewnętrzny 8, 16, 32, 64, 256 Język asemblera LLVM Szerokość operandu, jeśli drugi argument wynosi 0; nieokreślony inaczej
GHC 7.10 (podstawa 4.8), w Data.Bits [ potrzebne źródło ]
countLeadingZeroscountTrailingZeros _ 		Funkcja biblioteki Bity skończone b => b Język programowania Haskell Szerokość argumentu
Standardowa biblioteka C++20 , w nagłówku <bit>


bit_ceil bit_floor bit_width licznik_zero licznik_jeden licznik_zero licznik_jeden 		Funkcja biblioteki



unsigned char, unsigned short, unsigned int, unsigned long, unsigned long long

Właściwości i relacje

0 Jeśli bity są oznaczone zaczynając od 1 (zgodnie z konwencją stosowaną w tym artykule), policz końcowe zera i operacje znajdowania pierwszego zbioru są powiązane przez ctz( x ) = ffs ( x ) − 1 (z wyjątkiem sytuacji, gdy wejście jest równe zero). Jeśli bity są oznaczone zaczynając od , to policz końcowe zera i znajdź pierwszy zestaw są dokładnie równoważnymi operacjami. Biorąc pod uwagę w bitów na słowo, log 2 można łatwo obliczyć z clz i odwrotnie, log 2 ( x ) = w − 1 − clz ( x ) .

Jak pokazano w powyższym przykładzie, operacje znajdowania pierwszego zera, liczenia wiodących jedynek i liczenia końcowych jedynek można zaimplementować poprzez zanegowanie danych wejściowych i użycie znajdowania pierwszego zestawu, liczenia wiodących zer i liczenia końcowych zer. Odwrotnie jest również prawdą.

Na platformach z wydajną operacją log 2 , takich jak M68000, ctz można obliczyć w następujący sposób:

ctz( x ) = log 2 ( x & −x )

gdzie & oznacza bitowe AND, a −x oznacza dopełnienie do dwóch z x . Wyrażenie x & −x czyści wszystkie oprócz najmniej znaczącego 1 bitu, tak że najbardziej i najmniej znaczący 1 bit są takie same.

Na platformach z wydajną operacją liczenia wiodących zer, takich jak ARM i PowerPC, ffs można obliczyć za pomocą:

ffs( x ) = w - clz( x & -x ) .

I odwrotnie, na maszynach bez operatorów log 2 lub clz , clz można obliczyć za pomocą ctz , aczkolwiek nieefektywnie:

clz = w − ctz(2 ⌈log 2 ( x )⌉ ) (co zależy od ctz zwracającego w dla wejścia zerowego)

Na platformach z wydajną operacją wagi Hamminga (liczba populacji), takich jak POPC firmy SPARC lub ONES firmy Blackfin , dostępne są:

ctz( x ) = popcount(( x & −x ) − 1) , lub ctz( x ) = popcount(~( x | −x )) ,
ffs( x ) = popcount( x ^ ~− x )
clz = 32 − popcount(2 ⌈log 2 ( x )⌉ − 1)

gdzie ^ oznacza bitowe wyłączne-OR, | oznacza bitowe OR, a ~ oznacza bitową negację.

Problem odwrotny (biorąc pod uwagę i , wyprodukuj x takie, że ctz( x ) = i ) można obliczyć z przesunięciem w lewo ( 1 << i ).

Znajdź pierwszy zestaw i powiązane operacje można rozszerzyć na dowolnie duże tablice bitów w prosty sposób, zaczynając od jednego końca i przechodząc do słowa, które nie jest całkowicie zerowe (dla ffs , ctz , clz ) lub nie jest całkowicie jedynkowe (dla ffz , clo , cto ) zostało napotkane. Struktura danych drzewa, która rekurencyjnie używa map bitowych do śledzenia, które słowa są niezerowe, może to przyspieszyć.

Emulacja oprogramowania

Większość procesorów pochodzących z późnych lat 80. i późniejszych ma operatory bitowe dla ffs lub ich odpowiedników, ale kilka nowoczesnych, takich jak niektóre z serii ARM-Mx, nie. Zamiast operatorów sprzętowych dla ffs, clz i ctz, oprogramowanie może emulować je za pomocą przesunięć, operatorów arytmetycznych liczb całkowitych i operatorów bitowych. Istnieje kilka podejść w zależności od architektury procesora i, w mniejszym stopniu, semantyki języka programowania i jakości generowania kodu kompilatora. Podejścia te można luźno opisać jako przeszukiwanie liniowe , przeszukiwanie binarne , przeszukiwanie + przeszukiwanie tabeli, mnożenie de Bruijna, konwersja zmiennoprzecinkowa/ekstrakcja wykładników oraz metody operatorów bitowych (bez rozgałęzień). Istnieją kompromisy między czasem wykonania a przestrzenią dyskową, a także przenośnością i wydajnością.

Emulacje oprogramowania są zwykle deterministyczne. Zwracają określony wynik dla wszystkich wartości wejściowych; w szczególności wynik dla wprowadzenia wszystkich bitów zerowych wynosi zwykle 0 dla ffs, a długość bitowa operandu dla innych operacji.

Jeśli ktoś ma sprzętowy clz lub odpowiednik, ctz można wydajnie obliczyć za pomocą operacji bitowych, ale sytuacja odwrotna nie jest prawdziwa: clz nie jest wydajne do obliczeń pod nieobecność operatora sprzętowego.

2 przyp

Funkcja 2 ⌈log 2 (x)⌉ (zaokrąglenie w górę do najbliższej potęgi dwójki) przy użyciu przesunięć i bitowych OR nie jest wydajna do obliczenia, jak w tym 32-bitowym przykładzie, a jeszcze bardziej nieefektywna, jeśli mamy 64-bitowy lub 128-bitowy -bitowy argument: 

 funkcja  pow2(x):  jeśli  x = 0 zwróć  nieważne  //  niepoprawne  jest implementacja zdefiniowana (nie w [0,63]) x ← x - 1  dla każdego  y  w  {1, 2, 4, 8, 16}: x ← x | (x >> y)   zwróć  x + 1

FFS

Ponieważ ffs = ctz + 1 (POSIX) lub ffs = ctz (inne implementacje), można zastosować odpowiednie algorytmy dla ctz, z możliwym ostatnim krokiem polegającym na dodaniu 1 do wyniku i zwróceniu 0 zamiast długości operandu dla wprowadzenia wszystkie bity zerowe.

CTZ

Algorytm kanoniczny to pętla licząca zera, zaczynając od LSB, aż do napotkania 1-bitowego:

 funkcja  ctz1 (x)  jeśli  x = 0  powrót  w t ← 1 r ← 0  natomiast  (x & t) = 0 t ← t << 1 r ← r + 1  powrót  r

Algorytm ten wykonuje operacje i czas O(n) i jest niepraktyczny w praktyce ze względu na dużą liczbę rozgałęzień warunkowych.

Tabela przeglądowa może wyeliminować większość gałęzi:

         table[0..2  n  -1] = ctz(i)  for  i  in  0..2  n  -1  funkcja  ctz2 (x)  if  x = 0  return  w r ← 0  pętla  if  (x & (2  n  -1)) ≠ 0  powrót  r + tablica[x & (2  n  -1)] x ← x >> n r ← r + n

Parametr n jest stały (zwykle 8) i reprezentuje kompromis czasowo-przestrzenny . Pętla może być również całkowicie rozwinięta . Ale jako wyszukiwanie liniowe, to podejście jest nadal O(n) w liczbie bitów w argumencie.

wyszukiwania binarnego wymaga logarytmicznej liczby operacji i rozgałęzień, tak jak w tej 32-bitowej wersji: Ten algorytm może być również wspomagany przez tabelę, zastępując trzy dolne instrukcje „if” tablicą wyszukiwania z 256 wpisami przy użyciu pierwszego nie -zero bajt napotkany jako indeks. 

 funkcja  ctz3 (x)  if  x = 0  return  32 n ← 0  if  (x & 0x0000FFFF) = 0: n ← n + 16, x ← x >> 16  if  (x & 0x000000FF) = 0: n ← n + 8, x ← x >> 8  jeśli  (x & 0x0000000F) = 0: n ← n + 4, x ← x >> 4  jeśli  (x & 0x00000003) = 0: n ← n + 2, x ← x >> 2  jeśli  ( x & 0x00000001) = 0: n ← n + 1  powrót  n

Jeśli sprzęt ma operatora clz, najbardziej efektywnym podejściem do obliczania ctz jest zatem:

 funkcja  ctz4 (x) x &= -x  powrót  w - (clz(x) + 1)

Algorytm dla 32-bitowego ctz wykorzystuje sekwencje de Bruijna do skonstruowania minimalnej idealnej funkcji mieszającej , która eliminuje wszystkie gałęzie. Algorytm ten zakłada, że ​​wynik mnożenia jest obcinany do 32 bitów. 

 0  dla  i  od  do  31: table[ ( 0x077CB531 * ( 1 << i ) ) >> 27 ] ← i // table [0..31] zainicjowana  funkcja  ctz5 (x)  return  table[((x & -x) * 0x077CB531) >> 27]

Wyrażenie (x & -x) ponownie izoluje najmniej znaczący 1 bit. Są wtedy tylko 32 możliwe słowa, które mnożenie bez znaku i przesunięcie haszują na właściwą pozycję w tabeli. (Ten algorytm nie obsługuje wejścia zerowego).

CLZ

Algorytm kanoniczny sprawdza po jednym bicie, zaczynając od MSB, aż do znalezienia niezerowego bitu, jak pokazano w tym przykładzie. Wykonuje się w czasie O(n), gdzie n jest długością bitową operandu i nie jest praktycznym algorytmem do ogólnego użytku.

 funkcja  clz1 (x)  jeśli  x = 0  powrót  w t ← 1 << (w - 1) r ← 0  natomiast  (x & t) = 0 t ← t >> 1 r ← r + 1  powrót  r

Udoskonalenie poprzedniego podejścia z pętlą sprawdza jednocześnie osiem bitów, a następnie wykorzystuje tablicę wyszukiwania 256 (28 ) wpisów dla pierwszego niezerowego bajtu. To podejście jest jednak nadal O(n) w czasie wykonania. 

 funkcja  clz2 (x)  if  x = 0  powrót  w t ← 0xff << (w - 8) r ← 0  while  (x & t) = 0 t ← t >> 8 r ← r + 8  powrót  r + table[x >> (w - 8 - r)]

Wyszukiwanie binarne może skrócić czas wykonania do O(log 2 n): 

 funkcja  clz3 (x)  if  x = 0  return  32 n ← 0  if  (x & 0xFFFF0000) = 0: n ← n + 16, x ← x << 16  if  (x & 0xFF000000) = 0: n ← n + 8, x ← x << 8  jeśli  (x & 0xF0000000) = 0: n ← n + 4, x ← x << 4  jeśli  (x & 0xC0000000) = 0: n ← n + 2, x ← x << 2  jeśli  ( x & 0x80000000) = 0: n ← n + 1  powrót  n

Najszybsze przenośne podejście do symulacji clz to połączenie wyszukiwania binarnego i wyszukiwania w tablicy: 8-bitowe wyszukiwanie w tablicy (2 8 = 256 1-bajtowych wpisów) może zastąpić 3 dolne gałęzie w wyszukiwaniu binarnym. Operandy 64-bitowe wymagają dodatkowej gałęzi. Można użyć wyszukiwania o większej szerokości, ale maksymalny praktyczny rozmiar tabeli jest ograniczony rozmiarem pamięci podręcznej danych L1 na nowoczesnych procesorach, która dla wielu wynosi 32 KB. Zapisywanie gałęzi jest więcej niż równoważone opóźnieniem braku pamięci podręcznej L1 .

Algorytm podobny do mnożenia de Bruijna dla CTZ działa dla CLZ, ale zamiast izolować najbardziej znaczący bit, zaokrągla w górę do najbliższej liczby całkowitej postaci 2 n -1 za pomocą przesunięć i bitowych OR: 

 tabela[0..31] = {0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15 , 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31}  funkcja  clz4 (x)  dla każdego  y  w  {1, 2, 4, 8, 16}: x ← x | (x >> y)   zwrotów  [((x * 0x07C4ACDD) >> 27) % 32]

W przypadku procesorów z głębokimi potokami, takich jak procesory Prescott i późniejsze procesory Intela, szybsze może być zastąpienie rozgałęzień przez bitowe operatory AND i OR (mimo że wymaganych jest o wiele więcej instrukcji), aby uniknąć opróżniania potoków w przypadku błędnie przewidywanych rozgałęzień (a tego typu rozgałęzienia są z natury nieobliczalny):

 funkcja  clz5 (x) r = (x > 0xFFFF) << 4; x >>= r;  q = (x > 0xFF ) << 3;  x >>= q;  r |= q;  q = (x > 0xF ) << 2;  x >>= q;  r |= q;  q = (x > 0x3 ) << 1;  x >>= q;  r |= q;  r |= (x >> 1);   powrót  r;

Na platformach, które zapewniają sprzętową konwersję liczb całkowitych na zmiennoprzecinkowe, pole wykładnika można wyodrębnić i odjąć od stałej, aby obliczyć liczbę wiodących zer. Konieczne są poprawki uwzględniające błędy zaokrągleń. Konwersja zmiennoprzecinkowa może mieć znaczne opóźnienie. Ta metoda jest wysoce nieprzenośna i zwykle nie jest zalecana.

  
 
        

    
  
  
        
   intx  ;  _  int  r  ;  związek  {  unsigned  int  u  [  2  ];  podwójne  d  ;  }  t  ;  t  .  u  [  LE  ]  =  0x43300000  ;  // LE wynosi 1 dla little-endian  t  .  ty  [  !  LE  ]  =  x  ;  t  .  d-  =  4503599627370496,0  ;  r  =  (  t  .  u  [  LE  ]  >>  20  )  -  0x3FF  ;  // log2  r  ++  ;  // CLZ

Aplikacje

Operacja zliczania wiodących zer (clz) może być wykorzystana do wydajnej implementacji normalizacji , która koduje liczbę całkowitą jako m × 2 e , gdzie m ma swój najbardziej znaczący bit na znanej pozycji (takiej jak najwyższa pozycja). To z kolei może być wykorzystane do implementacji dzielenia Newtona-Raphsona , konwersji liczb całkowitych na zmiennoprzecinkowe w oprogramowaniu i innych aplikacjach.

Policz wiodące zera (clz) można użyć do obliczenia 32-bitowego predykatu „x = y” (zero, jeśli prawda, jeden, jeśli fałsz) za pomocą tożsamości clz(x - y) >> 5 , gdzie „>>” jest bez znaku prawe przesunięcie. Może być używany do wykonywania bardziej wyrafinowanych operacji na bitach, takich jak znajdowanie pierwszego ciągu n 1 bitów. Wyrażenie clz(x − y)1 << (16 − clz(x − 1)/2) jest skutecznym wstępnym przypuszczeniem do obliczania pierwiastka kwadratowego z 32-bitowej liczby całkowitej przy użyciu metody Newtona . CLZ może skutecznie wdrożyć pomijanie wartości null , szybką technikę kompresji danych , która koduje liczbę całkowitą jako liczbę początkowych bajtów zerowych wraz z bajtami niezerowymi. Może również skutecznie generować o rozkładzie wykładniczym , biorąc clz jednolicie losowych liczb całkowitych.

Logarytm o podstawie 2 może być użyty do przewidywania, czy mnożenie się przepełni, ponieważ ⌈log 2 (xy)⌉ ≤ ⌈log 2 (x)⌉ + ⌈log 2 (y)⌉ .

Zliczanie wiodących zer i liczenie końcowych zer może być używane razem do implementacji algorytmu wykrywania pętli Gospera, który może znaleźć okres funkcji o skończonym zakresie przy użyciu ograniczonych zasobów.

Binarny algorytm GCD spędza wiele cykli na usuwaniu końcowych zer; można to zastąpić zliczaniem końcowych zer (ctz), po którym następuje przesunięcie. Podobna pętla pojawia się w obliczeniach sekwencji gradu .

Tablica bitów może być wykorzystana do zaimplementowania kolejki priorytetowej . W tym kontekście znajdowanie pierwszego zestawu (ffs) jest przydatne w efektywnym wdrażaniu operacji „pop” lub „pull element o najwyższym priorytecie”. Harmonogram czasu rzeczywistego jądra Linuksa używa do tego celu wewnętrznie metody sched_find_first_bit() .

Operacja zliczania końcowych zer daje proste, optymalne rozwiązanie problemu Wieży Hanoi : krążki są numerowane od zera, a przy ruchu k krążek o numerze ctz( k ) przesuwa się o minimalną możliwą odległość w prawo (zawracając do pozostawione w razie potrzeby). Może również wygenerować kod Graya , biorąc dowolne słowo i przerzucając bit ctz( k ) w kroku k .

Zobacz też

Notatki

Dalsza lektura

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Find_first_set&oldid=1139170019 ”