**Solution with discussion** https://discuss.leetcode.com/topic/73553/python-solution-with-detailed-explanation

**Hamming Distance** https://leetcode.com/problems/hamming-distance/

**Mask based linear time algorithm**

- Use a mask 1 and move it i times for each index. Use it to extract bit i for x and y and xor to update count.
- Time complexity: O(32)

```
class Solution(object):
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
mask, cnt = 1, 0
for i in range(31):
if ((mask << i)&x) ^ ((mask << i)&y):
cnt += 1
return cnt
```

**Using n&(n-1) trick**

- xor x and y.
- n&(n-1) unsets the leftmost bit. Use it to count 1s.
- Time complexity: O(hamming distance)

```
class Solution(object):
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
xor, cnt = x^y, 0
while xor:
cnt, xor = cnt+1, xor&(xor-1)
return cnt
```