C++ 如何计算整数中零位的数量？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4244274/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How do I count the number of zero bits in an integer?
提问by unwind
How would i go about finding the number of 'zero' bits in C++. Suppose I have an integer;
我将如何在 C++ 中找到“零”位的数量。假设我有一个整数；
int value = 276;
For which I have the bits 100010100, but how do I count the zeros?
我有 100010100 位，但我如何计算零？
回答by ronag
If you want efficiency then there is a good implementation in the book "Hackers Delight"
如果您想要效率，那么“Hackers Delight”一书中有一个很好的实现
22 instructions branch free.
22 条指令分支自由。
unsigned int count_1bits(unsigned int x)
{
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
unsigned int count_0bits(unsigned int x)
{
return 32 - count_1bits(x);
}
I'll try to explain how it works. It is a divide-and-conquer algorithm.
我将尝试解释它是如何工作的。它是一种分而治之的算法。
(x >> 1) & 0x55555555
Shifts all bits 1 step to the right and takes the least significant bit of every bit pair.
将所有位向右移动 1 步，并取每个位对中的最低有效位。
0x55555555 -> 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 (16x2 bit pairs)
So basically you will have the following table of all 2 bit permutations.
所以基本上你将拥有所有 2 位排列的下表。
1. (00 >> 1) & 01 = 00
2. (01 >> 1) & 01 = 00
3. (10 >> 1) & 01 = 01
4. (11 >> 1) & 01 = 01
x - ((x >> 1) & 0x55555555);
Then you subtract these from the non shifted pairs.
然后你从非移位对中减去这些。
1. 00 - 00 = 00 => 0 x 1 bits
2. 01 - 00 = 01 => 1 x 1 bits
3. 10 - 01 = 01 => 1 x 1 bits
4. 11 - 01 = 10 => 2 x 1 bits
x = x - ((x >> 1) & 0x55555555);
So now we have changed every 2 bit pair so that their value is now the number of bits of their corresponding original 2 bit pairs... and then we continue in similar way with 4 bit groups, 8 bit groups, 16 bit groups and final 32 bit.
所以现在我们改变了每 2 位对，以便它们的值现在是它们对应的原始 2 位对的位数……然后我们以类似的方式继续使用 4 位组、8 位组、16 位组和最终32 位。
If you want a better explanation buy the book, there are a lot of good explanation and discussions of alternative algorithms etc...
如果你想要一个更好的解释买这本书，有很多很好的解释和替代算法等的讨论......
回答by unwind
The easiest most naive way is to just iterate over the bits and count:
最简单最幼稚的方法是遍历位并计数：
size_t num_zeroes = 0;
for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i)
{
if ((value & (1 << i)) == 0)
++num_zeroes;
}
There are all number of better (for different values of "better") ways, but this is quite clear, very terse (code-wise), and doesn't require a bunch of setup.
有很多更好的（对于“更好”的不同值）的方法，但这很清楚，非常简洁（代码方面），并且不需要一堆设置。
One micro-optimization that might be considered an improvement is to not compute the mask to test each bit, instead shift the value and always test the rightmost bit:
一种可能被视为改进的微优化是不计算掩码来测试每一位，而是移动值并始终测试最右边的位：
for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i, value >>= 1)
{
if ((value & 1) == 0)
++num_zeroes;
}
回答by Goz
You can do 32 minus the number of bits set.
你可以做 32 减去设置的位数。
回答by mih
If you use GCC, you can try built-in functions:
如果你使用 GCC，你可以尝试内置函数：
int __builtin_popcount (unsigned int x)
int __builtin_ctz (unsigned int x)
int __builtin_clz (unsigned int x)
See GCC Documentationfor details.
有关详细信息，请参阅GCC 文档。
回答by Basilevs
Kernighan wayof counting set bits
Kernighan计数设置位的方法
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v - 1; // clear the least significant bit set
}
Can be easily adapted for the task given. A number of iterations here is equal to a number of bits set.
可以很容易地适应给定的任务。这里的迭代次数等于设置的位数。
I also recommend the link above for various other ways of solving this and others types of bit-related tasks. There also is a single line example of obtaining bit count implemented in macros.
我还推荐上面的链接，以了解解决此问题和其他类型的与位相关的任务的各种其他方法。还有一个在宏中实现的获取位计数的单行示例。
回答by MSalters
By far the most obvious solution is a lookup table.
到目前为止，最明显的解决方案是查找表。
/* Assuming CHAR_BITS == 8 */
int bitsPerByte[256] = { 8, 7, 7, 6, /* ... */ };
int bitsInByte(unsigned char c) { return bits[c]; }
回答by icecrime
There is a great book for this kind of stuff : Hacker's Delight(yeah, the name sucks : it has nothing to do with security but exclusively bit-twiddling). It provides several algorithms to count '1' bits, the best can also be found here(although the book has explanations that this website doesn't).
有一本关于这类东西的好书：Hacker's Delight（是的，这个名字很糟糕：它与安全无关，只是有点麻烦）。它提供了几种计算“1”位的算法，最好的也可以在这里找到（尽管这本书有本网站没有的解释）。
Once you know the '1' bits count, just subtract it to the number of bits in your type representation.
一旦您知道“1”位数，只需将其减去您的类型表示中的位数。
回答by 17andLearning
I'm surprised no one has mentioned this one:
我很惊讶没有人提到这一点：
int num_zero_bits = __builtin_popcount(~num);
This will give the number of zero bits in numwhen used with GCC.
num当与 GCC 一起使用时，这将给出零位的数量。
回答by CashCow
Do a one's compliment then count the 1s.
做一个赞美然后数1。
count_zero_bits( x ) = count_one_bits( ~x );
count_zero_bits( x ) = count_one_bits( ~x );
Implement the code to count the ones.
实现代码来计算那些。
template< typename I >
int count_one_bits( I i )
{
size_t numbits = 0;
for( ; i != 0; i >>= 1 )
{
numbits += i&1;
}
}
although there is an issue with my function if i is a negative number because >> will put 1 bits into the right hand side so you will get a never-terminating loop. If there is a templated way to enforce an unsigned type that would be ideal.
尽管如果 i 是负数，我的函数会出现问题，因为 >> 会将 1 位放入右侧，因此您将获得永不终止的循环。如果有一种模板化的方式来强制执行无符号类型，那将是理想的。
Once you have that then:
一旦你有了它：
template< typename I > int count_zero_bits( I i )
{
return count_one_bits( ~i );
}
will work.
将工作。
回答by user43609
According to me , the simplest way to get the zero bit count in a positive integer is the following piece of code.
根据我的说法，在正整数中获得零位计数的最简单方法是以下代码。
int get_zero_bit_count(int num)
{
int cnt = 0;
while(num > 0)
{
int and_num = num & 1;
if (and_num != num) cnt++;
num >>= 1;
}
return cnt;
}
This piece of code is easy to understand and is selp explainatory . This works well for positive integers.
这段代码很容易理解，也很容易解释。这适用于正整数。
