461. 汉明距离
题目描述
输入两个非负整数 x 和 y。
把它们写成二进制并按位对齐，统计有多少个位上两者取值不同，这个数量称为汉明距离。
返回 x 与 y 的汉明距离。
示例 1
输入：x = 1, y = 4 输出：2
解释：1 = 0001，4 = 0100，第 0 位和第 2 位不同。
示例 2
输入：x = 3, y = 1 输出：1
解释：3 = 11，1 = 01，只有第 1 位不同。
数据范围
0 <= x, y <= 2^31 - 1
解题思路
对应位不同的位置，恰好是 x ^ y 中为 1 的位置。所以先算 s = x ^ y，再数 s 里有几个 1。数 1 时用 s &= s - 1：s - 1 会把最低位的 1 变成 0、把它右边的 0 都变成 1，与 s 相与后正好去掉最低位的 1，循环次数等于 1 的个数。
为什么正确
cnt + （s 中 1 的个数）始终等于 x 与 y 的汉明距离。
复杂度分析
时间 O(k)，k 为不同位的个数（最多 31）；空间 O(1)。
易错点
逐位比较时容易只比较到较短数的位数；直接对 x ^ y 计数可以避免这个问题。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
s = x ^ y
cnt = 0
while s:
s &= s - 1
cnt += 1
return cntclass Solution {
public int hammingDistance(int x, int y) {
int s = x ^ y;
int cnt = 0;
while (s != 0) {
s &= s - 1;
cnt++;
}
return cnt;
}
}class Solution {
public:
int hammingDistance(int x, int y) {
int s = x ^ y;
int cnt = 0;
while (s) {
s &= s - 1;
cnt++;
}
return cnt;
}
};func hammingDistance(x int, y int) int {
s := x ^ y
cnt := 0
for s != 0 {
s &= s - 1
cnt++
}
return cnt
}var hammingDistance = function(x, y) {
let s = x ^ y;
let cnt = 0;
while (s !== 0) {
s &= s - 1;
cnt++;
}
return cnt;
};function hammingDistance(x: number, y: number): number {
let s = x ^ y;
let cnt = 0;
while (s !== 0) {
s &= s - 1;
cnt++;
}
return cnt;
}