Redirecting to
NADOS


  Prev   Next

FLIP BITS TO CONVERT A TO B







Pearls don't lie on the seashore. If you want one, you must dive for it.

FLIP BITS TO CONVERT A TO B

Hello coder. Get ready to begin with a new problem, "Flip Bits to convert A to B" in this article.


We suggest you go through the problem's outline first to get a feel of the question.


Important Link : Problem link, Solution video

PROBLEM DISCUSSION

The problem here deals with calculating the number of bits that are needed to be flipped to convert an integer A to B. Flipping a bit means updating a bit with value 0 to 1 or to update a bit with value 1 to 0.

For example:


57 = 0 1 1 1 0 0 1

76 =1 0 0 1 1 0 0


So we need to flip bits at positions 0, 1, 2, 4 and 6 (order is considered from left to right) to convert 57 to 76. Hence total 5 operations will be performed.

APPROACH

  • The problem can be solved by taking the XOR of the two numbers. As we know that XOR gives a set bit at positions where there is an odd number of 1s, this is exactly what we desired, we need the positions that needed to be flipped and by performing XOR operation we achieved the task.
  • Now all that is left is to count the number of set bits in the XOR integer by using Kerninghams algorithm to count the number of set bits.

import java.io.*; import java.util.*; public class Main { public static void main(String[] args){ Scanner scn = new Scanner(System.in); int a = scn.nextInt(); int b = scn.nextInt(); int flipped=a^b; int count=0; while(flipped!=0){ int rsb=(flipped& -flipped); flipped-=rsb; count++; } System.out.println(count); } }
java; true";
TIME & SPACE COMPLEXITY
TIME COMPLEXITY- O(k)

The time complexity for the function is proportional to the number of set bits in the XOR integer.

SPACE COMPLEXITY- O(1)

The space complexity for the function is constant.


Reader, this was quite an easy problem. In case you have any doubts in it, we recommend you to watch its solution video.


We'll see you in the next problem. Have a great day!

Bit Manipulation
Author: Shreeya Gupta
 
Run
Id Name