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
.
- For example, for
x = 7
, the binary representation is111
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 get110
, flip the second bit from the right to get101
, flip the fifth bit from the right (a leading zero) to get10111
, 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
Solution: XOR
start ^ goal will give us the bitwise difference of start and goal in binary format.
ans = # of 1 ones in the xor-ed results.
For C++, we can use __builtin_popcount or bitset<32>::count() to get the number of bits set for a given integer.
Time complexity: O(1)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 |
// Author: Huahua class Solution { public: int minBitFlips(int start, int goal) { return bitset<32>(start ^ goal).count(); // __builtin_popcount(start ^ goal); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment