c++ - 如何计算整数中的零位数？

Question

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

int value = 276;

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

score 26 · Accepted Answer

如果您想要效率，那么“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 位。

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

score 16 · Accepted Answer

最简单最天真的方法是迭代位并计数：

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

score 9 · Accepted Answer

9

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

于 2010-11-22T10:14:38.393 回答

score 8 · Accepted Answer

如果你使用 GCC，你可以尝试内置函数：

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

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

score 5 · Accepted Answer

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

int num_zero_bits = __builtin_popcount(~num);

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

score 4 · Accepted Answer

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
}

可以很容易地适应给定的任务。这里的迭代次数等于设置的位数。

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

score 3 · Accepted Answer

到目前为止，最明显的解决方案是查找表。

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

score 3 · Accepted Answer

这类东西有一本很棒的书：Hacker's Delight（是的，这个名字很烂：它与安全无关，只是有点玩弄）。它提供了几种计算“1”位的算法，最好的也可以在这里找到（尽管书中有解释，这个网站没有）。

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

score 1 · Accepted Answer

做一个人的赞美，然后数一数。

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

将工作。

score 0 · Accepted Answer

根据我的说法，在正整数中获取零位计数的最简单方法是以下代码。

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

这段代码很容易理解，而且很容易解释。这适用于正整数。

score 0 · Accepted Answer

扩展 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。 ..等）并添加/删除适当的班次

score 0 · Accepted Answer

#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/

score 0 · Accepted Answer

使用 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
}

c++ - 如何计算整数中的零位数？

13 回答 13

Related

Reference