iT邦幫忙

3

【小馬的LeetCode練功坊】1009. Complement of Base 10 Integer

參考題目: LeetCode 1009. Complement of Base 10 Integer
(相同的題目: LeetCode 476. Number Complement)

題目: 給你一個非負整數,求該數字的二進位表示法的位元取反(即補數),
譬如說

Input: 5
Output: 2
解說: 5的二進位表示為101,位元取反之後變成010,也就是十進位的2

其實這一題想法很簡單,
一個正整數加上二進位補數恰好會等於11…1,
即是取得一個數字二進位的最高位數,左移一位之後,
減去原數再減1就是了
(需注意0是特別的case,如果input是0,output是1,需要另外判斷)

譬如5的二進位表示為101,
取最高位數為100,
左移一位變成1000,
減去二進位的101再減1即得到二進位的10

那要怎麼取得一個數字的最高位數呢?
小馬有一個有趣的算法,
附上python程式碼:

#函數功能: 取得最高位元的1
#想法: 透過一連串 n |= … 運算使n最高位以下全變成1
#一開始 n=1xxxxx
#n |= (n >>  1) 後變為11xxxx
#再做 n |= (n >>  1) 後變為1111xx
#以此類推,最後n ^ (n >> 1)把最高位以下的 1消去 
def hibit(n): 
    n |= (n >>  1)
    n |= (n >>  2)
    n |= (n >>  4) 
    n |= (n >>  8)
    n |= (n >> 16)
    return n ^ (n >> 1)

class Solution:
    def bitwiseComplement(self, N: int) -> int:
        return (hibit(N)<<1) - N - 1 if N!=0 else 1

c++程式碼幾乎一樣就順便打一打

class Solution {
public:
    int hibit(int n){
        n |= (n >>  1);
        n |= (n >>  2);
        n |= (n >>  4);
        n |= (n >>  8);
        n |= (n >> 16);
        return n ^ (n >> 1);
    }
    int bitwiseComplement(int N) {
        return N==0 ? 1 :(hibit(N)<<1) - N - 1;
    }
};

尚未有邦友留言

立即登入留言