題目敘述 Minimum Bit Flips to Convert Number
給定兩個整數start 和 goal，請問最少需要幾次bit翻轉，使得start等於goal?
註:bit翻轉的定義就是0->1 或者1->0
測試範例
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 <= 10^9
start, goal都介於0~十億之間。
演算法 用XOR運算子計算有幾個bit不同
想法相當直覺，
start和goal的二進位表達式有幾個bit不同，就需要幾次對應的bit翻轉。
先計算start XOR goal的值
接著，建造一個迴圈，計算有幾個bit不同，最後返回作為答案。
Python程式碼 用XOR運算子計算有幾個bit不同
class Solution:
def minBitFlips(self, start: int, goal: int) -> int:
# User XOR(^) for finding different bits
# then count bits 1 in difference
difference = start ^ goal
counter = 0
for i in range(32):
if difference & 1 == 1:
counter += 1
difference >>= 1
return counter
Go 程式碼 用XOR運算子計算有幾個bit不同
func minBitFlips(start, goal int) int {
// User XOR(^) for finding different bits
// then count bits 1 in difference
difference := start ^ goal
counter := 0
for i := 0 ; i < 32 ; i++{
if difference & 1 == 1{
counter += 1
}
difference >>= 1
}
return counter
}
複雜度分析
時間複雜度: O(1)
掃描32bit整數的每一個位置，所需時間為O(32) = O(1) 常數級別。
空間複雜度: O(1)
所用到的都是固定尺寸的臨時變數，為常數級別O(1)。
