我如何找到 C++ 中“零”位的数量。 假设我有一个整数；
int value = 276;
我有位 100010100，但是如何计算零呢？
如果你想要效率，那么《Hackers Delight》一书中有一个很好的实现
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);
}
我将尝试解释它是如何工作的。这是一种分而治之的算法。
(x >> 1) & 0x55555555
将所有位向右移动 1 步，并取每个位对的最低有效位。
0x55555555 -> 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 (16x2 bit pairs)
所以基本上你会得到下表的所有 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);
然后从非移位对中减去这些。
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);
所以现在我们已经改变了每2位对，使得它们的值现在是它们对应的原始2位对的位数...然后我们以类似的方式继续4位组、8位组、16位组和最终 32 位。
如果您想要更好的解释，请购买这本书，其中有很多关于替代算法等的很好的解释和讨论......
最简单、最天真的方法就是迭代这些位并计数：
size_t num_zeroes = 0;
for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i)
{
if ((value & (1 << i)) == 0)
++num_zeroes;
}
有很多更好的（对于“更好”的不同值）方法，但这非常清楚，非常简洁（代码方面），并且不需要一堆设置。
一个可能被认为是改进的微优化是不计算掩码来测试每个位，而是移动值并始终测试最右边的位：
for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i, value >>= 1)
{
if ((value & 1) == 0)
++num_zeroes;
}
您可以做 32 减去设置的位数。
如果你使用GCC，你可以尝试内置函数：
int __builtin_popcount (unsigned int x)
int __builtin_ctz (unsigned int x)
int __builtin_clz (unsigned int x)
有关详细信息，请参阅 GCC 文档。
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
}
可以轻松适应给定的任务。这里的迭代次数等于设置的比特数。
我还推荐上面的链接，了解解决此问题和其他类型的位相关任务的各种其他方法。还有一个在宏中实现获取位数的单行示例。
我很惊讶没有人提到这个：
int num_zero_bits = __builtin_popcount(~num);
与 GCC 一起使用时，这将给出
num到目前为止，最明显的解决方案是查找表。
/* Assuming CHAR_BITS == 8 */
int bitsPerByte[256] = { 8, 7, 7, 6, /* ... */ };
int bitsInByte(unsigned char c) { return bits[c]; }
有一本关于此类内容的好书：Hacker's Delight（是的，这个名字很糟糕：它与安全无关，而只是一些小玩意）。它提供了几种算法来计算“1”位，最好的算法也可以在here找到（尽管这本书有解释，但该网站没有）。
一旦知道“1”位数，只需将其减去类型表示中的位数即可。
赞美别人，然后数1。
count_zero_bits( x ) = count_one_bits( ~x );
实现代码来计算个数。
template< typename I >
int count_one_bits( I i )
{
size_t numbits = 0;
for( ; i != 0; i >>= 1 )
{
numbits += i&1;
}
}
尽管如果 i 是负数，我的函数就会出现问题，因为 >> 会将 1 位放入右侧，因此您将得到一个永不终止的循环。如果有一种模板化方法来强制执行无符号类型，那就太理想了。
一旦你有了：
template< typename I > int count_zero_bits( I i )
{
return count_one_bits( ~i );
}
会起作用的。
根据我的说法，获取正整数中的零位计数的最简单方法是以下代码。
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;
}
这段代码很容易理解，并且有自我解释。这对于正整数非常有效。
扩展 ronag 的答案，其他用户提到的会导致错误的结果（他的算法仅适用于 x = 15 的值），这里是该算法的更新版本：
uint8_t count_1bits(uint32_t x) {
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
return x & 0x3F;
}
uint8_t count_0bits(uint32_t x) {
return 32 - count_1bits(x);
}
ronag 第一行的解释是正确的，但是，其余行使用了不同的方法。在第一行中，通过移位和减法，每个 2 位对将包含原始数字中该对中设置的位数。其余行通过将每个 2n 位组的 lsb 添加到该对移位 n 的 msb 来递归地将这些数字折叠在一起，以便 2n 位组包含在该组中设置的位数原编号：
01110110: 0111 (7 bits were set in the original number) 0110 (6 bits were set in the original number)
-> 01110110 & 00001111 + (01110110 >> 4) & 00001111
= 0110 + 0111
= 1101
上述算法适用于 32 位整数，但可以通过将常量更改为正确的位长度来轻松调整，以使模式保持不变（例如 0x5555... = 0101...、0x0f0f... = 00001111 ...等）并添加/删除适当的班次
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
ll a;
cin>>a;
ll ones=__builtin_popcountll(~a);
ll zero=__builtin_clzll(a);
ll num=abs(ones-zero);
cout<<num<<"\n";
return 0;
}
借助内置 gcc 函数，即 popcount（计算设置位的数量）和 clz（计算前导零的数量），我们可以计算整数中零位的数量
您可以在这里阅读有关它们的信息https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html，https://www.geeksforgeeks.org/builtin-functions-gcc-compiler/