内部计算64位整数中的尾随零位？

Question

这是关于位操作的一些先前问题的后续跟进.我修改了这个站点的代码来枚举设置了N位的K的字符串(x是设置int64_t了K位的当前值,并且在这段代码的末尾,它是按字典顺序排列的下一个整数,设置了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位其他内在函数,还是我必须做一些内联汇编程序？

谢谢!

Answer 1

__builtin_ctz获取类型的参数,unsigned int在大多数平台上为32位.

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