Minimum Bit Flips to Convert Number
Given two integers start and goal, return the number of bit flips required to turn start into goal. A bit flip changes a single bit from 0 to 1 or from 1 to 0.
- 0 <= start, goal <= 10⁹
Intuition
Minimum bit flips to convert number counts how many single-bit changes turn start into goal. A flip changes one bit, so the answer is simply the number of positions where the two numbers differ.
Comparing bit by bit with shifts and masks works, but one operation already computes exactly this:
- XOR produces a 1 in every position where the two numbers differ, so the answer is the population count of start XOR goal.
That is the whole solution — one XOR and one bit count.
Counting the set bits can be done several ways. The straightforward loop shifts right 32 times, testing the lowest bit each pass, at a fixed 32 iterations.
Brian Kernighan's method is neater: n & (n − 1) clears the lowest set bit, so looping until n is zero runs once per set bit rather than once per bit position. On numbers with few differing bits, that is far fewer iterations.
Most languages also provide a built-in — bin(n).count('1') in Python, Integer.bitCount in Java — which is the right choice unless the problem forbids it.
The common misstep is trying to reason about which specific bits to flip and in what order. Order is irrelevant, since each flip is independent and affects exactly one position, so no sequencing logic is needed.
Both numbers are non-negative and within 32 bits, so no sign-extension concerns arise from the XOR.
The cost is O(1) for fixed-width integers — at most 32 iterations regardless of input.
start ^ goal has a 1 exactly where the two numbers disagree, so the answer is that value's population count. Reframing "how many differences" as "popcount of the XOR" is the standard move — it's the Hamming distance.
Approach
Before reading on: price up what counting everything costs here, then ask which operator makes the unwanted values cancel themselves out. Aim for O(log x) time and O(1) space.
Count differing positions
A flip changes one bit, so the answer is the number of positions where the two numbers differ — nothing about ordering or which bits to pick matters.
Use XOR to find them
start XOR goal produces a 1 in exactly the differing positions. One operation replaces any bit-by-bit comparison loop.
Count the set bits
Population-count the XOR result. A simple loop shifting right 32 times works and has fixed cost.
Prefer Kernighan's method
n & (n - 1) clears the lowest set bit, so the loop runs once per set bit rather than once per position — far fewer iterations when few bits differ.
Or use the built-in
bin(n).count('1') in Python or Integer.bitCount in Java is clearest, and correct unless the problem forbids library calls.
Cost of the approach
At most 32 iterations regardless of input, giving O(1) time and O(1) space for fixed-width integers.
Solution & live demo
Common pitfalls
Comparing bits one at a time
for i in range(32):
if ((start >> i) & 1) != ((goal >> i) & 1): count += 1x = start ^ goal while x: count += x & 1; x >>= 1
Correct but always 32 iterations. XOR-ing first collapses the comparison into one operation, and the loop then stops as soon as the remaining bits are zero.
Using arithmetic shift on a negative value
// in Java: x >>= 1 on a negative int
// use x >>>= 1, or Integer.bitCount(x)
Java's >> preserves the sign bit, so a negative value shifts in 1s forever and the loop never terminates. The unsigned shift >>> (or the built-in popcount) avoids it.
Counting flips on the smaller number's width
while start or goal:
x = start ^ goal while x:
Driving the loop on the operands rather than their difference does extra work and tempts an early exit when one runs out — but high bits set in only one number still count as flips. The XOR already encodes them.
Edge cases
x = start ^ goal = 0, the loop body never executes, and the answer is 0 flips — correct.
The shorter number is implicitly zero-padded on the left. 3 ^ 4 = 7 = 111, giving 3 flips, which matches counting 011 against 100 by hand.
x = start, so the answer is simply the number of set bits in start — every 1 must be flipped down to 0.