执行__builtin_clz

Question

GCC(4.6+)的实施是什么__builtin_clz？它是否符合英特尔的某些CPU指令x86_64 (AVX)？

Answer 1

它应转换为位扫描反转指令和减法.BSR给出前导1的索引,然后您可以从单词大小中减去该指数以获得前导零的数量.

编辑:如果你的CPU支持LZCNT(前导零计数),那么这也许可以解决问题,但并非所有x86-64芯片都有该指令.

Answer 2

是的,不.

CLZ(计数前导零)和BSR(位扫描反向)相关但不同.CLZ等于(类型位宽小于1) - BSR.CTZ(计数尾随零),也称为FFS(查找第一组)与BSF(位扫描前向)相同.

请注意,在零操作时,所有这些都是未定义的!

回答你的问题,大多数时候在x86和x86_64上,__ builtin_clz生成从31减去的BSR操作(或者你的类型宽度是什么),并且__builting_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