前往
大廳
主題

LeetCode - 476. Number Complement 解題心得

Not In My Back Yard | 2020-10-30 12:00:04 | 巴幣 0 | 人氣 259

題目連結:


題目意譯:
給定一正整數 num,輸出其補數。在此的補數之產生方式為反轉其二進位制之位元。

限制:
給定的整數 num 保證可以放入 32 位元有號整數之中。
num ≧ 1
你可以假設二進位制中的表示方法中沒有任何前導 0 。



範例測資:
範例 1:
輸入: num = 5
輸出: 2
解釋: 5 的二進位制表示法為 101 (沒有前導 0 之位元)且其補數為 010。所以你需要輸出 2 。

範例 2:
輸入: num = 1
輸出: 0
解釋: 1 的二進位制表示法為 11 (沒有前導 0 之位元)且其補數為 0。所以你需要輸出 0 。


解題思維:
找到 num 在二進位表示法中位於最左邊的為「1」之位元其位置。如果沒有任何的「1」則定為最低位(最右邊)的位元。

將 num 反轉其位元(例如在 C 或 C++ 中其操作寫為 ~num)。然後將上面找到的最左邊的「1」之位置左邊的所有的「1」全部清掉(設為 0),只留下從該位元開始往右到底的所有位元之資訊。這項操作用位元遮罩(Bit Mask)以及位元運算可以輕鬆達成,例如在 C 、 C++ 可以寫成如下:
(~num) & (leftMost - 1)
其中 ,「&」代表著位元運算中的「和」(And),且 leftMost 為上述最左邊的「1」該位元代表的 2 之冪次(例如 5 的二進位表示法為 101 ,其最左邊的「1」代表 2 ^ 2 = 4 )。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作