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

胡志明t

一、题目解读

牛客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题解法：利用异或运算与位操作高效统计二进制位差异