Implementazione di __builtin_clz

Question

Qual è l'implementazione di GCC (4.6+) __builtin_clz? Corrisponde a qualche istruzione della CPU su Intel x86_64 (AVX)?

Answer 1

Dovrebbe essere convertito in un'istruzione Bit Scan Reverse e una sottrazione. Il BSR fornisce l'indice del primo 1, e quindi è possibile sottrarre quello dalla dimensione della parola per ottenere il numero di zeri iniziali.

Edit: se la tua CPU supporta LZCNT (Lead Zero Count), probabilmente anche questo trucco, ma non tutti i chip x86-64 hanno quell'istruzione.

Answer 2

Sì, corrisponde all'istruzione CPU BSR (bit scan inverso).

Ecco un esempio di codice che può aiutare a:

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

Sì e no.

CLZ (zero iniziale del conteggio) e BSR (inversione del bit-scan) sono correlati ma diversi. CLZ è uguale a (larghezza del bit di tipo meno uno) - BSR. CTZ (count zero finale), anche noto come FFS (trova il primo set) è lo stesso di BSF (bit-scan forward.)

Si noti che tutti questi valori non sono definiti quando si opera su zero!

In risposta alla tua domanda, la maggior parte delle volte su x86 e x86_64, __builtin_clz genera operazioni BSR sottratte da 31 (o qualunque sia la larghezza del tuo testo), e __builting_ctz genera un'operazione BSF.

Se vuoi sapere che cosa genera l'assemblatore GCC, il modo migliore per sapere è vedere. Il flag -S avrà uscita gcc l'assemblatore è generato per l'input data:

gcc -o -S test.S test.c

consideri:

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

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

On x86 per CLZ gcc (-O2) genera:

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

e CTZ:

012.351.

bsfl %edi, %eax 
ret 

Si noti che se si vuole veramente BSR, e non CLZ, è necessario fare 31 - CLZ (. Per interi a 32 bit) Questo spiega la XOR 31, come x XOR 31 == 31 - x (questo identità è vero solo per i numeri della dal 2^y - 1) Così:

num = __builtin_clz(num)^31; 

cede

bsrl %edi, %eax 
ret