高效统计二进制中1的个数：位运算技巧解析

1. 二进制中1的计数原理与实现

在计算机科学中，统计一个整数二进制表示中1的个数是一个经典问题。这个问题看似简单，但背后蕴含着巧妙的位运算技巧。今天我要分享的是一个高效的计算方法，它利用了二进制数的特性，通过位运算快速统计1的个数。

1.1 基础方法对比

最直观的方法是逐位检查。对于一个32位整数，我们可以通过循环右移并与1进行按位与操作来统计1的个数：

c复制int count_bits_naive(unsigned int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

这种方法简单易懂，但效率不高，因为它必须检查每一位，即使某些位是0。对于32位整数，总是需要32次循环。

1.2 优化思路：利用n & (n-1)

更聪明的方法是使用n & (n-1)这个技巧。这个操作有一个神奇的特性：它会把n的二进制表示中最右边的1变成0。让我们深入理解为什么：

• 当n减1时，最低位的1会变成0，这个1右边的所有0会变成1
• 然后与原数n进行按位与操作，会保留原数中更高位的1，而将最低位的1及其右边的所有位清零

例如，n=12（二进制1100）：

• n-1=11（1011）
• n & (n-1) = 1100 & 1011 = 1000（8）

可以看到，最右边的1被消除了。每次这样的操作恰好消除一个1，因此我们可以通过统计这个操作的次数来得到1的总数。

2. 代码实现与解析

2.1 核心函数实现

基于上述原理，我们可以写出非常简洁的实现：

c复制int count_num_of_1(int n) {
    int count = 0;
    while (n) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

这个函数的循环次数等于n中1的个数，而不是固定的32次，效率显著提高。

2.2 完整测试程序

为了验证这个函数，我们可以编写一个简单的测试程序：

c复制#include <stdio.h>

i