Count number of bits to be flipped to convert A to B. OR
Find number of Bit swaps required to convert one integer to another OR
Given two integers A & B. Determine how many bits required to convert A to B.
Given two number A and B, Write an algorithm to count the number of bit flips required to convert A to B
Let's see what is the input and expected output for better understanding,
Case 1:
Input A: 6 (Binary equivalent of 6: 0 1 1 0 )
Input B: 8 (Binary equivalent of 8: 1 0 0 0 )
Output: Number of bits that need to be changed in A to convert it to B is : 3
Explanation: (From Right, For number 6,
Bit at position 0 is 0, which is same in both number,
Bit at position 1 is 1, which needs to be unset to match it to number B,
Bit at position 2 is 1, which needs to be unset to match it to number B,
Bit at position 3 is 0, which needs to be set to match it to number B)
Case 2:
Input A: 9 (Binary equivalent of 9: 0 1 0 0 )
Input B: 2 (Binary equivalent of 2: 0 0 1 0 )
Output: Number of bits that need to be changed in A to convert it to B is : 2
Explanation: (From Right, For number 9,
Bit at position 0 is 0, which is same in both number,
Bit at position 1 is 0, which needs to be set to match it to number B,
Bit at position 2 is 1, which needs to be unset to match it to number B,
Bit at position 3 is 0, which is same in both number)
Algorithm
If you are not aware of how to count number of SET bits in a number, I suggest to please look into this post first: Count number of Set Bits in Integer
Approach 1:
In this apprach, we will compare each bits of both number A and B and see if bits on position 0,1,2...n is same for both number, if yes, then we will not count it but if they are different then that is the bit that need to be flipped to match to number B.
When we do logical AND between number and 1 (A & 1), then result will be 1, if right most bit is set in A.
We will do logical AND for both numbers by 1 [(A & 1), (B & 1)] and check the result,
If resulting number for both number is same, it means both numbers have same bit in last position.
If resulting number for both number is different, it means bit at last position is different and we can increment our diffCount.
So we will count the differences in bits in both number. Lets see with example.
Approach 2 (Optimized approach)
In this approach,
- In first step, we need to Find number of bits that are different in both number A and B and discard the bits that are same.
- Once we identify resulting number that contains bits difference in A and B, we can count the number of SET bits in resulting number and that will be number of bits required to be flipped to convert A to B.
Example:
0 1 1 0 = 6
XOR 0 0 1 0 = 2
--------------
0 1 0 0 = 4
Count the number of SET bits present in number 4 and that is the number of Bits that need to be fipped to convert A to B.
For counting how to find number of bits present in a number.
We have covered detailed post on: How to count number of bits set in number
Count number of Bits to be flipped to convert A to B Java Program
package javabypatel;
public class CountNumberOfBitsToBeFlippedToConvertAToB {
public static void main(String[] args) {
int a = 6;
int b = 8;
System.out.println(countBitToFlipToConvertAToB(a,b));
}
private static int countBitToFlipToConvertAToB(int a, int b){
//Find number of bits that differ between A and B.
int c = a ^ b;
//Count number of SET bits in "c"
int count=0;
while(c!=0){
c = c &(c-1);
count++;
}
return count;
}
}
You may also like to see
Compress a given string in-place and with constant extra space.
Check whether a given string is an interleaving of String 1 and String 2.
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord.
Serialize and Deserialize a Binary Tree
Advanced Multithreading Interview Questions In Java
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
Post a Comment