This post is completed by 1 user

  • 1
 Add to List
Beginner

242. Find the Bit Flips Needed: Convert One Binary Number to Another

Objec­tive:  Given two numbers x and y. write an algorithm to find the number of bits that are to be flipped to convert the 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 1stand 4thposition.
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 the result if the bit is set in either 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.

Output:

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

Related Problems: