位元運算之運用

位元運算是許多程式設計中常見的技巧，最主要的優點不外乎是效率與程式碼的簡潔。但其最大的缺點就是可讀性非常差，而且限制也較多。

位元運算往往不直覺，較為艱深，對位元的變化要了若指掌才行。一般不建議在程式碼中使用這些技巧，不僅使他人理解困難外，就算是自己寫的程式碼，也不見得能在短時間內理解，甚至是自己都無法理解。

但若是在講求效率的程式競賽中，位元運算是個常常使用的技巧。不但執行效率高，而且程式碼量少又簡潔。當然還是有個致命的缺點是除錯困難。不過，在像 ACM-ICPC 的競賽中，有些題目就是要使用位元運算來解決。因此，對於競賽的選手來說，基本的位元運算還是非常重要的！

C/C++ 中的位元運算符號

由於我對於 C/C++ 比較熟悉，加上 C/C++ 也是 ACM-ICPC 可使用的語言之一，接下來的程式碼部分，將都使用 C/C++ 中的語法。以下為 C/C++ 中位元運算的運算元：

symbol	function
`>>`	右移運算
`<<`	左移運算
`&`	and 運算
`\|`	or 運算
`^`	xor 運算
`~`	not 運算

二的補數

關於二的補數，可以參考維基百科：二的補數

這邊比較需要提到的是：在二的補數系統中，某個整數 x 加上負號，會等於對該數進行 not 運算後加上 1 的值。 (-x ≡ ~x + 1)

奇數判斷

(x & 1) == 1

將數字以二的冪次數加總， x = 2ⁿ + 2^n-1 + … + 2¹ + 2⁰。二的冪次中，只有 2⁰ 為奇數 1。要判斷一個整數是否為奇數時，僅需要判斷其最低位元是否為 1 即可。因此只要用 1₁₀ (0001₂) 對該數進行 and 運算，若結果仍為 1 即可確定該數為奇數，否則為偶數。

這邊要注意括號，由於 == 的運算優先度高於 &，若不加上括號將使運算變為 x & (1 == 1)。感謝 DJWS 前輩的指教 :)。

二的冪次

2ⁿx

x << n

利用左移運算，即可輕易將整數 x 乘以 2ⁿ。若僅需要二的羃次，1 << n 即可得到 2ⁿ 該數。

x/2ⁿ

x >> n

利用右移運算，即可輕易將整數 x 除以 2ⁿ。需要注意的是，該除法會直接捨去浮點數部分。

末端連續 n 個位元 1

(1 << n) - 1

1 << n 的會使得第 n 位位元為位元 1，其餘皆為位元 0。減去 1₂ (00…001₂) 時，會使得位元中的第 0 位到第 n - 1 位的位元為位元 1，而第 n 位（含）之後的位元皆為位元 0。位元的樣子將會為 00…0011…11 共 n 個位元 1。

取 2ⁿ 的模數

x & ((1 << n) - 1)

前面提到 (1 << n) - 1 會得到末端連續 n 個位元 1。利用該數字與 x 進行 and 運算，此時 x 中第 0 位到第 n - 1 位的位元 1 將會被保留，而不管第 n 位（含）之後的位元為何，都將被設定為位元 0。該結果即為對 x 取 2ⁿ 的模數。

最低的位元 1

x & -x

最低的位元 1 為在位元表示中位於最低位的位元 1。例如： 14₁₀ (1110₂) 的最低位元為 2₁₀ (0010₂)。

根據二的補數，-x 為 ~x + 1。因此在這先將 -x 拆開為 ~x + 1 來討論。x 中最低位的位元 1 經過 not 運算後，將在 ~x 中變為最低位的位元 0。因此對 ~x 加上 1 後，最低位的位元 0 重新變為位元 1，且其後的位元都將被設定為 0。

對任何數加上 1，在位元的意義即為將最低位的位元 0 變為位元 1，且低於該位的位元都將被設定為 0。

經過 and 運算後，x 最低的 1 位元將仍然為 1，且低於該位元的位元也都將為位元 0。另外，因為 x & ~x 會等於 0，所以 ~x 沒有改變的部分會使得高於該位元的位元也都將會是位元 0。此時該最低位的位元 1 將會被獨立出來。

是否為二的冪次

(x & -x) == x

此方法根據上述的最低位位元 1 而來，若該數字為二的冪次，那麼該數以位元表示時，僅會有一個位元 1。既然只會有一個位元 1，在求最低位位元 1 時，該最低位位元 1 必為該數字本身。

將第 n 個位元設定為 1

x | ( 1 << n )

利用第 n 個位元為 1 的二的冪次數 2ⁿ，該數字僅有第 n 個位元為 1。在利用 or 運算，即可保證第 n 個位元被設定為 1。

將第 n 個位元設定為 0

方法一

x & ~(1 << n)

取得第 n 個位元為 1 的數字，在對其做 not 運算。因此該數字變為僅有第 n 個位元為 0，而其他位元為 1 的數字。在以該數字與 x 做 and 運算，此時 x 的第 n 個位元將被設定為 0。

方法二

~((~x) | (1 << n)

先對該數字做 not 運算，以 x’ 代稱。在利用上述將第 n 個位元設定為 1 的方法，將 x’ 的第 n 個位元設定為 1。最後在對該數做一次 not 運算，由於第 n 個位元在 x’ 中被設定為 1 了，所以在做一次 not 後，將會變為 0。

整數交換

x^=y^=x^=y

拆開來看即為：

x = x ^ y;
y = y ^ x;
x = x ^ y;

這個方法基於 xor(^) 的特性：

任何數對本身做 xor 運算都會等於 0
任何數對 0 做 xor 運算都會等於本身

在第一次進行 xor 運算後，此時的 x 等於 x ^ y，暫時稱為 x'。第二次進行 xor 運算後 y 等於 y ^ x'，將 x' 還原後的 y 為 y ^ x ^ y。根據前面提到 xor 的特性， y 即等於 x，暫時以 y' 代稱。第三次的 xor 運算 x 又等於 x' ^ y'，將 x' 與 y' 展開後，x 等於 x ^ y ^ x，同樣根據 xor 的特性， x 會等於 y。如此一來就完成了兩個整數的交換。

消去最低位 1 位元