**Launch your smart contract idea in just 4 days**

623 reads

by Gopi GorantalaMarch 6th, 2022

In this lesson, we find the number of positions where the bits are different for the given input.

In this question, we will find the number of positions at which the corresponding bits are different.

Given integers `x`

, `y`

finds the positions where the corresponding bits are different.

**Example 01:**

```
Input: x = 1, y = 8
Output: 2
Explanation:
1 (0 0 0 1)
8 (1 0 0 0)
↑ ↑
```

**Example 02:**

```
Input: x = 12, y = 15
Output: 2
Explanation:
12 (1 1 0 0)
15 (1 1 1 1)
↑ ↑
```

We solve this using shifting operation and then we move to solve it in a more optimal way.

This approach is better as it takes `O(1)`

time complexity. We shift the bits to left or right and then check if the bit is one or not.

We use the right shift operation, where each bit would have its turn to be shifted to the rightmost position.

Once shifted we use either modulo % (i.e., i % 2) or `&`

operation (i.e., i & 1).

**Hint:** you can check if a number does not equal 0 by the `^`

operator.

```
#include <iostream>
using namespace std;
void hammingDistance(int a, int b){
int xorVal = a ^ b;
int distance = 0;
while(xorVal ^ 0){
if(xorVal % 2 == 1){
distance += 1;
}
xorVal >>= 1;
}
cout << "Hamming Distance between two integers is " << distance << endl;
}
int main() {
int a = 1;
int b = 8;
hammingDistance(a, b);
return 0;
}
```

**Time complexity:** `O(1)`

. For a `32-bit`

integer, the algorithm would take at most 32 iterations.

**Space complexity:** `O(1)`

. Memory is constant irrespective of the input.

In the above approach, we shifted each bit one by one. So, is there a better approach in finding the hamming distance? Yes.

When we do & bit operation between number `n`

and `(n-1)`

, the rightmost bit of one in the original number `n`

would be cleared.

```
n = 40 => 00101000
n - 1 = 39 => 00100111
----------------------------------
(n & (n - 1)) = 32 => 00100000
----------------------------------
```

Based on the above idea, we can count the distance in 2 iterations rather than all the shifting iterations we did earlier. Let’s see the code in action.

```
#include <iostream>
using namespace std;
int hammingDistance(int a, int b){
int xorVal = a ^ b;
int distance = 0;
while (xorVal != 0) {
distance += 1;
xorVal &= ( xorVal - 1); // equals to `xorVal = xorVal & ( xorVal - 1);`
}
return distance;
}
int main() {
int a = 1;
int b = 8;
cout << "Hamming Distance between two integers is " << hammingDistance(a, b);
return 0;
}
```

**Time complexity:** `O(1)`

. The input size of the `integer`

is fixed, we have a constant time complexity.

**Space complexity:** `O(1)`

. Memory is constant irrespective of the input.

*First Published here*

L O A D I N G

. . . comments & more!

. . . comments & more!