Sunday, June 11, 2017

Count number of different bits in two Numbers

Problem:
Given two numbers, find how many bits are different in two numbers.
Or, another way to look at problem is - Determine number of bits required to convert num_1 to num_2.

num_1 = 1
num_2 = 0
Number of different bits = 1

num_1 = 11111
num_2 = 01110
Number of different bits = 2

Solution:

Basically we need to find at each position if the value of bit in two number is same or different. If they are different then increase the counter and do the same for all subsequent bits.

It might not be very obvious from the problem but there is a bit operator which exactly finds out how different two inputs are. Let's apply XOR operator and see how it behaves:

1 ^ 0 = 1
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 1 = 0

So notice that, when bits are same output is always 0. And when both bits are different then output is 1.

    11111
^  01110
-------------
    10001

So after taking XOR, we just need to count the number of 1's in the result.


Java Implementation

public static int countNumberOfDifferentBits(int a, int b){

       int xor = a ^ b;
       int count = 0;
       for(int i= xor; i!=0;){
            count += i & 1;
            i = i >> 1;
       }
}

1 comment: