La mise en œuvre de __builtin_clz

Question

Quelle est la mise en œuvre de (4.6+) __builtin_clz de GCC? Est-ce qu'il correspond à une instruction du processeur Intel x86_64 (AVX)?

Answer 1

Il devrait se traduire par un Bit analyse l'instruction de la marche arrière et Soustraire. Le BSR donne l'indice des principaux 1, et vous pouvez soustraire que de la taille de texte pour obtenir le nombre de zéros en tête.

Edit:. Si votre CPU prend en charge LZCNT (leader du comte zéro), qui va probablement faire l'affaire aussi, mais pas tous les x86-64 puces ont cette instruction

Answer 2

Oui et non.

CLZ (comptage zéro de gauche) et BSR (inversion de bits de balayage) sont liés mais différents. CLZ est égal à (type bit largeur inférieure une) - BSR. CTZ (compte de fuite zéro), aussi connu sous le FFS (vers première série) est le même que BSF (de l'avant-scan bit).

Notez que tous ces éléments ne sont pas définies lors de l'utilisation sur le zéro!

En réponse à votre question, la plupart du temps sur x86 et x86_64, __builtin_clz génère opération BSR soustraites du 31 (ou quel que soit votre type largeur), et génère __builting_ctz une opération de BSF.

Si vous voulez savoir ce que l'assembleur GCC génère, la meilleure façon de savoir est de voir. Le drapeau -S aura sortie de l'assembleur gcc il généré pour l'entrée suivant:

gcc -S -o test.S test.c

Considérez:

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

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

x86 pour gcc ClZ (-O2) génère:

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

et ctz:

bsfl    %edi, %eax
ret

Notez que si vous voulez vraiment bsr, et non clz, vous devez faire 31 - clz (. Pour les entiers 32 bits) Ceci explique la XOR 31, comme x XOR 31 == 31 - x (cette identité est seulement vrai pour les numéros du 2 ^ y - 1) donc:

num = __builtin_clz(num) ^ 31;

rendements

bsrl    %edi, %eax
ret