Implementación de __builtin_clz

Question

¿Cuál es la implementación de GCC (4.6+) __builtin_clz? ¿Corresponde a alguna instrucción de CPU en Intel x86_64 (AVX)?

Answer 1

Se debe traducir a una instrucción Bit Scan Reverse y un restar. El BSR proporciona el índice del 1 principal, y luego puede restarlo del tamaño de palabra para obtener el número de ceros a la izquierda.

Editar: si su CPU es compatible con LZCNT (conteo de cero principal), entonces eso probablemente también lo haga, pero no todos los chips x86-64 tienen esa instrucción.

Answer 2

Sí, corresponde a la instrucción de la CPU BSR (bit scan reverse).

Aquí hay un código de ejemplo que puede ayudarle 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í, y no.

CLZ (conteo de cero inicial) y BSR (cambio de bit de reversa) están relacionados pero son diferentes. CLZ es igual (tipo ancho de bit menos uno) - BSR. CTZ (conteo de origen cero), también conocido como FFS (buscar primer conjunto) es lo mismo que BSF (avance de exploración de bit)

¡Tenga en cuenta que todos estos están indefinidos cuando se opera en cero!

Respondiendo a su pregunta, la mayoría de las veces en x86 y x86_64, __builtin_clz genera una operación BSR restada de 31 (o cualquiera que sea el ancho de su tipo), y __builting_ctz genera una operación BSF.

Si quiere saber qué ensamblador GCC está generando, la mejor manera de saber es ver. La bandera -S tendrá salida de gcc el ensamblador que genera para la entrada dada:

gcc -S -o test.S test.c

Considere:

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

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

En x86 para gcc clz (-O2) genera:

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

y para ctz:

bsfl %edi, %eax 
ret 

Tenga en cuenta que si usted realmente quiere BSR, y no clz, es necesario hacer 31 - clz (. De enteros de 32 bits) Esto explica la XOR 31, cuando x XOR 31 == 31 - x (esto identidad sólo es cierto para los números de la de 2^y - 1) por lo tanto:

num = __builtin_clz(num)^31; 

produce

bsrl %edi, %eax 
ret