First idea that comes to mind is to take all positions and check if bits

at corresponding positions are different.

#### Approach 1. Naive

**Intuition:**

Given two numbers A and B. We can take the lowest bit of A and the lowest bit of B

and check if they are equal. Then, we just delete these two bits.

**Getting the lowest bit:**

If we represent a number in binary system, we will have sum of some powers of two.

For example, let's consider 22. It's binary representation is 10110, so

22 = 1*2^4 + 0*2^3 + 1*2^2 + 1*2^1 + 0*2^1. As you can see, the lowest bit of any

number defines a parity of this number. That is, odd numbers will have 1 as the lowest bit,

even numbers will have 0.

**Removing the lowest bits:**

Let's take 22 again. It's binary representation is 10110. Now, let's remove last

(lowest) bit. It becomes 1011 which is 11. Here's the trick: removing the

lowest bit is same as diving by 2. If number is odd, just round it down, so 23

without the last bit is also 11.

**Algorithm:** While either of number is positive, just take the lowest bits,

compare them until we will finish with all positions.

```
class Solution {
public:
// getting the lowest bit
int getLowestBit(int x) {
return x % 2;
}
int removeLowestBit(int x) {
return x / 2;
}
int hammingDistance(int x, int y) {
int result = 0;
while (x > 0 or y > 0) {
int bit_x = getLowestBit(x);
int bit_y = getLowestBit(y);
if (bit_x != bit_y)
result++;
x = removeLowestBit(x);
y = removeLowestBit(y);
}
return result;
}
};
```

**Complexity Analysis:**

Time complexity: O(log2(max(A, B))).

If we can just iterate through all

positions (bits), this should work in $$O(numberOfPositions)$$. And we know that

decimal number N will have O(log2(N)) bits in binary representation. So solution

will be O(log(max(A, B))).

#### Approach 2. Bit operations

**Intuition:**

What does the XOR operation do? For each position in binary representation,

A xor B will have 1 if bits in corresponding positions differ. That's what we need.

Answer for this problem will be number of ones in A xor B.

**Algorithm:** Just find A xor B and count number of bits in it. In C++, that

would be pretty short.

```
class Solution {
public:
int hammingDistance(int x, int y) {
return __builtin_popcount(x ^ y);
}
};
```

**Complexity Analysis:**

Time complexity: O(log2(max(A, B))).

XOR operation works in O(1), although counting number of ones will be O(log2(N)).