二進位操作: 一的補數 Number Complement_Leetcode #476

Michael Pointner on Unsplash

題目敘述 476. Number Complement

給定一個整數num，請輸出對應的一的補數，
也就是num二進位表達式的01對調，0換成1，1換成0。

測試範例

Example 1:

Input: num = 5
Output: 2
Explanation: 

5 = 0b 101
01對調後
2 = 0b 010

Example 2:

Input: num = 1
Output: 0
Explanation: 

1 = 0b 1
01對調後
0 = 0b 0

約束條件

Constraints:

• 1 <= num < 2^31

num在 4 bytes整數範圍內。

演算法 使用XOR運算子特質

XOR運算子有一個很好的特質

1 XOR 1 = 0 完成了1 翻轉成 0 的計算

0 XOR 1 = 0 完成了0 翻轉成 1 的計算

先計算原本num需要的位元寬度，接著製造一個全1的 mask，兩者做XOR，

最後輸出就是num一的補數。

程式碼 使用XOR運算子特質

from math import floor
from math import log

class Solution:
    def findComplement(self, num: int) -> int:
        
        bits_length = floor( log(num, 2) + 1)
        
        return num^( 2**bits_length - 1 )

額外補充，python內建一個取得位元寬度的function .bit_length()

class Solution:
    def findComplement(self, num: int) -> int:
        
        bit_mask = 2**num.bit_length() -1 
        
        return ( num ^ bit_mask )

複雜度分析

時間複雜度: O( 1 )

如果n無不限制範圍，那麼所需時間為位元寬度 = O( log n )

題目已經說是32bit的整數範圍內，可視為一次性的常數操作，所需時間為O(1)。

空間複雜度: O(1)

所用到的臨時變數占用的空間都是固定大小，為常數級別O(1)

Reference:

[1] Number Complement - LeetCode