Pregunta Implementación de __builtin_clz


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


15
2018-02-19 22:36


origen


Respuestas:


Debería traducirse a un Bit Scan Reverse instrucción 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 cero inicial), entonces probablemente también lo haga, pero no todos los chips x86-64 tienen esa instrucción.


15
2018-02-19 22:41



Si 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 final cero), también conocido como FFS (buscar primer conjunto) es lo mismo que BSF (avance de exploración de bits).

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

En respuesta 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 desea saber qué ensamblador GCC está generando, la mejor manera de saber es ver. El indicador -S tendrá una salida de gcc del ensamblador que generó para la entrada dada:

gcc -S -o test.S test.c

Considerar:

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

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

En x86 para clz gcc (-O2) genera:

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

y para ctz:

bsfl    %edi, %eax
ret

Tenga en cuenta que si realmente quiere bsr, y no clz, necesita hacer 31 - clz (para enteros de 32 bits). Esto explica el XOR 31, como x XOR 31 == 31 - x (esta identidad solo es verdadera para los números) de la 2 ^ y - 1) Entonces:

num = __builtin_clz(num) ^ 31;

rendimientos

bsrl    %edi, %eax
ret

14
2018-01-08 22:54