A bit flip turns a single bit of a number's binary form from 0 to 1 or from 1 to 0.
Given two integers start and goal, return the minimum number of bit flips needed to convert start into goal.
0 (including leading zeros) never need a flip, so they add nothing to the count.1 — or sum pairwise popcounts. Same XOR-and-count idea, applied across the set.x & (x - 1) is known as Brian Kernighan's algorithm.Input: start = 10, goal = 7 Output: 3 10 is 1010 and 7 is 0111 in binary; they differ in 3 bit positions.
Input: start = 3, goal = 4 Output: 3 3 is 011 and 4 is 100 in binary; they differ in 3 bit positions.
- 0 <= start, goal <= 10^9
Converting one number into another a bit at a time sounds fiddly — but a single operation collapses the whole thing. Here's the arc from counting bits by hand to reading the answer off in one line.
i holds either 0 or 1.a ^ b produces a 1 exactly where a and b differ — the heart of this problem.1s a number has (its population count).Asking these before coding shows you're mapping the input space, not just pattern-matching.
“Can start and goal already be equal?”
Then the answer is 0 — a clean base case the code should handle for free.
“Are the inputs always non-negative?”
Yes here, so there's no sign bit or two's-complement surprise to reason about.
“How large can the numbers get?”
Up to a billion, which fits in about 30 bits — so even a per-bit scan is instant.
Before I code, two quick checks.
If start already equals goal I return 0 — agreed?
And both inputs are non-negative and under a billion, so about 30 bits — correct?
In plain words: align the two numbers bit for bit and count the positions that don't match. Each mismatch costs exactly one flip.
Worked example — start = 10, goal = 7
start = 10 -> 1 0 1 0 goal = 7 -> 0 1 1 1 differ? Y Y . Y -> 3 positions answer: 3
A matching bit is already done; a differing bit must be flipped exactly once. So the total cost is precisely the count of differing positions — never more, never less.
start ^ goal yields a number whose 1-bits sit exactly where the two disagree. The problem becomes: how many 1s does start ^ goal have?
1 0 1 0 (10) ^ 0 1 1 1 (7) = 1 1 0 1 -> three 1s -> 3
Rather than inspect all ~31 positions, x &= x - 1 erases the lowest set bit each step — so you loop only once per 1-bit.
| Brute force | Optimal | |
|---|---|---|
| Idea | Scan all ~31 bit positions | XOR, then count the set bits |
| Time | O(1) | O(1) |
| Space | O(1) | O(1) |
Both are constant-time on fixed-width integers; the optimal just does fewer operations and reads as one idea. Full code is in the Approaches selector below.
Key takeaway
To measure how two numbers differ bit-for-bit, XOR them and count the 1s. XOR-then-popcount is the reflex move for any "how many positions differ" question — it's exactly the Hamming distance.
diff = start XOR goal
flips = 0
while diff != 0:
diff = diff AND (diff - 1) # drop the lowest set bit
flips = flips + 1
return flips