如何使用C查找数字中的前导零数
例如，如果我有64号，那么它的二进制表示将是0000 0000 0000 0000 0000 0000 0100 0000，因此零的前导数是25.记住我必须在O（1）时间内计算它。
请告诉我正确的方法。即使你的复杂性> O（1），请发表你的答案。 感谢名单
我刚刚在搜索结果的顶部发现了这个问题，这个代码：
int pop(unsigned x) { unsigned n; n = (x >> 1) & 033333333333; x = x - n; n = (n >> 1) & 033333333333; x = x - n; x = (x + (x >> 3)) & 030707070707; return x % 63; } int nlz(unsigned x) { x = x | (x >> 1); x = x | (x >> 2); x = x | (x >> 4); x = x | (x >> 8); x = x | (x >>16); return pop(~x); }
pop的计数为1位，比第一个（upvoted）答案快几倍。
我没有注意到，问题是关于64位数字，所以这里：
int nlz(unsigned long x) { unsigned long y; long n, c; n = 64; c = 32; do { y = x >> c; if (y != 0) { n = n - c; x = y; } c = c >> 1; } while (c != 0); return n - x; }
是64位算法，再次比上面提到的快几倍。
右转是你的朋友。
int input = 64; int sample = ( input < 0 ) ? 0 : input; int leadingZeros = ( input < 0 ) ? 0 : 32; while(sample) { sample >>= 1; --leadingZeros; } printf("Input = %d, leading zeroes = %d\n",input, leadingZeros);
请看这里的32位版本和其他伟大的位杂乱黑客。
// this is like doing a sign-extension // if original value was 0x00.01yyy..y // then afterwards will be 0x00.01111111 x |= (x >> 1); x |= (x >> 2); x |= (x >> 4); x |= (x >> 8); x |= (x >> 16); x |= (x >> 32);
之后你只需要返回64 – numOnes（x）。 一个简单的方法是numOnes32（x）+ numOnes32（x >> 32），其中numOnes32定义为：
int numOnes32(unsigned int x) { x -= ((x >> 1) & 0x55555555); x = (((x >> 2) & 0x33333333) + (x & 0x33333333)); x = (((x >> 4) + x) & 0x0f0f0f0f); x += (x >> 8); x += (x >> 16); return(x & 0x0000003f); }
我没有尝试过这段代码，但这应该直接使用numOnes64（在更短的时间内）：
int numOnes64(unsigned long int x) { x = ((x >> 1) & 0x5555555555555555L) + (x & 0x5555555555555555L); x = ((x >> 2) & 0x3333333333333333L) + (x & 0x3333333333333333L); // collapse: unsigned int v = (unsigned int) ((x >>> 32) + x); v = ((v >> 4) + v) & 0x0f0f0f0f) + (v & 0x0f0f0f0f); v = ((v >> 8) & 0x00ff00ff) + (v & 0x00ff00ff); return ((v >> 16) & 0x0000ffff) + (v & 0x0000ffff); }
我会选择：
unsigned long clz(unsigned long n) { unsigned long result = 0; unsigned long mask = 0; mask = ~mask; auto size = sizeof(n) * 8; auto shift = size / 2; mask >>= shift; while (shift >= 1) { if (n <= mask) { result += shift; n <<= shift; } shift /= 2; mask <<= shift; } return result; }
因为对数基数2大致表示表示数字所需的位数，所以在答案中可能有用：
irb(main):012:0> 31 - (Math::log(64) / Math::log(2)).floor() => 25 irb(main):013:0> 31 - (Math::log(65) / Math::log(2)).floor() => 25 irb(main):014:0> 31 - (Math::log(127) / Math::log(2)).floor() => 25 irb(main):015:0> 31 - (Math::log(128) / Math::log(2)).floor() => 24
当然，使用log(3)一个缺点是它是一个浮点例程; 可能有一些非常聪明的比特技巧来找到整数中前导零位的数量，但我想不出一个我的头顶…
使用浮点数不是正确答案….
这是一个算法，我用它来计算TRAILING 0 …将它改为前导……这个算法在O（1）中（总是在同一时间执行，甚至在某些CPU上同时执行）。
int clz(unsigned int i) { int zeros; if ((i&0xffff)==0) zeros= 16, i>>= 16; else zeroes= 0; if ((i&0xff)==0) zeros+= 8, i>>= 8; if ((i&0xf)==0) zeros+= 4, i>>= 4; if ((i&0x3)==0) zeros+= 2, i>>= 2; if ((i&0x1)==0) zeros+= 1, i>>= 1; return zeroes+i; }