解题思路

这是一道计算两个整数二进制表示中不同位数的题目，主要思路如下：

  1. 问题分析：

    • 给定两个int32整数 和
    • 需要计算它们的二进制表示中有多少位不同
    • 例如：3(11)和5(101)有2位不同

  2. 解决方案：

    • 使用异或运算(^)找出不同的位（结果为1的位就是不同的位）
    • 使用Brian Kernighan算法计算1的个数
    • 可以消除最右边的1

  3. 优化技巧：

    • 不需要实际转换成二进制字符串
    • 使用位运算可以高效计算

代码

class Solution {
public:
    int countBitDiff(int m, int n) {
        // 异或运算找出不同的位
        int r = m ^ n;
        int count = 0;
        
        // Brian Kernighan算法计算1的个数
        while(r) {
            r &= (r - 1);  // 消除最右边的1
            count++;
        }
        
        return count;
    }
};

public class Solution {
    public int countBitDiff(int m, int n) {
        // 异或运算找出不同的位
        int r = m ^ n;
        int count = 0;
        
        // Brian Kernighan算法计算1的个数
        while(r != 0) {
            r &= (r - 1);  // 消除最右边的1
            count++;
        }
        
        return count;
    }
}

class Solution:
    def countBitDiff(self, m: int, n: int) -> int:
        # 异或运算找出不同的位
        r = m ^ n
        count = 0
        
        # Brian Kernighan算法计算1的个数
        while r:
            r &= (r - 1)  # 消除最右边的1
            count += 1
        
        return count

算法及复杂度

  • 算法：Brian Kernighan算法
  • 时间复杂度： - 为二进制中1的个数
  • 空间复杂度： - 只需要常数级别的额外空间