在 C++ 中，计算一个 int整数的二进制表示中 1的个数（也称为 Population Count 或 Hamming Weight）有多种方法。以下是几种常见的方法：

方法 1：逐位检查（循环移位法）

int countOnes(int num) 
{
    int count = 0;
    for (int i = 0; i < 32; ++i) 
    {
        if (num & (1 << i)) 
        {
            count++;
        }
    }
    return count;
}

说明：

  • 遍历整数的每一位（共 32 位）。
  • 使用 1 << i生成掩码，检查该位是否为 1。
  • 优点：简单直观，适用于所有整数。
  • 缺点：循环次数固定为 32 次，效率较低。

方法 2：Brian Kernighan 算法（优化版）

int countOnes(int num) 
{
    int count = 0;
    while (num != 0) {
        num &= (num - 1);  // 清除最低位的1
        count++;
    }
    return count;
}

说明：

  • num &= (num - 1)会清除 num最低位的 1。
  • 优点：循环次数等于 1的个数，效率更高。
  • 缺点：对于 num = 0的情况也能正确处理。

方法 3：使用 std::bitset（C++标准库）

#include <bitset>

int countOnes(int num) 
{
    std::bitset<32> bits(num);
    return bits.count();  // 直接返回1的个数
}

说明：

  • std::bitset提供了 count()方法直接统计 1的个数。
  • 优点：代码简洁，可读性强。
  • 缺点：需要包含头文件 <bitset>，可能不如位操作高效。

方法 4：编译器内置函数（高效实现）

int countOnes(int num) 
{
    return __builtin_popcount(num);  // GCC/Clang 内置函数
}

说明：

  • __builtin_popcount是 GCC 和 Clang 提供的内置函数，直接调用硬件指令（如 POPCNT）。
  • 优点：效率最高（单条 CPU 指令）。
  • 缺点：非标准，仅适用于 GCC/Clang，MSVC 需用 __popcnt()。

方法 5：查表法（适用于频繁调用）

int countOnes(int num) 
{
    // 预计算8位数的1的个数（256种可能）
    static const unsigned char table[256] = 
    {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        // ...（完整表见下文）
    };
    return table[num & 0xFF] + table[(num >> 8) & 0xFF] +
           table[(num >> 16) & 0xFF] + table[(num >> 24) & 0xFF];
}

说明：

  • 预计算 8 位整数的 1的个数，然后分段查表。
  • 优点：无循环，适合高频调用场景。
  • 缺点：需要额外的静态表，占用内存。

性能对比

方法 时间复杂度 适用场景
逐位检查 O(32) 通用，简单
Brian Kernighan O(1的个数) 高效，推荐
std::bitset O(1) 代码简洁
内置函数 O(1) 极致性能（GCC/Clang）
查表法 O(1) 高频调用

示例代码（Brian Kernighan 算法）

#include <iostream>

int countOnes(int num) 
{
    int count = 0;
    while (num != 0) 
    {
        num &= (num - 1);
        count++;
    }
    return count;
}

int main() 
{
    int num = 0b1101;  // 二进制 1101（十进制 13）
    std::cout << countOnes(num);  // 输出 3
    return 0;
}

总结

  • 推荐方法：Brian Kernighan 算法（平衡性能和可读性）。
  • 极致性能：使用 __builtin_popcount（GCC/Clang）或 __popcnt()（MSVC）。
  • 代码简洁：std::bitset。