Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Minimum Bit Flips to Convert Number

EASYProblemSolveExternal Links

Description

A bit flip of a number is the operation of choosing any single bit in its binary representation and changing it from 0 to 1 or from 1 to 0.

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

For example, if start = 10 (binary 1010) and goal = 7 (binary 0111), we need to flip exactly those bit positions where the two numbers differ.

Note: This problem is equivalent to computing the Hamming Distance between two integers — the number of positions at which the corresponding bits are different.

Examples

Example 1

Input: start = 10, goal = 7

Output: 3

Explanation:

  • start = 10 in binary: 1010
  • goal = 7 in binary: 0111
  • Positions that differ: bit 0 (0 vs 1), bit 2 (0 vs 1), bit 3 (1 vs 0)
  • We need 3 flips: 1010 → 1011 → 1111 → 0111

Example 2

Input: start = 3, goal = 4

Output: 3

Explanation:

  • start = 3 in binary: 011
  • goal = 4 in binary: 100
  • Every bit position differs: bit 0 (1 vs 0), bit 1 (1 vs 0), bit 2 (0 vs 1)
  • All 3 bits need to be flipped.

Example 3

Input: start = 0, goal = 0

Output: 0

Explanation: Both numbers are identical, so no flips are needed.

Constraints

  • 0 ≤ start, goal ≤ 10^9

Editorial

Brute Force - String Conversion and Comparison

Intuition

The most intuitive way to count differing bits is to convert both numbers to their binary string representations, then compare them character by character.

Imagine you have two strings of light switches (ON/OFF). To count how many switches you need to toggle, you simply walk along both rows side by side and count the positions where one is ON and the other is OFF.

Since the two binary strings might have different lengths (e.g., 10 = 1010 has 4 digits, 7 = 111 has 3 digits), we need to pad the shorter string with leading zeros so both have the same length before comparing.

Step-by-Step Explanation

Let's trace through start = 10, goal = 7:

Step 1: Convert start = 10 to binary string → 1010 (length 4).

Step 2: Convert goal = 7 to binary string → 111 (length 3).

Step 3: The strings have different lengths (4 vs 3). Pad the shorter one with a leading zero: 111 → 0111. Now both are length 4.

Step 4: Compare position 0 (MSB): 1 vs 0. They differ → flips = 1.

Step 5: Compare position 1: 0 vs 1. They differ → flips = 2.

Step 6: Compare position 2: 1 vs 1. They match → flips stays 2.

Step 7: Compare position 3 (LSB): 0 vs 1. They differ → flips = 3.

Step 8: All positions compared. Return flips = 3.

String Comparison: Counting Differing Bits of 10 and 7 — Convert both numbers to binary strings, pad to equal length, then walk through comparing character by character to count mismatches.

Algorithm

  1. Convert start and goal to binary string representations
  2. Pad the shorter string with leading zeros so both have equal length
  3. Initialize a counter flips = 0
  4. For each position i from 0 to length-1:
    • If start_binary[i] ≠ goal_binary[i], increment flips
  5. Return flips

Code

#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minBitFlips(int start, int goal) {
        // Convert to binary strings
        string s = "", g = "";
        int tempS = start, tempG = goal;
        
        // Handle zero case
        if (tempS == 0) s = "0";
        while (tempS > 0) {
            s = (char)('0' + tempS % 2) + s;
            tempS /= 2;
        }
        
        if (tempG == 0) g = "0";
        while (tempG > 0) {
            g = (char)('0' + tempG % 2) + g;
            tempG /= 2;
        }
        
        // Pad shorter string with leading zeros
        while (s.length() < g.length()) s = "0" + s;
        while (g.length() < s.length()) g = "0" + g;
        
        // Compare character by character
        int flips = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] != g[i]) flips++;
        }
        
        return flips;
    }
};
class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        # Convert to binary strings (remove '0b' prefix)
        s = bin(start)[2:]
        g = bin(goal)[2:]
        
        # Pad shorter string with leading zeros
        max_len = max(len(s), len(g))
        s = s.zfill(max_len)
        g = g.zfill(max_len)
        
        # Compare character by character
        flips = 0
        for i in range(max_len):
            if s[i] != g[i]:
                flips += 1
        
        return flips
class Solution {
    public int minBitFlips(int start, int goal) {
        String s = Integer.toBinaryString(start);
        String g = Integer.toBinaryString(goal);
        
        // Pad shorter string with leading zeros
        int maxLen = Math.max(s.length(), g.length());
        while (s.length() < maxLen) s = "0" + s;
        while (g.length() < maxLen) g = "0" + g;
        
        // Compare character by character
        int flips = 0;
        for (int i = 0; i < maxLen; i++) {
            if (s.charAt(i) != g.charAt(i)) flips++;
        }
        
        return flips;
    }
}

Complexity Analysis

Time Complexity: O(log(max(start, goal)))

Converting each number to a binary string takes O(log n) where n is the number's value. The comparison loop iterates through all bit positions, which is at most ⌊log₂(max(start, goal))⌋ + 1 positions. For values up to 10⁹, this is at most 30 iterations.

Space Complexity: O(log(max(start, goal)))

We create two binary strings, each of length at most 30 characters. This is extra space proportional to the number of bits.

Why This Approach Is Not Efficient

The string conversion approach works correctly but has unnecessary overhead:

1. Wasteful string creation: We allocate two string objects, copy characters, and potentially pad with zeros — all to compare bits that are already stored as binary inside the CPU.

2. O(log n) extra space: The two strings consume memory proportional to the number of bits. For a simple counting problem, we should be able to use O(1) space.

3. Iterates through ALL bit positions: Even if only a few bits differ, we still compare every single position.

Key insight: If we XOR start and goal, the result has a 1 at every position where the two numbers differ and a 0 where they match. For example: 1010 XOR 0111 = 1101. The number of 1s in the XOR result equals the number of flips needed. This eliminates string conversion entirely and works directly on the binary representation.

Better Approach - Bit-by-Bit Right Shift Comparison

Intuition

Instead of converting to strings, we can compare the two numbers directly at the bit level. The idea is to repeatedly extract the least significant bit (rightmost bit) of both numbers using & 1, check if they differ, and then right-shift both numbers to expose the next bit.

Think of it like peeling layers off two numbers from the right side: we look at the outermost layer (LSB), compare, record if they differ, then peel off that layer (right shift) and repeat.

This avoids any string allocation — we work entirely with integer arithmetic.

Step-by-Step Explanation

Let's trace start = 10 (binary 1010), goal = 7 (binary 0111):

Step 1: Initialize flips = 0. Both start and goal are non-zero, so enter loop.

Step 2: Extract LSBs: start & 1 = 0, goal & 1 = 1. They differ → flips = 1. Right shift both: start = 5 (101), goal = 3 (011).

Step 3: Extract LSBs: 5 & 1 = 1, 3 & 1 = 1. They match → flips stays 1. Right shift: start = 2 (10), goal = 1 (01).

Step 4: Extract LSBs: 2 & 1 = 0, 1 & 1 = 1. They differ → flips = 2. Right shift: start = 1 (1), goal = 0 (0).

Step 5: Extract LSBs: 1 & 1 = 1, 0 & 1 = 0. They differ → flips = 3. Right shift: start = 0, goal = 0.

Step 6: Both are 0, loop ends. Return flips = 3.

Bit-by-Bit Right Shift Comparison: start=10 vs goal=7 — Watch how we extract and compare the rightmost bit of each number, then shift both right to reveal the next bit — all without string conversion.

Algorithm

  1. Initialize flips = 0
  2. While start > 0 OR goal > 0:
    • Extract LSBs: bit_s = start & 1, bit_g = goal & 1
    • If bit_s ≠ bit_g, increment flips
    • Right shift both: start >>= 1, goal >>= 1
  3. Return flips

Code

class Solution {
public:
    int minBitFlips(int start, int goal) {
        int flips = 0;
        
        while (start > 0 || goal > 0) {
            // Extract least significant bits
            int bitS = start & 1;
            int bitG = goal & 1;
            
            // If bits differ, we need a flip
            if (bitS != bitG) {
                flips++;
            }
            
            // Right shift to expose next bit
            start >>= 1;
            goal >>= 1;
        }
        
        return flips;
    }
};
class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        flips = 0
        
        while start > 0 or goal > 0:
            # Extract least significant bits
            bit_s = start & 1
            bit_g = goal & 1
            
            # If bits differ, we need a flip
            if bit_s != bit_g:
                flips += 1
            
            # Right shift to expose next bit
            start >>= 1
            goal >>= 1
        
        return flips
class Solution {
    public int minBitFlips(int start, int goal) {
        int flips = 0;
        
        while (start > 0 || goal > 0) {
            // Extract least significant bits
            int bitS = start & 1;
            int bitG = goal & 1;
            
            // If bits differ, we need a flip
            if (bitS != bitG) {
                flips++;
            }
            
            // Right shift to expose next bit
            start >>= 1;
            goal >>= 1;
        }
        
        return flips;
    }
}

Complexity Analysis

Time Complexity: O(log(max(start, goal)))

The loop runs once for each bit in the longer binary representation. For values up to 10⁹, this is at most 30 iterations. Each iteration does constant work (AND, comparison, shift).

Space Complexity: O(1)

We use only a few integer variables (flips, bitS, bitG). No strings or arrays are allocated. This is an improvement over the string-based approach.

Why This Approach Is Not Efficient

The bit-by-bit comparison improves on space (O(1) vs O(log n)), but it still iterates through every single bit position — even the ones that match.

For start = 10 and goal = 7, only 3 out of 4 bits differ, yet we loop 4 times. For larger numbers where only 1 or 2 bits differ, we might loop 30 times but only count 1-2 flips.

Key insight: We can combine TWO powerful bit manipulation techniques:

  1. XOR to instantly identify ALL differing positions in one operation: start ^ goal produces a number with 1s exactly where the bits differ.
  2. Brian Kernighan's algorithm to count only the set bits: n & (n - 1) clears the lowest set bit of n. By repeating this until n becomes 0, we loop exactly once per set bit — skipping zeros entirely.

This means if only 2 bits differ out of 30, we loop only 2 times instead of 30.

Optimal Approach - XOR with Brian Kernighan's Bit Counting

Intuition

This approach combines two elegant bit manipulation ideas:

Idea 1: XOR finds all differences. When you XOR two numbers, the result has a 1 at every bit position where the inputs differ and a 0 where they match. So start ^ goal encodes all the information we need — the number of 1s in this result equals the number of flips required.

For example: 10 ^ 7 = 1010 ^ 0111 = 1101 = 13. The three 1s in 13 correspond to the three differing bit positions.

Idea 2: Brian Kernighan's algorithm counts set bits efficiently. The trick n & (n - 1) always removes the lowest set bit of n. Why? Subtracting 1 from n flips the lowest set bit to 0 and all lower bits to 1. ANDing with the original n cancels the lowest set bit while preserving everything above it.

Example: n = 13 (1101).

  • 13 & 12 = 1101 & 1100 = 1100 = 12 (removed bit 0)
  • 12 & 11 = 1100 & 1011 = 1000 = 8 (removed bit 2)
  • 8 & 7 = 1000 & 0111 = 0000 = 0 (removed bit 3)

Three iterations for three set bits. If the XOR had only 1 set bit, we'd loop just once.

Step-by-Step Explanation

Let's trace start = 10, goal = 7:

Step 1: Compute XOR: xor = 10 ^ 7 = 1010 ^ 0111 = 1101 = 13. The 1s mark positions where start and goal differ.

Step 2: Initialize count = 0. xor = 13 (binary 1101), which is non-zero, so enter loop.

Step 3: Apply Brian Kernighan: xor = xor & (xor - 1) = 13 & 12 = 1101 & 1100 = 1100 = 12. The lowest set bit (position 0) was cleared. count = 1.

Step 4: xor = 12 (1100), still non-zero. Apply: 12 & 11 = 1100 & 1011 = 1000 = 8. Bit at position 2 cleared. count = 2.

Step 5: xor = 8 (1000), still non-zero. Apply: 8 & 7 = 1000 & 0111 = 0000 = 0. Bit at position 3 cleared. count = 3.

Step 6: xor = 0, loop ends. Return count = 3.

XOR + Brian Kernighan: start=10, goal=7 — Watch how XOR instantly reveals all differing bits, then Brian Kernighan's n & (n-1) trick strips away exactly one set bit per iteration — looping only through the differences.

Algorithm

  1. Compute xor = start ^ goal — this marks all differing bit positions with 1
  2. Initialize count = 0
  3. While xor ≠ 0:
    • Clear the lowest set bit: xor = xor & (xor - 1)
    • Increment count
  4. Return count

Why n & (n - 1) clears the lowest set bit:

  • n - 1 flips the lowest set bit of n to 0 and sets all lower bits to 1
  • ANDing n with (n - 1) cancels the lowest set bit (because it's 1 in n but 0 in n-1) while preserving all higher bits

Code

class Solution {
public:
    int minBitFlips(int start, int goal) {
        // XOR marks all positions where bits differ
        int xorVal = start ^ goal;
        
        int count = 0;
        
        // Brian Kernighan's algorithm: count set bits
        while (xorVal != 0) {
            // Clear the lowest set bit
            xorVal = xorVal & (xorVal - 1);
            count++;
        }
        
        return count;
    }
};
class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        # XOR marks all positions where bits differ
        xor_val = start ^ goal
        
        count = 0
        
        # Brian Kernighan's algorithm: count set bits
        while xor_val != 0:
            # Clear the lowest set bit
            xor_val = xor_val & (xor_val - 1)
            count += 1
        
        return count
class Solution {
    public int minBitFlips(int start, int goal) {
        // XOR marks all positions where bits differ
        int xorVal = start ^ goal;
        
        int count = 0;
        
        // Brian Kernighan's algorithm: count set bits
        while (xorVal != 0) {
            // Clear the lowest set bit
            xorVal = xorVal & (xorVal - 1);
            count++;
        }
        
        return count;
    }
}

Complexity Analysis

Time Complexity: O(k) where k is the number of differing bits (set bits in start ^ goal)

Brian Kernighan's algorithm loops exactly once per set bit in the XOR result. In the best case (start == goal), k = 0 and we don't loop at all. In the worst case (all 30 bits differ), k = 30. Crucially, this is proportional to the number of differing bits, not the total bit width — unlike the previous approaches which always iterate through all bit positions.

Space Complexity: O(1)

We use only two integer variables (xorVal and count). No additional data structures are needed.

Why this is optimal: The XOR operation computes all differences in O(1) (single CPU instruction). Brian Kernighan's algorithm then counts those differences in O(k) iterations, where k ≤ 30 for 32-bit integers. We cannot do better than O(k) because we need at least k operations to count k things, and we cannot identify the answer faster than O(1) for the XOR step.