如何仅使用 C 中的位运算(没有 if、for、while 等)返回整数左侧连续 1 的个数? 我不确定从哪里开始解决这个问题。
//BurstSize(-1) = 32,
//BurstSize(0xFFF0F0F0) = 12
//Legal: ! ~ & ^ | + << >>
//Max ops: 50
int BurstSize(int a) {
//code
}
最佳答案
如果您使用 GCC,您可以调用 __builtin_clz()
来计算前导零。反转输入,然后它可以用来计算领先的。
int BurstSize(unsigned a) {
return __builtin_clz(~a);
}
如果您无法访问__builtin_*()
,那么您可以实现前导零计数功能,如Hacker's Delight :
int nlz4(unsigned x) {
int y, m, n;
y = -(x >> 16); // If left half of x is 0,
m = (y >> 16) & 16; // set n = 16. If left half
n = 16 - m; // is nonzero, set n = 0 and
x = x >> m; // shift x right 16.
// Now x is of the form 0000xxxx.
y = x - 0x100; // If positions 8-15 are 0,
m = (y >> 16) & 8; // add 8 to n and shift x left 8.
n = n + m;
x = x << m;
y = x - 0x1000; // If positions 12-15 are 0,
m = (y >> 16) & 4; // add 4 to n and shift x left 4.
n = n + m;
x = x << m;
y = x - 0x4000; // If positions 14-15 are 0,
m = (y >> 16) & 2; // add 2 to n and shift x left 2.
n = n + m;
x = x << m;
y = x >> 14; // Set y = 0, 1, 2, or 3.
m = y & ~(y >> 1); // Set m = 0, 1, 2, or 2 resp.
return n + 2 - m;
}
int BurstSize(unsigned a) {
return nlz4(~a);
}
关于c - 仅使用位运算的整数左侧连续的个数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21899879/