内部计算64位整数中的尾随零位?
这是关于位操作的一些先前问题的后续跟进。 我修改了这个站点的代码来枚举设置了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位的其他内在函数,还是我必须做一些内联汇编程序?
谢谢!
__builtin_ctz
接受unsigned int
类型的参数,在大多数平台上为32位。
如果long
为64位,则可以使用__builtin_ctzl
unsigned long
__builtin_ctzl
。 或者你可以使用__builtin_ctzll
unsigned long long
__builtin_ctzll
– 在这种情况下你应该使用1ULL << i
而不是1UL << i
。