AlgoViz
HomeBit Manipulation

Minimum Bit Flips to Convert Number

Medium

Count the set bits of the XOR

Problem

Return the number of bit flips needed to turn start into goal.

In simple words

XOR the two numbers; the count of 1s is how many bits differ.

The idea

XOR marks exactly the positions where the two numbers differ, and each differing position needs one flip. So the answer is the population count of start ^ goal.

The trick

  • XOR first, then popcount — two operations total.
  • Same-bit positions cancel to 0 and cost nothing.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

10
7
0
1

Step 1 of 2. Here's the example — start=10, goal=7 Values: 10, 7.

1/2
Optimal
timeO(1)spaceO(1)
1return popcount(start ^ goal)

Input

array
[10, 7]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
start=10, goal=7
Output:
3

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.