# Solution by Na2a

• 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 = 12^4 + 02^3 + 12^2 + 12^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)).

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