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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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