Minimum Bit Flips to Convert Number | Bit Manipulation

This chapter explores how to find the minimum number of bit flips required to transform one positive integer into another. We will examine the core bitwise operations that reveal differing bit positions, evaluate naive vs. optimal bit-counting approaches, and analyze the underlying time and space complexities.

1. Problem Statement: Understanding Bit Flips

We are given two positive integers, start and goal (both inclusive of zero, with no negative numbers). Our objective is to determine how many individual bits must be flipped (changing 0 to 1 or 1 to 0) in the binary representation of start to precisely match the binary representation of goal.

Example 1: start = 10, goal = 7

• Binary of 10 (8 + 2): 1010
• Binary of 7 (4 + 2 + 1, padded to 4 bits): 0111

Let's compare the bits position by position from right to left:

In total, we must flip 3 bits.

Example 2: start = 3, goal = 4

• Binary of 3 (2 + 1): 0011 (four-bit representation)
• Binary of 4 (4): 0100 (four-bit representation)

Comparing position by position:

Total flips required: 3 bits.

2. Choosing the Right Tool: Why XOR?

When searching for differences between two binary numbers, we need a bitwise operator that can isolate mismatched bits. Let's analyze how standard bitwise operators behave:

Real-Life Analogy: The Difference Detector

Think of the XOR operator (^) as an automated quality-control inspector. If two assembly parts are identical (0 and 0, or 1 and 1), the inspector remains silent and outputs 0. But if there is a discrepancy between the two parts (0 and 1), the inspector sounds an alarm and outputs 1.

Thus, performing start ^ goal instantly flags every bit position that differs.

3. Step-by-Step Problem-Solving Framework

To solve the minimum bit flip problem, we break the procedure down into two straightforward phases:

1. Find Differences (XOR): Compute ans = start ^ goal. The resulting integer will contain 1 at every bit index that needs to be flipped.
2. Count Set Bits: Count how many 1s exist in ans. That total count is our final answer.

Now, the problem simplifies entirely to: Given the number 13, how many set bits (1s) does it have?

4. Approach 1: Fixed 32-Bit Traversal (Naive Check)

A straightforward way to count set bits in an integer is to iterate through all possible bit positions from 0 to 31 (since standard integers operate within 32 bits).

Checking the $i$-th Bit

To check whether the $i$-th bit is set in our ans, we use the left-shift bitmask technique:

if ((ans & (1 << i)) != 0) {
    count++;
}

Implementation Logic

int countSetBits(int ans) {
    int count = 0;
    for (int i = 0; i < 31; i++) {
        if ((ans & (1 << i)) != 0) {
            count++;
        }
    }
    return count;
}

• Time Complexity: $\mathcal{O}(31)$ because the loop always runs 31 times regardless of how small the number is.
• Space Complexity: $\mathcal{O}(1)$ (constant extra space).

5. Approach 2: Optimized Bit Traversal (Division by 2)

We can optimize our traversal so we do not waste CPU cycles iterating through leading zeros up to bit 31. Instead of checking every single bit position statically, we can inspect the value dynamically using division by 2 (n = n / 2 or n >>= 1).

Tracing with ans = 13 (1101 in binary)

Let's trace division by 2 and check remainders:

• Iteration 1: 13 / 2 = 6, remainder = 1 $\rightarrow$ count = 1
• Iteration 2: 6 / 2 = 3, remainder = 0 $\rightarrow$ count = 1
• Iteration 3: 3 / 2 = 1, remainder = 1 $\rightarrow$ count = 2
• Iteration 4: 1 / 2 = 0, remainder = 1 $\rightarrow$ count = 3
• Value reaches 0, loop terminates.

Complete Optimized Code Solution

class Solution {
    public int minBitFlips(int start, int goal) {
        // Step 1: XOR to find differing bits
        int ans = start ^ goal;
        
        // Step 2: Count set bits dynamically
        int count = 0;
        while (ans > 0) {
            // Check if the current least significant bit is 1 (odd number check)
            if ((ans & 1) == 1) {
                count++;
            }
            // Right shift ans by 1 (equivalent to integer division by 2)
            ans >>= 1; 
        }
        
        return count;
    }
}

6. Complexity Analysis

• Time Complexity: $\mathcal{O}(\log_2 N)$, where $N$ is the value of start ^ goal. The loop runs proportional to the number of bits required to represent the XOR outcome, skipping all leading zeros.
• Space Complexity: $\mathcal{O}(1)$ as no additional data structures are allocated.

Summary and Key Takeaways

• Problem Objective: Finding the minimum bit flips to convert start into goal is equivalent to counting the number of set bits in their XOR difference.
• XOR Operator Properties: XOR (^) uniquely outputs 1 when comparing mismatching bits (0 and 1) and 0 for matching bits.
• Bitmasking Check: The $i$-th bit of a number can be verified using the expression (number & (1 << i)).
• Optimization Principle: Avoid fixed 32-bit loops when numbers are small; dividing by 2 (>>= 1) terminates the loop the moment the value reduces to 0.
• Optimal Complexity: The optimized bit-counting solution executes in logarithmic time ($\mathcal{O}(\log_2 N)$) and constant space ($\mathcal{O}(1)$).