220. Count Bits to Flip to Convert A to B

Given two non-negative integers a and b, find the minimum number of bits that need to be flipped to convert a into b.

Input: Two lines: the first contains a, the second contains b. Output: Print a single integer - the minimum number of bit flips needed to convert a into b.

0 <= a, b <= 10^9

This directly reuses the popcount (count set bits) logic from earlier in this same category - once you've built that one building block, several other problems reduce to just applying it after one extra step (here, an XOR).

You want to turn number A into number B by flipping individual bits. How many flips does it take, at minimum? Brute force: Compare a and b bit by bit manually (checking each corresponding pair of bits one at a time) and count how many differ - this works and is essentially the same idea as the optimized approach, just without using the XOR operator to do the comparison in one shot. Optimised: XOR is precisely the operation that marks exactly the bits where two numbers DIFFER (1 where they differ, 0 where they match) - so counting set bits in (a XOR b) directly gives the number of differing bit positions, which is exactly the minimum number of flips needed, with zero extra reasoning required beyond that one XOR.

Compute x = a XOR b as before, but then count its set bits using Brian Kernighan's trick: repeatedly do x = x AND (x - 1), which clears the lowest set bit each time, and count how many iterations it takes until x becomes 0. This only performs one iteration per set bit rather than checking every one of the 32 bit positions regardless of whether it's set, so it's faster whenever the differing bits are sparse. Time: O(number of differing bits), at most O(log n) Space: O(1)

Convert both a and b into binary strings padded to the same length, then compare them position by position, counting how many positions differ. Each differing position is exactly one bit that must be flipped, but building and comparing strings is more overhead than necessary for a purely numeric bit comparison. Time: O(log(max(a,b))) Space: O(log(max(a,b)))

Compute x = a XOR b, since a bit is set in x exactly where a and b differ. Then loop over all fixed bit positions (e.g. 0 to 31), and for each one check whether that bit is set in x by shifting a mask and using bitwise AND, incrementing a counter for each set bit found. This avoids string conversion entirely and works directly on the integer representation. Time: O(32) = O(log n) Space: O(1)

1. XOR a and b together - wherever the two numbers have DIFFERENT bits, the XOR result has a 1; wherever they're the SAME, it has a 0. 2. Count the set bits in that XOR result - each one represents exactly one bit that needs to be flipped to turn a into b. 3. That count is the minimum number of flips.

Time: Proportional to the number of bits in the larger number (around 30 steps) - essentially instant. Space: O(1) - no extra storage needed.

Test a = b (0 flips needed) and a, b at opposite extremes (0 and 10^9) to maximize the number of differing bits.

This problem is a great example of recognizing that a seemingly separate question ('minimum flips to convert A to B') reduces directly to a problem you may have already solved ('count set bits') - always look for this kind of reduction before designing a new algorithm from scratch.