• # 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 */
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).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.