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

rhsgfswg

一、题目解读

牛客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. 输出结果：返回差异位计数。

四、代码与注释

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int countBitDiff(int a, int b) {
   
5. // 异或运算得到不同位为1的结果
   
6. int xor_result = a ^ b;
   
7. int count = 0;
   
8. 
   
9. // 计算1的个数
   
10. while (xor_result) {
    
11. count += xor_result & 1; // 检查**位是否为1
    
12. xor_result >>= 1; // 右移一位继续检测
    
13. }
    
14. return count;
    
15. }
    
16. 
    
17. int main() {
    
18. int a, b;
    
19. cin >> a >> b;
    
20. cout << countBitDiff(a, b) << endl;
    
21. return 0;
    
22. }

复制代码

五、总结

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

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