The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, calculate the Hamming distance.
- Note:
0 ≤ x, y < 231.
Example:
Input: x = 1, y = 4
Output: 2
Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
The above arrows point to positions where the corresponding bits are different.
C Solution 1:
int hammingDistance(int x, int y) {
int num = x ^ y;
int res = 0;
while (num) {
res += num & 1;
num >>= 1;
}
return res;
}
C Solution 2:
int hammingDistance(int x, int y) {
int diff = x ^ y;
int res = 0;
while (diff) {
res++;
diff &= diff - 1;
}
return res;
}
C Solution 3:
int hammingDistance(int x, int y) {
int res = 0;
while (x || y) {
res += ((x & 1) + (y & 1)) == 1;
x >>= 1;
y >>= 1;
}
return res;
}
Summary:
- Solution 2 is better than Solution 1 because of time complexity.
- Solution 2 maybe better than Solution 3 because it's clearer.
LeetCode: 461. Hamming Distance
近期评论