Sunday, March 23, 2014

Count number of bits to be flipped to convert A to B

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/.
Problem
You 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