Implementacja __builtin_clz

Question

Jaka jest implementacja GCC (4.6+) __builtin_clz? Czy odpowiada niektórym instrukcjom procesora w Intel x86_64 (AVX)?

Answer 1

Należy przetłumaczyć na instrukcję Bit Scan Reverse i odjąć. BSR podaje indeks wiodącego 1, a następnie można go odjąć od rozmiaru słowa, aby uzyskać liczbę zer wiodących.

Edycja: jeśli twój procesor obsługuje LZCNT (Leading Zero Count), to prawdopodobnie zrobi to samo, ale nie wszystkie układy x86-64 mają tę instrukcję.

Answer 2

Tak, odpowiada instrukcji procesora BSR (skanowanie bitowe do tyłu).

Oto przykładowy kod, który może pomóc:

int a=20; //10100 

//trailing zeroes 
cout<<__builtin_ctz(a)<<endl; //gives 2 
cout<<__builtin_ctz(a<<4)<<endl; //gives 6 

//leading zeroes 
cout<<__builtin_clz(a)<<endl; //gives 27 
cout<<__builtin_clz(a>>4)<<endl; //gives 31 

cout<<__builtin_clz(0)<<endl; //gives 32 

Answer 3

Tak i nie.

CLZ (zerem wiodącym zliczającym) i BSR (odwrócony bit-skan) są powiązane, ale różne. CLZ jest równy (wpisz bitową szerokość mniejszą) - BSR. CTZ (zliczanie zliczające zera), znane również jako FFS (pierwszy znaleziony zestaw) jest taki sam, jak z BSF (skanowanie w kierunku bitu do przodu).

Należy pamiętać, że wszystkie te parametry są nieokreślone przy zerowej pracy!

W odpowiedzi na twoje pytanie, przez większość czasu na x86 i x86_64, __builtin_clz generuje operację BSR odejmowaną od 31 (lub niezależnie od szerokości twojego typu), a __builting_ctz generuje operację BSF.

Jeśli chcesz wiedzieć, co generuje GIGA asembler, najlepiej wiedzieć, jak to sprawdzić. Flaga -S będzie miał wyświetlamy GCC asembler to wygenerowany dla danego wejścia:

gcc -S -o test.S test.c

Rozważmy:

unsigned int clz(unsigned int num) { 
    return __builtin_clz(num); 
} 

unsigned int ctz(unsigned int num) { 
    return __builtin_ctz(num); 
} 

On x 86 do CLZ gcc (-O2) generuje:

bsrl %edi, %eax 
xorl $31, %eax 
ret 

i CTZ:

bsfl %edi, %eax 
ret 

Pamiętaj, że jeśli naprawdę chcesz bsr, a nie clz, musisz zrobić 31 - clz (dla 32-bitowych liczb całkowitych). To wyjaśnia XOR 31, jako x XOR 31 == 31 - x (to tożsamość jest prawdziwe tylko dla liczb od od 2^r - 1) Więc:

num = __builtin_clz(num)^31; 

daje

bsrl %edi, %eax 
ret