Bit Manipulation – 陪你刷題

透過 bitwise operation 來巧妙的操控個別或部分 bits ,因為 bitwise operation 的操作接近原生的 cpu instruction ,執行速度較直接使用加減乘除更快,除了常見的 XOR, OR, NOT, AND,以下還有一些常見的操作:

swap 兩變數 a 和 b

a = a ^ b;
b = a ^ b; (a 此時為 a^b ,因此 b = a ^ b ^ b = a)
a = a ^ b; (b 此時為 a ,因此 a = a ^ b ^ a = b)

去除變數最低的一 bit (Least Significant Bit)

a & (a-1)

Leetcode #231 Power of Two

如果為 2 的 power ,代表其 bit representation 只包含一個 bit ,前面有清除 LSB 的 bit manipulation 技巧,清除後若該數等於 0 ,即代表該數為 the power of two .

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return (n>0) && !(n&(n-1));
    }
};
  • 延伸練習 Leetcode #333 ,這題可以一次練習 DP 和 bit manipulation

得到變數最低的一 bit (Least Significant Bit)

對於每個二補數求其 negation ,作法為對每一個位數求其 1補數,再對結果加 1 。

a & (-a)
  • Leetcode #260 即可應用這個技巧

XOR 技巧使用

Leetcode #268 Missing Number

方法 1 Hash Table

依序將每個數放入 hash table ,再從 0 開始到 hash table 查找是否有紀錄。

  • Time Complexity: O (n+n) = O (n)
  • Space Complexity: O(n)

方法 2 Bit Manipulation

利用 XOR 的技巧來找出 missing number ,題目說在 n-1 個數字中會包含 [0, n] 的數,將這 n-1 個數字與 [0, n] 做 XOR 後,即可找出 missing number 。

  • Time Complexity: O (n)
  • Space Complexity: O (1)

方法 3 Cyclic sort

Cyclic Sort – 陪你刷題文章中有探討過這題,Cyclic Sort 也是相當高效的作法。

Leetcode #136 Single Number

方法 1 Hash table

走訪一輪,並分別記下各數出現次數於 hash table。接著走訪第二輪,遇到出現次數為 1 次的,即可直接回傳。

  • time complexity: O (n)
  • space complexity: O (n)

方法 2 Bit Manipulation

使用 XOR 技巧,出現兩次的數會因為 XOR 而抵銷。

  • time complexity: O (n)

  • space complexity: O (1)

  • 延伸練習 Leetcode #137, #260

做完 XOR 這幾題後,可以發現使用 hash table 的空間複雜度需要至少 O(n) ,應用 bit manipulation 能夠降低到 O(1)

Reference

  1. changgyhub/leetcode_101