Question 461. Hamming Distance
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 < 2^31.
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
With golang, bit operation
1、get the different bits with XOR operations
1 (0 0 0 1)
xor
4 (0 1 0 0)
==>
(0101)
now, only need count the number of '1' bits
2、count
first, we need a bitmask like (0 0 0 1), and left shift it to compare each bit of your xor result (in the previous step), if "bitmask AND xor" is not 0, counter increase 1
then, stop left shift when bitmask overflowed (the value of int is a negative number, unsigned int is 0, so, just check bitmask is more than 0 or not).
Example:
(1 0 1 0)
AND
(0 0 0 1)
==>
0
left shift
(1 0 1 0)
AND
(0 0 1 0)
==>
is not 0, counter++
left shift
(1 0 1 0)
AND
(0 1 0 0)
==>
0
......
bitmask overflowed : (0 0 0 0) or (1 1 1 1)
stop
result : 2
Code:
func hammingDistance(x int, y int) int {
count := 0
xor := x ^ y /* get xor bits */
/* when overflow, exit loop */
for bitMask := 1; bitMask > 0; bitMask <<= 1 {
if bitMask & xor != 0 { /* find bit 1 */
count++
}
}
return count
}
Complexity Analysis:

Time complexity : O(1).
The times of for loop is const, so the time complexity is O(1). 
Space complexity : O(1).
We only need constant memory to store 3 local variables, so the space complexity is O(1).