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,

See also