例如,如果我有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 = %dn",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上同时执行)。
需要了解更多c/c++开发分享如何使用C查找数字中的前导零数,也可以关注C/ C++技术分享栏目---计算机技术网(www.ctvol.com)!
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; }
以上就是c/c++开发分享如何使用C查找数字中的前导零数相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/979827.html