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.
Intuition
Line the two numbers up in binary and the answer is just the count of positions where they disagree. So the real question is: which operator reports disagreement? AND and OR both collapse different inputs to the same output, so neither can tell you a position differs. XOR is the one that returns 1 exactly when two bits differ — so start ^ goal is a number whose set bits mark precisely the positions needing a flip. Count those set bits and you are done.
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
Write both numbers in binary and count disagreements by hand
Take start = 10, goal = 7. In four bits that is 1010 and 0111. Compare position by position: the leading bits differ (flip), the next pair agree (leave it), the next differ (flip), the last differ (flip). Three flips. Nothing clever has happened yet — but this hand-count tells us exactly what the algorithm must compute: the number of positions where the two bit patterns disagree.
Ask which operator detects a disagreement
We need a per-bit operation that outputs 1 only when the inputs differ. AND gives 1 only when both are 1, so 0&1 and 0&0 both give 0 — it cannot distinguish them. OR gives 1 when either is 1, so 1|1 and 0|1 both give 1 — same problem. XOR is precisely the disagreement detector: 0^1 = 1, 1^0 = 1, 1^1 = 0, 0^0 = 0. So compute x = start ^ goal, and every set bit in x marks a position that must flip. For our example, 10 ^ 7 = 13 = 1101 — three set bits, matching the hand count.
Count the set bits, and stop as soon as the number runs out
Now the problem is just population count on x. The straightforward loop tests all 32 bit positions with x & (1 << i). But there is no reason to walk past the highest set bit: repeatedly take x & 1 to test the lowest bit, then right-shift by one, and stop the moment x becomes 0. For x = 13 that is four iterations rather than 32. The complexity becomes O(log x) rather than a fixed O(32) — same answer, less work on small inputs.
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.