如何在64位整数中计算末尾的零位？

Question

5

这是在一些以前的有关位操作的问题后的跟进。我修改了该网站上的代码，用于枚举设置了K个N位的字符串（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;

使用__builtin_ctz()进行修改只有在最低位的一比特位于x的低DWORD时才能正常工作，但如果不是，则会完全破坏。可以通过以下代码看到：

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位吗？还是我必须使用一些内联汇编？谢谢！

- Andrew

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- interjay · Accepted Answer

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

如果long为64位，您可以使用__builtin_ctzl来接受unsigned long类型的参数。或者您可以使用__builtin_ctzll来接受unsigned long long类型的参数-在这种情况下，您应该使用1ULL << i代替 1UL << i。