牛客16909题解法：利用异或运算与位操作高效统计二进制位差异

一、题目解读

牛客16909题要求计算两个整数a和b的二进制位差异，即统计a和b二进制表示中不同位的数量。题目需高效处理整数差异，考察对位运算的理解与应用。例如，当a=5（二进制101）与b=3（二进制011）时，差异位为第二位和第三位，共2个，因此输出应为2。

二、解题思路

核心思路为：异或运算+位统计。

1. 通过a^b（异或）得到的新数，其每位为1的条件是a、b对应位不同（相同为0，不同为1）。

2. 统计异或结果中二进制1的个数，即为差异位总数。

3. 采用位运算优化：循环右移并检查最低位，避免复杂遍历，提升效率。

三、解题步骤解析

1. 输入处理：读取整数a和b。

2. 异或计算：执行a^b，生成差异位标记数。

3. 位统计循环：

    通过&1检查当前最低位是否为1，累加计数器。

    右移>>1逐位检测，直至数值为0。

4. 输出结果：返回差异位计数。

四、代码与注释

#include <iostream>  
using namespace std;  

int countBitDiff(int a, int b) {  
    // 异或运算得到不同位为1的结果  
    int xor_result = a ^ b;  
    int count = 0;  

    // 计算1的个数  
    while (xor_result) {  
        count += xor_result & 1;  // 检查最低位是否为1  
        xor_result >>= 1;         // 右移一位继续检测  
    }  
    return count;  
}  

int main() {  
    int a, b;  
    cin >> a >> b;  
    cout << countBitDiff(a, b) << endl;  
    return 0;  
}

五、总结

本文解法利用异或运算的“不同位为1”特性，结合位操作高效统计差异位，时间复杂度为O(logn)（取决于二进制位数），空间复杂度O(1)。掌握此类位运算技巧可显著优化算法性能，适合编程练习与竞赛场景。