461. Hamming Distance

  • 70.8%

https://leetcode.com/problems/hamming-distance/?tab=Description

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.

1
2
3
4
5
6
7
8
9
10
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.


方法一:

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int hammingDistance(int x, int y) {
int res = 0;
int z = x ^ y;
while(z){
res++;
z = z & (z-1);
}
return res;
}
};

https://discuss.leetcode.com/topic/72236/my-c-solution-using-bit-manipulation

My C++ solution using bit manipulation

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int hammingDistance(int x, int y) {
int dist = 0, n = x ^ y;
while (n) {
++dist;
n &= n - 1;
}
return dist;
}
};

https://discuss.leetcode.com/topic/72288/python-1-line-49ms

Python 1 line 49ms

1
2
3
4
5
6
7
8
class Solution(object):
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
return bin(x^y).count('1')

my code:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int hammingDistance(int x, int y) {
int z = x ^ y;
int res = 0;
while(z){
if(z&1) res++;
z >>= 1;
}
return res;
}
};

https://discuss.leetcode.com/topic/72093/java-1-line-solution-d

Java 1 Line Solution :D

What does come to your mind first when you see this sentence “corresponding bits are different”? Yes, XOR! Also, do not forget there is a decent function Java provided: Integer.bitCount() ~~~

1
2
3
4
5
public class Solution {
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
}
谢谢你,可爱的朋友。