Objective: 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)); | |
| } | |
| } |
Output:
Number of bit needs to be flipped to convert 10 to 20 are: 4