Table of Contents

## Problem Statement

In this problem, we are given two integers, A and B, and the goal is to find the hamming distance between the given integers. The integers are greater that/equal to **0 **and less than **2**^{31 }

### Example

First Integer = 5 , Second Integer = 2

3

First Integer = 4 , Second Integer = 5

1

## Approach(Counting Bit by Bit)

The first thing which is very clear is that since we need to find the number of bits where the corresponding bit values in the given two numbers are different, we need to do bitwise-XOR of the given integers. The results that XOR will produce in an individual bit position would be ‘1’ if the **bits in the two integers at that position were different**. Otherwise, the XOR will produce a ‘0’ at that position.

Now that we have deduced this part, the only follow-up remaining is to efficiently find out the numbers of bits which are **set **(bit value = ‘1’) in the bitwise XOR of the given integers. In order to count this value, we loop for every bit (from **0** to **30**) and check whether is set in the XOR value or not.

### Algorithm

- Store the bitwise XOR of the two integers in a variable –
*xor_* - Initialize
*cnt*= 0 to store the result - For every
*i = 0*and*i < 31:*- If the ‘
*ith*‘ bit is set in*xor_*- Increment
*cnt: cnt++*

- Increment
- Increment
*i*

- If the ‘
- Return
*cnt*

### Implementation of Hamming Distance Leetcode Solution

#### C++ Program

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

#### Java Program

class hamming_distance{ static int hammingDistance(int x , int y){ int xor_ = x ^ y , cnt = 0; for(int i = 0 ; i < 31 ; i++){ if(((1 << i) & xor_) > 0) cnt++; } return cnt; } public static void main(String args[]){ int x = 5 , y = 2; System.out.println(hammingDistance(x , y)); } }

3

### Complexity Analysis of Hamming Distance Leetcode Solution

#### Time Complexity

**O(1)** as we perform a constant number of operations regardless of the input.

#### Space complexity

**O(1)** as we use constant memory space.

## Approach(Counting Bits efficiently – Kernighan’s Algorithm)

The first steps stays the same, which is to find out the bitwise XOR of the teo given numbers. However, we count the number of set bits in their XOR efficiently using the Kernighan’s Algorithm, which is based on the idea:

When we perform ‘

bitwise &‘ operation between an integer‘i’and‘i – 1’, its right most set bit isunset.

Let us follow the above idea through an example. Consider N = 36(100100). Now if we ‘&’ it with N – 1, we’d get:

N & (N – 1) = (36 & 35) = (100100 & 100011) = (100000) which clearly **unsets** the right most bit(at position 2 from the right). Similarly, we can further write:

N & (N – 1) = (32 & 31) = (100000 & 011111) = 000000 which again unsets the rightmost set bit at position 5 from the right. The process can’t be continued further as the integer N has become zero.

This beautiful idea proves to be very useful to **count set bits** in an integer, as we only need to just **iterate** as many times as **there are set bits** in a given integer.

### Algorithm

- Store the bitwise XOR of the two integers in a variable –
*xor_* - Initialise
*cnt*= 0 to store the result - While
*xor_*is greater than*0*:- Increment
*cnt: cnt++* - set xor_ = xor_ & (xor_ – 1)

- Increment
- Return
*cnt*

### Implementation of Hamming Distance Leetcode Solution

#### C++ Program

#include <bits/stdc++.h> using namespace std; int hammingDistance(int x , int y){ int xor_ = x ^ y , cnt = 0; while(xor_ > 0){ xor_ = (xor_ & (xor_ - 1)); ++cnt; } return cnt; } int main(){ int x = 5 , y = 2; cout << hammingDistance(x , y) << endl; return 0; }

#### Java Program

class hamming_distance{ static int hammingDistance(int x , int y){ int xor_ = x ^ y; int cnt = 0; while(xor_ > 0){ xor_ = (xor_ & (xor_ - 1)); ++cnt; } return cnt; } public static void main(String args[]){ int x = 5 , y = 2; System.out.println(hammingDistance(x , y)); } }

3

### Complexity Analysis of Hamming Distance Leetcode Solution

#### Time Complexity

**O(1)** as we perform a constant number of operations regardless of the input.

#### Space complexity

**O(1)** as we use constant memory space.