A bit flip of a number x is choosing a bit in the binary representation of x and flipping it from either 0 to 1 or 1 to 0.
x = 7, the binary representation is 111 and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get 110, flip the second bit from the right to get 101, flip the fifth bit from the right (a leading zero) to get 10111, etc.Given two integers start and goal, return the minimum number of bit flips to convert start to goal.
Example 1:
Input: start = 10, goal = 7 Output: 3 Explanation: The binary representation of 10 and 7 are 1010 and 0111 respectively. We can convert 10 to 7 in 3 steps: - Flip the first bit from the right: 1010 -> 1011. - Flip the third bit from the right: 1011 -> 1111. - Flip the fourth bit from the right: 1111 -> 0111. It can be shown we cannot convert 10 to 7 in less than 3 steps. Hence, we return 3.
Example 2:
Input: start = 3, goal = 4 Output: 3 Explanation: The binary representation of 3 and 4 are 011 and 100 respectively. We can convert 3 to 4 in 3 steps: - Flip the first bit from the right: 011 -> 010. - Flip the second bit from the right: 010 -> 000. - Flip the third bit from the right: 000 -> 100. It can be shown we cannot convert 3 to 4 in less than 3 steps. Hence, we return 3.
Constraints:
0 <= start, goal <= 109
Note: This question is the same as 461: Hamming Distance.
The simplest way to determine the different bits between two numbers is to use the XOR operation. XORing two bits will yield 1 if the bits are different and 0 if they are the same. Thus, XORing two numbers will produce a number with bits set at positions where the input numbers have different bits. Counting the number of 1s in this result will give the number of flips required.
This code calculates the XOR of the two integers, then counts the number of 1s in the result by shifting the XOR-ed value right and checking the least significant bit using bitwise AND with 1.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the number of bits in the maximum of the two numbers, as you may have to check each bit once.
Space Complexity: O(1) as no additional space is used.
Many languages offer built-in functions to count the number of set bits (ones) in a binary number. Utilizing these handy functions can make our solution more concise and often more efficient. The bitwise XOR is computed between the two numbers, and the solution boils down to counting the number of set bits in the result.
This C solution uses the GCC built-in function __builtin_popcount to count the number of set bits in the XOR-ed numbers.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1) on systems where built-ins are optimized.
Space Complexity: O(1) since we use no additional resources.
| Approach | Complexity |
|---|---|
| Using XOR and Bit Count | Time Complexity: O(n) where n is the number of bits in the maximum of the two numbers, as you may have to check each bit once. |
| Using PopCount in Built-in Libraries | Time Complexity: O(1) on systems where built-ins are optimized. |
L3. Minimum Bit Flips to Convert Number | Bit Manipulation • take U forward • 95,649 views views
Watch 9 more video solutions →Practice Minimum Bit Flips to Convert Number with our built-in code editor and test cases.
Practice on FleetCode