Hamming Distance
Problem
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.
Solution
public class Solution {
public int hammingDistance(int x, int y) {
int diff = x ^ y, count = 0;
while (diff != 0) {
count += diff & 1;
diff = diff >> 1;
}
return count;
}
}
One line built-in ;)
public class Solution {
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
}
Analysis
This problem asks to count the difference of bits in each position
We first use ^
(bitwise XOR) to get the difference in bit format
Then we need to count how many 1
are there to get the result
We can either use built-in function Integer.bitCount()
or implement it by ourselves
Remember the difference between |
bitwise or, &
bitwise and, and ^
bitwise XOR
In bit operations, |
returns 1 if there is just one or more 1 in the bit position&
returns 1 if both bit positions have 1^
returns 1 if values in two positions are different