如何计算一个整数中零位的数量？

Question

我该如何在 C++ 中查找“零”位的数量？假设我有一个整数；

int value = 276; 

我有一串二进制位 100010100，如何计算其中零的个数？

- user349026

---

请点击此处查看：http://graphics.stanford.edu/~seander/bithacks.html。 - Chris Lutz

尝试在谷歌上搜索“位计数”。 - Bojan Komazec

你忘记了前面的23个零了吗？是啊，是啊，我知道这取决于整数表示方式 ;) - mih

我最近花了相当多的时间研究如何优化Tanimoto计算中的popcount。这里有一个很好的总结，介绍了几种方法：http://www.dalkescientific.com/writings/diary/archive/2008/07/05/bitslice_and_popcount.html。最终我使用了一个16位LUT，它非常简单，速度也比最快的稍微慢一点。如果你真的关心速度的话，那就用它吧。 - Dmitri

Answer 1

如果你想要效率，那么书籍“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

将所有位向右移动一个单位，并取每个位对中的最低有效位。

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位。

如果您想要更好的解释，请购买这本书，其中有很多关于替代算法等方面的良好解释和讨论...

- ronag

---

除了count_0bits()函数假设在您选择的平台和编译器上，无符号整数是32位的... - user

的确。需要分别为16、32和64位执行不同的实现。可以使用元模板编程完成。 - ronag

你漏掉了一行代码：x = (x + (x >> 4)) & 0x0f0f0f0f;，在 x = x + (x >> 8); 之前。 - libo

Answer 2

最简单、最朴素的方法就是遍历位并计数：

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;
}

- unwind

---

另一个微小的优化是删除==0（并稍微修改条件），因为0==false且1==true。 - Kricket

@Kelsey：但那只是愚蠢的做法，编译器会在非常低级别的优化（甚至可能没有任何优化）中自动完成这项工作。为保持清晰明了，最好还是保留它。 - unwind

Answer 3

你可以做32减去所设置的位数。

- Goz

---

最好是8 * sizeof(int) -（设置位的数量），但这个建议很好。 - BЈовић

@VJo：C++标准是否规定了8位字节？从技术上讲，在C语言中，您不能假设sizeof返回8位字节的大小。 - JeremyP

@JeremyP 你是对的。C++标准1.7-1告诉我们：“一个字节至少要足够大，以包含基本执行字符集中的任何成员，并由一系列连续的位组成，其数量是实现定义的。” - BЈовић

是的，你需要 CHAR_BIT * sizeof(int)，即使这只告诉你内存中的大小，而不是 int 值表示所需的位数。你可以从 std::numeric_limits<int>::digits + std::numeric_limits<int>::is_signed 获取该值。 - MSalters

Answer 4

如果您使用GCC编译器，可以尝试使用内置函数：

int __builtin_popcount (unsigned int x) 
int __builtin_ctz (unsigned int x)
int __builtin_clz (unsigned int x)

详细信息请参阅GCC文档。

- mih

Answer 5

Kernighan算法用于计算二进制位中置为1的数量。

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
}

可以轻松地适应所给定的任务。此处的迭代次数等于设置的位数。

我还建议查看上面的链接，了解解决这种和其他类型位相关任务的各种方法。还有一个单行示例，实现了获取位计数的宏。

- Basilevs

---

这是一个非常有用的补充 - 许多重要的算法在非常大（多字）位向量或矩阵中产生稀疏分布的集合位。 - Brett Hale

Answer 6

我很惊讶没有人提到这个：

int num_zero_bits = __builtin_popcount(~num);

使用GCC时，num中的零位数将被计算。

- 17andLearning

Answer 7

这里有一本非常适合这种问题的书：Hacker's Delight（是的，名字很糟糕：它与安全无关，而完全是位操作）。它提供了几种算法来计算“1”位数，最好的算法也可以在这里找到（尽管这本书有这个网站没有的解释）。

一旦你知道了“1”位数，只需将其从类型表示中的位数中减去即可。

- icecrime

---

“Hacking”或“Hacker”这个词的含义被误解了。它不仅仅与安全有关。在这个上下文中，它只是指“聪明或快速的解决方法”（参见维基百科）。 :) - SysAdmin

@SysAdmin：不幸的是，该死的媒体把“hack/hacking/hacker”的含义曲解成了“crack/cracking/cracker”的意思。虽然我们中的一些人仍在抵制。 - R. Martinho Fernandes

@SysAdmin：确实如此，但每次我推荐这本书时，总会得到一些有关安全性的愚蠢评论 :) - icecrime

Answer 8

迄今为止最明显的解决方案是查找表。

/* Assuming CHAR_BITS == 8 */
int bitsPerByte[256] = { 8, 7, 7, 6, /* ... */ };
int bitsInByte(unsigned char c) { return bits[c]; }

- MSalters

---

我认为“统计零位的数量”是解决“如何计算一个整数的零位数？”问题的更为明显的方案。 - R. Martinho Fernandes

Answer 9

在C++20中，您可以使用标准库函数bit_width和popcount来实现此功能：

#include <bit>
#include <cstdint>
#include <iostream>
 
int main()
{
    uint32_t i = 276;
    std::cout << std::bit_width(i) - std::popcount(i) << '\n'; // output: 6
}

- Chao

Answer 10

先执行一次取反操作，然后计算其中的1的个数。

count_zero_bits( x ) = count_one_bits( ~x );

实现代码以计算1的个数。

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 );
}

会起作用。

- CashCow