Bit Manipulation

Number of bit to be flipped to convert one number to another.

by

Objec­tive:  Given two numbers x and y. write an algorithm to find the number of bits which are to be flipped to convert number x to y.

Example

x = 10, Y = 20
x = 0 1 0 1 0, y = 1 0 1 0 0
So if we need to convert x to y then a) turn on the bits at 2nd and 5th position b) turn off the bits at 1st and 4th position.
Output: 4

Approach:

Let’s observe the XOR table

X Y Result
0 0 0
0 1 1
1 0 1
1 1 0
  • So as we can see that XOR of two numbers will set the bit in result if the bit is set in either in X or Y, not in both.
  • Calculate z = x XOR y.
  • Count the number of set bits in z. this will be the final answer.

Code:


public class CountBitsToBeFlipped {
public int calculate(int x, int y){
//xor of 2 numbers, the bit will be in the result if that bit is set in either x or y
//so by doing xor we will get all the bits which needs to be flipped to convert x to y
int z = x ^ y;
int count =0;
while (z>0){
count += z & 1;
z >>= 1;
}
return count;
}
public static void main(String[] args) {
CountBitsToBeFlipped c = new CountBitsToBeFlipped();
int x = 10;
int y = 20;
System.out.println("Number of bit needs to be flipped to convert " + x + " to " + y + " are: " + c.calculate(x,y));
}
}

view raw

CountBitsToBeFlipped.java

hosted with ❤ by GitHub


Output:

Number of bit needs to be flipped to convert 10 to 20 are: 4

Related Posts: