🎎改頭換面 二進位操作 用最少的bit翻轉讓兩個數字相同_Leetcode #2220

Keagan Henman on Unsplash

題目敘述 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)。

Reference

[1] Minimum Bit Flips to Convert Number - LeetCode