Bit Manipulation Bit basics
109. Minimum Bit Flips to Convert Number
You are given two non-negative integers, start and goal. A bit flip picks one bit of a number and
changes it: a 0 becomes 1, or a 1 becomes 0. Return the smallest number of bit flips that turns start
into goal.
Any bit can be flipped, including the 0s in front of a number's highest 1 bit. For example, 1 is 001, and
flipping its bit 2 gives 101, which is 5.
Example 1
Input: start = 21, goal = 12
3Explanation: 21 is 10101 and 12 is 01100. They differ in bits 0, 3 and 4, counting from 0 at the right. Each
of those bits needs one flip.
Example 2
Input: start = 4294967296, goal = 1
2Explanation: 4294967296 is 232: a 1 followed by 32 zeros. We flip bit 32 to 0 and bit 0 to 1.
Example 3
Input: start = 9007199254740991, goal = 0
53Explanation: 253 − 1 is 53 ones in binary. Every one of them must be flipped to 0.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ start, goal ≤ 253 − 1
Clarifying questions
What you would ask an interviewer before writing any code.