First, by calculating `x ^ y`

, we can get the num whose bit representations shows `1`

only when the bits in `x`

and `y`

are different. That is to say, our task is count a number of `1`

in `x ^ y`

.

How we can check the count of digits `1`

of some bit representation?

Of course we can check whether each digit is `1`

while shifting to right one by one. But there is a faster solution for this problem. I saw the following technique in Elements in programming inteview.

let's say a bit representation is `X`

= `1001000`

.

Then consider `X - 1`

= `1000111`

Then try calculate `X & X-1`

= `1000000`

.

What happened here? We can reset the most right `1`

occurrence from `X`

without checking rightmost three `0`

digits! In this way, we can speed up the iteration to `O(n)`

while n is the occurrence of `1`

in `X`

, not the length of digit of `X`

. (Of course, the worst case time complexity is the same but practically this is much more efficient)

```
func hammingDistance(x int, y int) int {
xor := x ^ y
res := 0
for xor != 0 {
xor = xor & (xor - 1)
res++
}
return res
}
```