☕ DSA Java Articles

Topics › Bit Manipulation › Interview Problems

Minimum Bit Flips to Convert Number

Medium TUF ID 141 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A bit flip changes a single bit of a number from 0 to 1 or from 1 to 0. You are given two integers start and goal. Return the minimum number of bit flips needed to turn start into goal. Leading zeros count as bits, so turning 3 = 011 into 4 = 100 takes three flips.

Constraints: 0 ≤ start, goal ≤ 10^9. The solutions below also work for negative inputs, treating them as 32-bit patterns.

Example 1

start = 10, goal = 7
answer = 3           // 1010 -> 0111: bits 0, 2 and 3 differ

Example 2

start = 3, goal = 4
answer = 3           // 011 -> 100: every one of the three low bits differs

Example 3

start = 5, goal = 5
answer = 0           // nothing to flip

Why the answer is the number of differing bits

Each flip changes exactly one bit position, and flipping a position twice is a waste. A position where start and goal already agree needs no flip; a position where they disagree needs exactly one. Flips at different positions do not interfere with each other. So the minimum is precisely the number of positions where the two numbers differ: the Hamming distance between start and goal. Every approach below counts those positions; they differ only in how.

Approach 1: Brute force, compare each position

Intuition. Walk through all 32 bit positions, extract bit i of each number with (x >> i) & 1, and count the positions where the two bits differ. There is nothing to prove: it is the definition.

Algorithm.

  1. flips = 0.
  2. For i from 0 to 31: if ((start >> i) & 1) != ((goal >> i) & 1), increment flips.
  3. Return flips.
static int bruteForce(int start, int goal) {
    int flips = 0;
    for (int i = 0; i < 32; i++) {
        if (((start >> i) & 1) != ((goal >> i) & 1)) flips++;
    }
    return flips;
}

Complexity. Time O(32), which is constant but always the full 32 iterations. Space O(1).

Approach 2: Better, XOR then count ones

Intuition. XOR produces a 1 exactly where its two inputs differ and a 0 where they agree. So start ^ goal is a number whose set bits mark precisely the positions that must be flipped, and the problem collapses to counting set bits. Count them by reading the lowest bit and shifting right with >>> until nothing is left; the unsigned shift guarantees termination even if the XOR is negative.

Algorithm.

  1. diff = start ^ goal, flips = 0.
  2. While diff != 0: flips += diff & 1, diff >>>= 1.
  3. Return flips.
static int better(int start, int goal) {
    int diff = start ^ goal;
    int flips = 0;
    while (diff != 0) {
        flips += diff & 1;
        diff >>>= 1;
    }
    return flips;
}

Complexity. Time O(position of the highest differing bit): the loop stops as soon as diff runs out of bits, so for 10 and 7 it runs 4 times, not 32. Space O(1).

Approach 3: Optimal, XOR then Brian Kernighan

Intuition. n & (n - 1) clears the lowest set bit of n and nothing else, because n - 1 flips that bit and the zeros below it while leaving the higher bits alone. Applying it repeatedly to diff removes one differing position per round, so the number of rounds is the number of flips. The loop now runs once per flip rather than once per bit, which is the best possible for a counting loop: it does exactly as much work as the answer is large.

Algorithm.

  1. diff = start ^ goal, flips = 0.
  2. While diff != 0: diff &= diff - 1, flips++.
  3. Return flips.
static int optimal(int start, int goal) {
    int diff = start ^ goal;
    int flips = 0;
    while (diff != 0) {
        diff &= diff - 1;
        flips++;
    }
    return flips;
}

Dry run on start = 10 = 1010, goal = 7 = 0111: diff = 1010 ^ 0111 = 1101.

round diff diff - 1 diff & (diff - 1) flips
1 1101 1100 1100 1
2 1100 1011 1000 2
3 1000 0111 0000 3

Complexity. Time O(k) where k is the answer, at most 32. Space O(1).

In Java the whole thing is also a one-liner using the library popcount, which the JIT compiles to a single hardware instruction:

static int optimalBuiltin(int start, int goal) {
    return Integer.bitCount(start ^ goal);
}

Use this in production and the Kernighan loop in interviews, where the point is to show that you know why n & (n - 1) works.

Edge cases and pitfalls