c - __builtin_clz 的实现

Question

GCC (4.6+) 的实现是什么__builtin_clz？它是否对应于 Intel 上的一些 CPU 指令x86_64 (AVX)？

Answer 1

是的，没有。

CLZ（计数前导零）和 BSR（位扫描反转）相关但不同。CLZ 等于（类型位宽减一）- BSR。CTZ（计数尾随零），也称为 FFS（查找第一个集合）与 BSF（位扫描向前）相同。

请注意，在零上操作时，所有这些都是未定义的！

在回答您的问题时，大部分时间在 x86 和 x86_64 上，__builtin_clz 生成从 31（或任何您的类型宽度）中减去的 BSR 操作，而 __builtin_ctz 生成一个 BSF 操作。

如果您想知道 GCC 正在生成什么汇编程序，最好的方法是查看。-S 标志将使 gcc 输出它为给定输入生成的汇编程序：

gcc -S -o test.S test.c

考虑：

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

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

在 x86 上为 clz gcc (-O2) 生成：

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

对于 ctz：

bsfl    %edi, %eax
ret

请注意，如果您真的想要 bsr 而不是 clz，则需要执行 31 - clz（对于 32 位整数）。这解释了 XOR 31，因为 x XOR 31 == 31 - x（此标识仅适用于数字从 2^y - 1) 所以：

num = __builtin_clz(num) ^ 31;

产量

bsrl    %edi, %eax
ret

Answer 2

它应该转换为位扫描反向指令和减法。BSR 给出了前导 1 的索引，然后您可以从字长中减去该索引以获得前导零的数量。

编辑：如果您的 CPU 支持 LZCNT（前导零计数），那么这可能也可以解决问题，但并非所有 x86-64 芯片都有该指令。