Log inSign up
easyGeeksforGeeksNot Started

Count Bits to Flip to Convert A to B

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on GeeksforGeeks
Lesson

Problem Statement

Given two positive integers a and b, determine the minimum number of bit flips required to convert a into b.

A bit flip changes a 0 to a 1 or a 1 to a 0 at any specific bit position.

Example 1 · Example 1: Converting 10 to 20:

Input: a = 10, b = 20
Output: 4
Explanation: 10 in binary is 01010, 20 is 10100. They differ at 4 bit positions (positions 1, 2, 3, 4). Thus 4 flips are needed.

Example 2 · Example 2: Converting 20 to 25:

Input: a = 20, b = 25
Output: 3
Explanation: 20 is 10100_2, 25 is 11001_2. Differing bit positions: 0, 2, 3. Total flips: 3.

Constraints:

  • 1 <= a, b <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Recognize that bit differences between two numbers are isolated via XOR.
  • Implement Brian Kernighan's algorithm for popcount calculation.
  • Understand the equivalence between bit flips and Hamming distance.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Count minimum bit flips to transform one integer to another.
  • Calculate Hamming distance between two values.

Algorithmic Decision Tree:

  • Compute diff = a ^ b.
  • Count set bits in diff using Brian Kernighan's algorithm.

Connected Patterns:

Count Set BitsHamming DistanceNumber of 1 Bits

1. 32-Bit Fixed Comparison

Intuition

Loop through indices 0 to 31. Extract bitA = (a >> i) & 1 and bitB = (b >> i) & 1. If bitA != bitB, increment flipCount.

When to apply: Baseline comparison.

Algorithm

  1. Step 1: Initialize count = 0.
  2. Step 2: Loop i from 0 to 31.
  3. Step 3: If ((a >> i) & 1) != ((b >> i) & 1), increment count.
  4. Step 4: Return count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int countFlipsBrute(int a, int b) {
6 int count = 0;
7 for (int i = 0; i < 32; ++i) {
8 if (((a >> i) & 1) != ((b >> i) & 1)) {
9 count++;
10 }
11 }
12 return count;
13}
14
15int main() {
16 cout << "Brute (10, 20): " << countFlipsBrute(10, 20) << endl; // 4
17 cout << "Brute (20, 25): " << countFlipsBrute(20, 25) << endl; // 3
18 return 0;
19}

Time & Space Complexity

  • Time complexity: O(32) = O(1)
  • Space complexity: O(1)

2. XOR with Right Shift Scan

Intuition

Compute diff = a ^ b. In a loop while diff > 0, add diff & 1 to count and right shift diff >>= 1. This terminates as soon as the most significant set bit in diff is processed.

When to apply: When avoiding comparisons on identical high-order zero bits.

Algorithm

  1. Step 1: Compute diff = a ^ b.
  2. Step 2: Initialize count = 0.
  3. Step 3: While diff > 0, count += diff & 1, and diff >>= 1.
  4. Step 4: Return count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int countFlipsShift(int a, int b) {
6 int diff = a ^ b;
7 int count = 0;
8 while (diff > 0) {
9 count += (diff & 1);
10 diff >>= 1;
11 }
12 return count;
13}
14
15int main() {
16 cout << "Better (10, 20): " << countFlipsShift(10, 20) << endl; // 4
17 return 0;
18}

Time & Space Complexity

  • Time complexity: O(log(a ^ b))
  • Space complexity: O(1)

3. Brian Kernighan's Algorithm on XOR

Intuition

Calculate diff = a ^ b. Use Brian Kernighan's bit-clearing trick: diff &= (diff - 1). In each iteration, this directly zeroes the rightmost set bit, skipping all intermediate zero bits. Loop repeats exactly k times, where k is the number of bit flips required.

When to apply: Optimal for production and competitive programming: runs strictly in O(k) steps.

Algorithm

  1. Step 1: Compute diff = a ^ b.
  2. Step 2: Initialize count = 0.
  3. Step 3: While diff != 0, diff &= (diff - 1), and increment count.
  4. Step 4: Return count.

Kernighan XOR Popcount Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Step 1: Compute diff = a ^ b = 10 ^ 20 = 30 (binary 11110)
Visual state
Values and pointers at this exact step
pointers
S
11110
0
↑ initial diff
Check / comparison
diff = 30 (11110_2)
Decision / next transition
diff > 0, proceed with Kernighan's loop.
Why this step matters

Step 1: Compute diff = a ^ b = 10 ^ 20 = 30 (binary 11110). flipCount = 0.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 int countBitsFlip(int a, int b) {
8 int diff = a ^ b;
9 int count = 0;
10 while (diff != 0) {
11 diff &= (diff - 1);
12 count++;
13 }
14 return count;
15 }
16};
17
18int main() {
19 Solution sol;
20 cout << "Optimal (10, 20): " << sol.countBitsFlip(10, 20) << endl; // 4
21 cout << "Optimal (20, 25): " << sol.countBitsFlip(20, 25) << endl; // 3
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(k) where k is the number of flipped bits (at most 32)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Compare All 32 Bit PositionsO(32) = O(1)O(1)Loop through bit positions 0 to 31, comparing ((a >> i) & 1) != ((b >> i) & 1).Fixed 32-iteration loop.
2.Better — XOR with Shift & AddO(log(a ^ b))O(1)Compute diff = a ^ b. While diff > 0, add (diff & 1) to count and shift diff >>= 1.Linear shifting until MSB.
3.Optimal — Brian Kernighan's Algorithm on XOROptimalO(k) where k is the number of flipped bitsO(1)Compute diff = a ^ b. Repeatedly clear the lowest set bit: diff &= (diff - 1), incrementing flipCount.Only the set bits are processed.

Common Pitfalls & Crucial Edge Cases

Counting bits in a and b separately

The total flips is NOT popcount(a) - popcount(b). Different bit positions require flipping even if popcounts match.

Looping 32 times when fewer flips are needed

A standard loop over all 32 bits works, but Brian Kernighan's algorithm is cleaner and faster in practice.

Signed shift pitfall

Using arithmetic right shift >> instead of logical right shift >>> can propagate sign bits on negative values.

Crucial Edge Cases to Validate:

  • a == b — Numbers are identical, so a ^ b = 0; requires 0 flips.
  • a is the bitwise NOT of b (~b) — Every single bit differs; requires 32 flips.
  • One number is 0 — Result is the popcount (number of set bits) of the other number.
  • Negative numbers — In languages with signed integers, ensure sign bit differences are handled properly.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Name-drop 'Hamming Distance' and 'Brian Kernighan's Algorithm' to demonstrate standard computer science vocabulary.
  2. Discuss the built-in compiler intrinsics (e.g., __builtin_popcount in GCC/Clang, Integer.bitCount in Java) after explaining the manual algorithm.
  3. Mention hardware-level POPCNT instruction support for modern x86/ARM architectures.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is computing a ^ b the first step in counting bits to flip from a to b?

2.What algorithm counts the set bits in x = a ^ b in time proportional only to the number of set bits?

3.What is this problem known as in information theory and coding theory?

Back to DSA Sheet