Minimum Bit Flips to Convert Number

easy bitwise xor

Problem

You are given two non-negative integers start and goal (each up to 10⁹). A bit flip picks one bit of start's binary representation — leading zeros included — and changes it from 0 to 1 or from 1 to 0. Return the minimum number of bit flips needed to make start equal to goal.

Inputstart = 10, goal = 7

Output3

In binary, 10 = 1010 and 7 = 0111. The two numbers disagree at bit positions 0, 2, and 3, so three flips are required.

start (0–1023)

goal (0–1023)

def min_bit_flips(start, goal):
    diff = start ^ goal
    flips = 0
    while diff:
        flips += diff & 1
        diff >>= 1
    return flips

function minBitFlips(start, goal) {
  let diff = start ^ goal;
  let flips = 0;
  while (diff) {
    flips += diff & 1;
    diff >>= 1;
  }
  return flips;
}

int minBitFlips(int start, int goal) {
    int diff = start ^ goal;
    int flips = 0;
    while (diff != 0) {
        flips += diff & 1;
        diff >>= 1;
    }
    return flips;
}

int minBitFlips(int start, int goal) {
    int diff = start ^ goal;
    int flips = 0;
    while (diff) {
        flips += diff & 1;
        diff >>= 1;
    }
    return flips;
}

Explanation

The key insight is that bit flips are independent: flipping bit 3 never affects bit 0. So the minimum number of flips is simply the number of positions where start and goal hold different bits — no clever ordering can do better, and matching every differing position is clearly enough.

XOR is the perfect tool for finding those positions. For each bit, start ^ goal produces a 1 exactly when the two bits differ and a 0 when they agree. So diff = start ^ goal is a number whose set bits are precisely the flips we must perform, and the answer is the population count (number of 1 bits) of diff.

To count the set bits we loop while diff is non-zero: add the lowest bit (diff & 1) to flips, then shift right by one. Each iteration consumes one bit position, so the loop runs once per bit up to the highest set bit of diff.

Walking the default example: start = 10 is 1010 and goal = 7 is 0111, so diff = 1101 (decimal 13). Scanning from bit 0: bit 0 is 1 (flip, total 1), bit 1 is 0 (skip), bit 2 is 1 (total 2), bit 3 is 1 (total 3). Then diff is 0 and we return 3.

The loop executes at most ⌈log₂(max(start, goal))⌉ + 1 times — about 30 iterations for values up to 10⁹ — and uses only two integer variables, giving O(log n) time and O(1) space. In practice you can also use a built-in popcount such as bin(x).count("1") in Python, Integer.bitCount in Java, or __builtin_popcount in C++.

Time: O(log n) Space: O(1)