Bit Manipulation
基本觀念
Bit Manipulation 只有幾種基本運算: and, or, xor, not, <<, >>。
常用技巧：
簡單技巧
- n & （n-1）能够去掉 n 最右邊一位的 1
- n & -n 能夠取出最後一位 1 (e.g. n==110, -n==010, n&-n==010)
數有幾個 1
Loop n & (n-1) 直到 n == 0，可以算出 n 有幾個 1
int count_one(int n)
{
int count = 0;
while(n != 0)
{
n = n&(n-1);
count++;
}
return count;
}
進階技巧
自己做 bit 加法
XOR 的概念很像加法，原本是 0 的東西遇到 1，就會變成 1，再遇到下一個 1 的時候，就會變成 0。可以參考這個 comment 跟這個 comment。
做法:
讓 b0 b1
0 0
1 0
0 1
0 0
加到第三次就會循環。
b0 = b0^A[i]&(~b1)
b1 = b1^A[i]&(~b0)
範例一：
X = 1 1
X = 1 1
Y = 0 1
X = 1 1
初始:
b0 = 0 0
b1 = 0 0
第一次 X:
b0 = 1 1
b1 = 0 0
第二次 X:
b0 = 0 0
b1 = 1 1
第一次 Y:
b0 = 0 0
b1 = 1 0
第三次 X:
b0 = 0 1
b1 = 0 0
範例二：
X = 1 1
X = 1 1
Y = 0 1
X = 1 1
Y = 0 1
第一次 X:
b0 = 1 1
b1 = 0 0
第二次 X:
b0 = 0 0
b1 = 1 1
第一次 Y:
b0 = 0 0
b1 = 1 0
第三次 X:
b0 = 0 1
b1 = 0 0
第二次 Y:
b0 = 0 0
b1 = 0 1