461. 汉明距离

描述

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：
0 ≤ x, y < 231.

示例:

输入: x = 1, y = 4

输出: 2

解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

上面的箭头指出了对应二进制位不同的位置。

思路

(1)即求异或结果中1的个数。为了计算等于 1 的位数，可以将每个位移动到最右侧，然后检查该位是否为 1。

class Solution {
    public int hammingDistance(int x, int y) {
        int result = x ^ y;
        int m = 1;
        int count = 0;
        while(result != 0){
            //if(result % 2 == 1){  
            if((result & 1) == 1){
                count++;
            }
            result >>= 1;
        }
        return count;
    }
}

复杂度分析：

• 时间复杂度：O(1)，在 Python 和 Java 中 Integer 的大小是固定的，处理时间也是固定的。 32 位整数需要 32 次迭代。

• 空间复杂度：O(1)，使用恒定大小的空间。

（2）布赖恩·克尼根算法（效率更高）

方法二是逐位移动，逐位比较边缘位置是否为 1。寻找一种更快的方法找出等于 1 的位数。

是否可以像人类直观的计数比特为 1 的位数，跳过两个 1 之间的 0。例如：10001000。

上面例子中，遇到最右边的 1 后，如果可以跳过中间的 0，直接跳到下一个 1，效率会高很多。

这是布赖恩·克尼根位计数算法的基本思想。该算法使用特定比特位和算术运算移除等于 1 的最右比特位。

当我们在 number 和 number-1 上做 AND 位运算时，原数字 number 的最右边等于 1 的比特会被移除。

基于以上思路，通过 2 次迭代就可以知道 10001000 中 1 的位数，而不需要 8 次。即只需对最后一位1做运算，而不需对每一位都要与1相与来统计个数，效率更高。

class Solution {
  public int hammingDistance(int x, int y) {
    int xor = x ^ y;
    int distance = 0;
    while (xor != 0) {
      distance += 1;
      // remove the rightmost bit of '1'
      xor = xor & (xor - 1);
    }
    return distance;
  }
}

复杂度分析：

• 时间复杂度：O(1)。

  • 与移位方法相似，由于整数的位数恒定，因此具有恒定的时间复杂度。

  • 但是该方法需要的迭代操作更少。

• 空间复杂度：O(1)，与输入无关，使用恒定大小的空间。