C++ 实现求二进制中 1 的个数 |21xrx.com

C++ 实现求二进制中 1 的个数

2023-06-22 07:23:45 深夜i -- --

C++ 二进制 1的个数实现

二进制是计算机世界中最基础的表达方式，经常被程序员用来进行位运算。对于一个二进制数，我们经常要求它中间 1 的个数。今天我来介绍 C++ 实现求二进制中 1 的个数的方法。

方法一：位运算法

我们可以通过不断把二进制数的最低位的 1 变为 0，并统计变的次数来得到 1 的个数。代码如下：


int countOne(int n) {
  int count = 0;
  while (n) {
    n &= n - 1;
    count++;
  }
  return count;
}

其中，`n &= n - 1` 表示将 `n` 的最低位 1 变为 0，因为 `n - 1` 的二进制数一定是在 `n` 最低位的 1 及其右侧的位上取反得来的。比如，`n` 为二进制数 `110101`，则 `n - 1` 为二进制数 `110100`。通过 `n &= n - 1` 可以将 `n` 的最后一个 1 变为 0，而其余 1 不受影响。我们将这个操作执行的次数累加起来即可得到 1 的个数。

方法二：查表法

我们可以提前将 0 到 255 每个十进制数的二进制表示中 1 的个数保存在一个长度为 256 的整数数组中，每次查询时将这个数组中 8 个数字加起来即可。代码如下：


const int bitCounts[256] = { /* 保存了 0 到 255 每个十进制数的二进制表示中 1 的个数 */ };
int countOne(int n) {
  int res = 0;
  unsigned char *p = (unsigned char*)&n; // 将 n 按字节地址连续映射为 8 个 unsigned char 变量
  for (int i = 0; i < sizeof(int); ++i) {
    res += bitCounts[p[i]];
  }
  return res;
}

以上两种方法均可以快速计算出二进制数中 1 的个数。在具体实现时，要对边界情况做好处理，以保证算法的准确性和正确性。

上一篇: idea打包java可执行jar包

下一篇: C++中如何寻找数组中的素数：子函数的调用方法

评论区

()

相似文章