Durchführung von __builtin_clz

Was die Umsetzung der GCC (4.6+) __builtin_clz? Entspricht es einige CPU-Instruktion auf Intel x86_64 (AVX)?

InformationsquelleAutor der Frage Cartesius00 | 2012-02-19

  1. 16

    Sollte es zu übersetzen, um eine Bit Scan Reverse Unterricht und subtrahieren. Die BSR gibt die index der führenden 1, und dann können Sie subtrahieren, dass aus dem Wort Größe, um die Anzahl der führenden Nullen.

    Edit: wenn deine CPU unterstützt LZCNT (Führende Null an zu Zählen), dann wird das wahrscheinlich den trick tun, auch, aber nicht alle x86-64-chips haben, dass der Unterricht.

    InformationsquelleAutor der Antwort chisophugis

  2. 14

    Ja, und Nein.

    CLZ (count leading zero) und BSR (bit scan reverse) sind verwandt, aber unterschiedlich. CLZ equals (Typ bit Breite weniger) - BSR. CTZ (count trailing zero), auch bekannt als FFS (Erster Satz) ist das gleiche wie BSF (bit scan forward.)

    Beachten Sie, dass alle diese sind nicht definiert, wenn der Betrieb auf null!

    In Antwort auf Ihre Frage, die meisten der Zeit, die auf x86-und x86_64 -, __builtin_clz generiert BSR Betrieb abgezogen 31 (oder was auch immer Ihr Typ Breite ist), und __builting_ctz erzeugt ein ASF-Betrieb.

    Wenn Sie wissen wollen, was assembler von GCC ist die Erzeugung, der beste Weg, um wissen ist zu sehen. Das -S-flag wird gcc Ausgabe der assembler erzeugt es für den gegebenen input:

    gcc -S -o test.S-test.c

    Betrachten:

    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 gcc (-O2) erzeugt:

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

    und für ctz:

    bsfl    %edi, %eax
ret

    Beachten Sie, dass wenn Sie wirklich wollen, bsr, und nicht clz, die Sie tun müssen, 31 - clz (für 32-bit-Ganzzahlen.) Dies erklärt die XOR-31, x XOR 31 == 31 - x (diese Identität gilt nur für zahlen, die aus 2^y - 1) Also:

    num = __builtin_clz(num) ^ 31;

    Erträge

    bsrl    %edi, %eax
ret

    InformationsquelleAutor der Antwort theycallhimart

Schreibe einen Kommentar