二进制数中1的个数计算与位运算优化

1. 问题背景与核心需求

这道题目来自AcWing题库第801题，属于位运算基础题型。给定一个长度为n的数列，要求快速计算每个数的二进制表示中1的个数。这类问题在算法竞赛、面试笔试以及底层系统开发中都非常常见。

举个例子，数字5的二进制是101，其中包含2个1；数字7的二进制是111，包含3个1。看似简单的问题背后，其实考察了对计算机底层数据表示的理解，以及位运算的灵活应用能力。

2. 基础解法与位运算原理

2.1 逐位检查法

最直观的思路是将数字的每一位依次取出检查：

cpp复制int countOnes(int x) {
    int cnt = 0;
    while (x) {
        cnt += x & 1;  // 检查最低位
        x >>= 1;       // 右移一位
    }
    return cnt;
}

这个方法的时间复杂度是O(k)，k是数字的二进制位数。对于32位整数，最多需要32次循环。虽然简单易懂，但在处理大量数据时效率不够理想。

2.2 位运算优化技巧

更高效的方法是使用x & (x - 1)这个位运算技巧：

cpp复制int countOnes(int x) {
    int cnt = 0;
    while (x) {
        x &= (x - 1);  // 清除最低位的1
        cnt++;
    }
    return cnt;
}

这个方法的精妙之处在于：x - 1会将x的最低位的1变为0，而该位后面的0全部变为1。与运算后，最低位的1就被清除了。这样每次循环都能精确地消除一个1，循环次数等于1的个数。

3. 进阶解法与性能对比

3.1 查表法（预计算）

对于需要处理大量数据的情况，可以预先计算好所有可能的8位数（0-255）的1的个数，然后分段查询：

cpp复制int table[256];
void initTable() {
    for (int i = 0; i < 256; i++) {
        table[i] = (i & 1) + table[i / 2];
    }
}

int countOnes(int x) {