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.
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
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.