牛客16909题解：位运算经典，二进制位不同个数计算

一、问题理解

牛客16909题要求计算两个整数的二进制表示中不同位的数量，这在错误检测、密码学、图像处理等领域有广泛应用。

二、算法核心思想

1. 异或运算：找出两个数不同的二进制位

2. 位计数：统计异或结果中1的个数

3. 位操作：通过移位和与运算逐位检查

三、完整代码实现（带注释）

#include <iostream>
using namespace std;

int countBitDiff(int a, int b) {
    // 异或运算得到不同位为1的结果
    // 例如：5(0101) ^ 3(0011) = 6(0110)
    int xor_result = a ^ b;
    int count = 0;
    
    // 计算1的个数（汉明重量）
    while (xor_result) {
        // 检查最低位是否为1
        count += xor_result & 1;
        // 右移一位，相当于除以2
        xor_result >>= 1;
    }
    return count;
}

int main() {
    int a, b;
    cin >> a >> b;
    // 输出距离
    cout << countBitDiff(a, b) << endl;
    return 0;
}

四、关键点解析

1. 异或运算：a ^ b 的结果中，1的位表示a和b在该位不同

2. 位计数：通过循环和位操作统计1的个数

3. 时间复杂度：O(log(max(a,b)))，取决于数字的二进制位数