如何计算整数中的零位数？

Question

我将如何在C++中找到"零"位的数量.假设我有一个整数;

int value = 276; 

我有100010100位,但我如何计算零？

Answer 1

如果你想要效率,那么在"黑客喜悦"一书中有一个很好的实现

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位

如果你想要更好的解释购买这本书,有很多很好的解释和讨论替代算法等...

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

Answer 3

您可以减去设置的位数 32 .

Answer 4

计算设置位的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
}

可以轻松适应给定的任务。这里的迭代次数等于设置的比特数。

我还推荐上面的链接，了解解决此问题和其他类型的位相关任务的各种其他方法。还有一个获取宏中实现的位数的单行示例。

Answer 5

如果您使用GCC，则可以尝试内置功能：

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

有关详细信息，请参见GCC文档。

Answer 6

我很惊讶没有人提到这一点：

int num_zero_bits = __builtin_popcount(~num);

num当与 GCC 一起使用时，这将给出零位的数量。