最重要的设置位的未设置位数？

假设64位整数0x000000000000FFFF表示为

 00000000 00000000 00000000 00000000 00000000 00000000 >11111111 11111111 

如何找到最重要的设置位（标有>的那个）左侧的未设置位数？

Answer 1

 // clear all bits except the lowest set bit x &= -x; // if x==0, add 0, otherwise add x - 1. // This sets all bits below the one set above to 1. x+= (-(x==0))&(x - 1); return 64 - count_bits_set(x); 

其中count_bits_set是您可以找到的最快的计数位版本。 有关各种位计数技术，请参阅https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel 。

Answer 2

在直接C（我的设置中很长的64位），取自类似的Java实现:(在更多关于汉明重量的阅读后更新）

更多解释：顶部只是将所有位置于最重要的1的右侧，然后否定它。 （即，最重要的1的’左’的0到现在都是1，其他一切都是0）。

然后我使用汉明重量实现来计算比特。

 unsigned long long i = 0x0000000000000000LLU; i |= i >> 1; i |= i >> 2; i |= i >> 4; i |= i >> 8; i |= i >> 16; i |= i >> 32; // Highest bit in input and all lower bits are now set. Invert to set the bits to count. i=~i; i -= (i >> 1) & 0x5555555555555555LLU; // each 2 bits now contains a count i = (i & 0x3333333333333333LLU) + ((i >> 2) & 0x3333333333333333LLU); // each 4 bits now contains a count i = (i + (i >> 4)) & 0x0f0f0f0f0f0f0f0fLLU; // each 8 bits now contains a count i *= 0x0101010101010101LLU; // add each byte to all the bytes above it i >>= 56; // the number of bits printf("Leading 0's = %lld\n", i); 

我很想知道这是多么有效率。 虽然测试了几个值，它似乎工作。

Answer 3

基于： http ： //www.hackersdelight.org/HDcode/nlz.c.txt

 template int clz(T v) {int n=sizeof(T)*8;int c=n;while (n){n>>=1;if (v>>n) c-=n,v>>=n;}return cv;} 

如果您想要一个允许您保持午餐的版本，请转到：

 int clz(uint64_t v) { int n=64,c=64; while (n) { n>>=1; if (v>>n) c-=n,v>>=n; } return cv; } 

正如您将看到的，您可以通过仔细分析汇编程序来节省周期，但这里的策略并不可怕。 while循环将运行Lg [64] = 6次; 每次它将问题转换为计算一半大小的整数的前导位数。 while循环中的if语句提出了一个问题：“我可以将这个整数表示为一半的位数”，或者类似地说，“如果我把它减半，我丢失了吗？”。 if（）有效负载完成后，我们的数字将始终位于最低的n位。 在最后阶段，v为0或1，这样就可以正确完成计算。

Answer 4

如果您正在处理无符号整数，则可以执行以下操作：

 #include  int numunset(uint64_t number) { int nbits = sizeof(uint64_t)*8; if(number == 0) return nbits; int first_set = floor(log2(number)); return nbits - first_set - 1; } 

我不知道它将如何在性能上与已经提供的循环和计数方法进行比较，因为log2（）可能很昂贵。

编辑 ：

这可能会导致高值整数出现一些问题，因为log2()函数会转换为double并且可能会出现一些数值问题。 您可以使用与long double一起使用的log2l()函数。 更好的解决方案是使用整数log2()函数， 如此问题 。

Answer 5

我不确定我是否正确理解了这个问题。 我认为你有一个64位的值，并希望找到其中的前导零数。

一种方法是找到最高有效位并简单地从63减去其位置（假设最低位为位0）。 您可以通过测试是否在所有64位的循环内设置位来找出最重要的位。

另一种方法可能是在gcc中使用（非标准）__builtin_clz。

Answer 6

我同意二元搜索的想法。 但是这里有两点很重要：

1. 您问题的有效答案范围为0到64（ 含） 。 换句话说 – 这个问题可能有65个不同的答案。 我认为（几乎可以肯定）所有发布“二分搜索”解决方案的人都错过了这一点，因此在MSB位开启时，他们会得到零或数字的错误答案。
2. 如果速度至关重要 – 您可能希望避免循环。 使用模板可以实现这一目标。

以下模板内容正确地找到任何无符号类型变量的MSB。

 // helper template  bool IsBitReached(T x) { const T cmp = T(1) << (bits ? (bits-1) : 0); return (x >= cmp); } template  int FindMsbInternal(T x) { if (!bits) return 0; int ret; if (IsBitReached(x)) { ret = bits; x >>= bits; } else ret = 0; return ret + FindMsbInternal(x); } // Main routine template  int FindMsb(T x) { const int bits = sizeof(T) * 8; if (IsBitReached(x)) return bits; return FindMsbInternal(x); } 

Answer 7

在这里，您可以轻松更新，因为您需要其他尺寸……

 int bits_left(unsigned long long value) { static unsigned long long mask = 0x8000000000000000; int c = 64; // doh if (value == 0) return c; // check byte by byte to see what has been set if (value & 0xFF00000000000000) c = 0; else if (value & 0x00FF000000000000) c = 8; else if (value & 0x0000FF0000000000) c = 16; else if (value & 0x000000FF00000000) c = 24; else if (value & 0x00000000FF000000) c = 32; else if (value & 0x0000000000FF0000) c = 40; else if (value & 0x000000000000FF00) c = 48; else if (value & 0x00000000000000FF) c = 56; // skip value <<= c; while(!(value & mask)) { value <<= 1; c++; } return c; } 

Answer 8

与user470379相同的想法，但倒计时……
假设未设置所有64位。 当值大于0时，保持向右移动值并减少未设置位的数量：

 /* untested */ int countunsetbits(uint64_t val) { int x = 64; while (val) { x--; val >>= 1; } return x; } 

Answer 9

尝试

 int countBits(int value) { int result = sizeof(value) * CHAR_BITS; // should be 64 while(value != 0) { --result; value = value >> 1; // Remove bottom bits until all 1 are gone. } return result; } 

Answer 10

使用log base 2可以获得最重要的数字1。

 log(2) = 1, meaning 0b10 -> 1 log(4) = 2, 5-7 => 2.xx, or 0b100 -> 2 log(8) = 3, 9-15 => 3.xx, 0b1000 -> 3 log(16) = 4 you get the idea 

等等……中间的数字成为日志结果的一部分。 因此，将值类型转换为int可以为您提供最重要的数字。

一旦你得到这个数字，比如b，那么简单的64-n就是答案。

 function get_pos_msd(int n){ return int(log2(n)) } last_zero = 64 - get_pos_msd(n)