这是对之前关于位操作的一些问题的跟进。我修改了 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 位,是否还有我应该使用的其他内在函数,或者我是否必须执行一些内联汇编程序?
谢谢!
最佳答案
__builtin_ctz
采用 unsigned int
类型的参数,在大多数平台上为 32 位。
如果long
是64位的,可以用__builtin_ctzl
这需要 unsigned long
.或者你可以使用 __builtin_ctzll
这需要 unsigned long long
- 在这种情况下你应该使用 1ULL << i
而不是 1UL << i
.
关于c++ - 计算 64 位整数中的尾随零位是固有的吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20747205/