## Sunday, March 23, 2014

### 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,