Count Number of Bits to Flip to Convert A to B - Visualization

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given two integers a and b, your task is to determine how many bits need to be flipped in a to convert it into b. Each flip changes a bit from 0 to 1 or from 1 to 0.

The goal is to count the number of differing bits between their binary representations.

Examples❯

a b Output Description
10 20 4 Binary of 10 is 1010, 20 is 10100; they differ in 4 bits
7 10 3 Binary of 7 is 0111, 10 is 1010; differing bits at positions 1, 2, and 3
0 0 0 Both are 0; no bits to flip
0 15 4 Binary of 15 is 1111; need to flip 4 bits from 0
1023 0 10 Binary of 1023 is 10 ones (1111111111); all 10 bits differ from 0
255 0 8 Binary of 255 is 11111111; flipping all 8 bits to get 0
1 1 0 Both are 1 (0001); no flips needed
"" 5 2 Empty input treated as 0; binary of 5 is 0101; two bits differ
31 14 3 Binary of 31 is 11111; 14 is 01110; 3 bit flips needed
4294967295 0 32 Max 32-bit unsigned int vs 0; all 32 bits must flip

Solution❯

Understanding the Problem

We are given two integers a and b. Our task is to find out how many bits are different between their binary representations. In other words, we need to count how many bits we need to flip in a so that it becomes equal to b.

Each bit can be either 0 or 1. A bit flip means changing a 0 to a 1, or a 1 to a 0. This problem is a great exercise in using bitwise operations, especially XOR, to compare bits.

Step-by-Step Solution with Example

Step 1: Understand XOR (Exclusive OR)

XOR is a bitwise operation that compares each corresponding bit of two numbers. It returns 1 if the bits are different and 0 if they are the same.

For example:


a = 10  -> binary: 1010
b = 20  -> binary: 10100

To make bit lengths equal:
a = 01010
b = 10100

XOR:
    01010
  ^ 10100
  --------
    11110

The result is 11110 in binary, which is 30 in decimal. This result has 4 bits set to 1, which means we need to flip 4 bits in a to get b.

Step 2: Initialize a counter

We’ll use a counter variable, initially set to 0, to keep track of how many 1’s are in the XOR result.

Step 3: Loop through each bit of the XOR result

We check the last bit of the XOR result using xor & 1. If it’s 1, we increment the counter. Then we right shift the number using xor >>= 1 to move to the next bit. We continue until the XOR result becomes 0.

Step 4: Return the counter

The counter now holds the number of differing bits between a and b.

Edge Cases

  • When a and b are equal: XOR result will be 0. Hence, 0 bits need to be flipped.
  • When either a or b is 0: The number of flips is equal to the number of 1's in the other number's binary representation.
  • Very large numbers: The algorithm still works efficiently as it only processes the number of bits set in the XOR result.

Final Thoughts

This problem is a classic use of the XOR operation to compare bit patterns. It helps build intuition around binary representation and how bitwise operations work. It’s also efficient, as it doesn’t need to convert numbers to strings or use arrays — everything is done using bitwise math.

Understanding how binary numbers differ and using simple looping allows us to solve this problem in a clean and optimized way, which is essential for both interviews and real-world programming.

Algorithm Steps❯

  1. Compute the XOR of a and b. This highlights all bit positions where the bits differ.
  2. Initialize a counter to 0.
  3. Loop while the XOR result is greater than 0:
    • Increment the counter if the least significant bit (LSB) is 1 (i.e., xor & 1).
    • Right shift the XOR result by 1 to move to the next bit.
  4. Return the counter as the final answer.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int countBitsToFlip(int a, int b) {
    int xor = a ^ b;
    int count = 0;
    while (xor) {
        count += (xor & 1);
        xor >>= 1;
    }
    return count;
}

int main() {
    int a = 29;  // Example value
    int b = 15;  // Example value
    printf("Number of bits to flip from %d to %d is: %d\n", a, b, countBitsToFlip(a, b));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(k)The algorithm computes the XOR of a and b, then checks each bit of the result. In the best case, a and b are equal, so the XOR result is 0 and the loop exits immediately. However, checking if the XOR is non-zero still takes constant time for fixed-width integers. So for integers with k bits, the complexity is O(k).
Average CaseO(k)The loop runs for the number of bits set in the XOR result. On average, about half the bits may differ, leading to O(k) operations for k-bit integers.
Worst CaseO(k)In the worst case, all k bits in the XOR result are set (e.g., a = 0 and b = all 1s), so the loop runs k times — once per bit. Thus, the worst-case time complexity is O(k).

Space Complexity❯

O(1)

Explanation: Only a constant amount of extra space is used: a counter and the XOR value. No additional space is required proportional to the input size.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...