汉明距离

汉明距离

问题

这个题目说的是，给你两个整数，你要计算出它们的二进制表示中，相应的二进制位有多少个是不同的。这个不同的个数，也称为这两个整数的汉明距离。

比如说，给你的两个整数是 3 和 8。它们的二进制表示分别是：

3: 0011
8: 1000

这两个数有 3 个二进制位是不相同的，因此它们的汉明距离是 3。

代码

public class AlgoCasts {

  int numberOfOne(int n) {
    int count = 0;
    while (n != 0) {
      ++count;
      n &= (n - 1);
    }
    return count;
  }

  public int hammingDistance(int x, int y) {
    return numberOfOne(x ^ y);
  }

}

使用 z&(z-1) 去除 z 位级表示最低的那一位。

public int hammingDistance(int x, int y) {
    int z = x ^ y;
    int cnt = 0;
    while(z != 0) {
        if ((z & 1) == 1) cnt++;
        z = z >> 1;
    }
    return cnt;
}

可以使用 Integer.bitcount() 来统计 1 个的个数。

public int hammingDistance(int x, int y) {
    return Integer.bitCount(x ^ y);
}