## Problem Statement

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers `x`

and `y`

, calculate the Hamming distance.

**Note:**

0 ≤ `x`

, `y`

< 2^{31}.

## Sample Test Cases

Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ The above arrows point to positions where the corresponding bits are different.

## Problem Solution

1)We find XOR of x and y , **Why**?

Because the xor makes the bit to set if the bits bits are different ie, 1^0 or 0^1 gives the result 1,

Now if we count number of bits which are set int result of XOR gives the hamming distance.

2)How to find if some **i**th bit is set?

To find if **i**th bit a number N is set

(i) (N & (1<<i)) >0

(ii) ((N>>i) & 1) ==1

any of the above can be used to check the status of **i**th bit.

If we find that if any bit is set we increase count.

Hence we start with 0th bit and shift right 1 bit each time and check the status of each bit.

## Complexity Analysis

Time Complexity: O(1) since we always need to iterate from 0 to 31 (int).

Space Complexity: O(1) does not require any data structure to store anything.

## Code Implementation

#include <bits/stdc++.h> using namespace std; int hammingDistance(int x, int y) { int xr = x^y; int hd = 0,setBit=1; for (int i = 0;i<31;i++) { if ((xr & setBit)> 0) hd++; setBit <<= 1; } return hd; } int main() { cout <<hammingDistance(3,4)<< endl; return 0; }