Implementierung von __builtin_clz

Was ist die Implementierung von GCCs (4.6+) __builtin_clz? Entspricht es einer CPU-Anweisung auf Intel x86_64 (AVX)?

Ja und nein.

CLZ (Count Leading Zero) und BSR (Bit-Scan Reverse) sind verwandt, aber unterschiedlich. CLZ ist gleich (Typbitbreite weniger eins) – BSR. CTZ (Count Trailing Zero), auch bekannt als FFS (Find First Set) ist dasselbe wie BSF (Bit-Scan Forward).

Beachten Sie, dass all diese beim Betrieb auf Null undefiniert sind!

Als Antwort auf Ihre Frage generiert __builtin_clz die meiste Zeit auf x86 und x86_64 eine BSR-Operation, die von 31 (oder was auch immer Ihre Typbreite ist) subtrahiert wird, und __builting_ctz generiert eine BSF-Operation.

Wenn Sie wissen wollen, was Assembler GCC generiert, ist der beste Weg, es zu wissen, es zu sehen. Das Flag -S lässt gcc den Assembler ausgeben, den es für die gegebene Eingabe generiert hat:

gcc -S -o test.S test.c

In Betracht ziehen:

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

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

Auf x86 für clz generiert gcc (-O2):

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

und für ctz:

bsfl    %edi, %eax
ret

Beachten Sie, dass Sie, wenn Sie wirklich bsr und nicht clz wollen, 31 – clz (für 32-Bit-Ganzzahlen) ausführen müssen. Dies erklärt das XOR 31 als x XOR 31 == 31 – x (diese Identität gilt nur für Zahlen der von 2^y – 1) Also:

num = __builtin_clz(num) ^ 31;

Erträge

bsrl    %edi, %eax
ret

Es sollte zu a übersetzen Bit-Scan-Umkehrung Anweisung und eine Subtraktion. Der BSR gibt den Index der führenden 1 an, den Sie dann von der Wortgröße subtrahieren können, um die Anzahl der führenden Nullen zu erhalten.

Bearbeiten: Wenn Ihre CPU LZCNT (Leading Zero Count) unterstützt, reicht das wahrscheinlich auch aus, aber nicht alle x86-64-Chips haben diese Anweisung.