c++ - 计算 64 位整数中的尾随零位是固有的吗？

Question

这是对之前关于位操作的一些问题的跟进。我修改了 this site 中的代码枚举设置了 N 位中的 K 位的字符串(x 是设置了 K 位的当前 int64_t，并且在此代码的末尾是按字典顺序设置的下一个设置了 K 位的整数):

int64_t b, t, c, m, r,z;
b = x & -x;
t = x + b;
c = x^t;
// was m = (c >> 2)/b per link
z = __builtin_ctz(x);
m = c >> 2+z;
x = t|m;

只要最低有效位在 x 的低 DWORD 中，使用 __builtin_ctz() 的修改就可以正常工作，但如果不是，它就会完全中断。这可以通过以下代码看出:

for(int i=0; i<64; i++) printf("i=%i, ctz=%i\n", i, __builtin_ctz(1UL << i));

为 GCC 版本 4.4.7 打印:

i=0, ctz=0
i=1, ctz=1
i=2, ctz=2

...

i=30, ctz=30
i=31, ctz=31
i=32, ctz=0

或者对于 icc 版本 14.0.0 类似的东西(除了 i>32 给出随机结果，而不是零)。在这两种情况下都可以使用除法而不是按 2+z 移动，但在我的 Sandy Bridge Xeon 上它慢了大约 5 倍。对于 64 位，是否还有我应该使用的其他内在函数，或者我是否必须执行一些内联​​汇编程序？

谢谢!

Answer 1

__builtin_ctz采用 unsigned int 类型的参数，在大多数平台上为 32 位。

如果long是64位的，可以用__builtin_ctzl这需要 unsigned long .或者你可以使用 __builtin_ctzll这需要 unsigned long long - 在这种情况下你应该使用 1ULL << i而不是 1UL << i .