透過 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) 。