This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/count-number-of-bits-to-be-flipped-to-convert-a-to-b/.
ProblemYou are given two numbers A and B. Write a function to determine the number of bits need to be flipped to convert integer A to integer B.Example
Input: 73, 21 Output: 4 Representing numbers in bits : A = 1001001 B = 0010101 C = * *** C = 4
Solution
Method 1 - Counting the bits set after XORing 2 numbers
1. Calculate XOR of A and B. a_xor_b = A ^ B 2. Count the set bits in the above calculated XOR result. countSetBits(a_xor_b)
XOR of two number will have set bits only at those places where A differs from B.
Example:
A = 1001001 B = 0010101 a_xor_b = 1011100 No of bits need to flipped = set bit count in a_xor_b i.e. 4
To get the set bit count please see another post here.
Here is the basic code
public static int bitFlipRequired(int a, int b) { int count = 0; int c = a ^ b; count = countBitsSet(c); return count; }
We can short hand the above code :
public static int bitSwapRequired(int a, int b) { int count = 0; for (int c = a ^ b; c != 0; c = c >> 1) { count += c & 1; } return count; }
Thanks
References - geeksforgeeks,
0 comments:
Post a Comment