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.

A bit flip of a number x is choosing a bit in the binary representation of x and flipping it from either 0 to 1 or 1 to 0.

For example, for x = 7, the binary representation is 111 and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get 110, flip the second bit from the right to get 101, flip the fifth bit from the right (a leading zero) to get 10111, etc.

Given two integers start and goal, return the minimum number of bit flips to convert start to goal.

Examples

Example 1:

1
2
3
4
5
6
7
8
9
Input: start = 73, goal = 21

Output: 4

Representing numbers in bits :
start  = 1 0 0 1 0 0 1
goal   = 0 0 1 0 1 0 1
diff  =  *   * * *
Hence output is 4.

Solution

Method 1 - Counting the bits set after XORing 2 numbers

We can do following:

Calculate XOR of A and B. a_xor_b = A ^ B
Count the set bits in the above calculated XOR result.

XOR of two number will have set bits only at those places where A differs from B.

Lets look at the example:

1
2
3
4
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 Number of 1 Bits. Here is the basic code

1
2
3
4
5
6
public int minBitFlips(int a, int b) {
	int count = 0;
	int c = a ^ b;
	count = countBitsSet(c);
	return count;
}

Code

1
2

##### Java

1
2
3
4
5
6
7
8
9
public int minBitFlips(int a, int b) {
	int count = 0;
	
	for (int c = a ^ b; c != 0; c = c >> 1) {
		count += c & 1;
	}

	return count;
}

Complexity

⏰ Time complexity: O(n) where n is number of bits in the xor-red number.
🧺 Space complexity: O(1)

Problem#

Examples#

Solution#

Method 1 - Counting the bits set after XORing 2 numbers#

Code#

Complexity#