位元運算

tags: Competitive Programming Note

本文已停止更新，新版請至 WiwiHo 的競程筆記

位元運算就是對二進位的 0 和 1 做一些處理，然後會有一些很神奇的性質和用途。

布林代數

先讓問題簡單一點，一個布林代數只有兩種狀態：true(2) 和 false(0)，先來一個符號表：

	邏輯運算符	布林運算符	C++ 布林運算子
AND	$\wedge$	$\cdot$（就是乘法的那顆點）	a && b
NOT	$\mathrm{\neg }$	$\bar{A}$（上劃線）	!a
OR	$\vee$	$+$	`a
XOR		$\oplus$	a != b

邏輯運算符就是數學課會學的那種，這個表應該有至少一欄可以讓你知道這些運算表示什麼，不知道的話可以 Google 個真值表。維基百科有非常多布林運算的規則。

XOR 的布林運算子是 != 應該會讓人比較問號，但仔細想一想，它的功能真的就是這樣，兩者不同時是 1，相同時是 0，恰好就和「不等於」一樣。

位元運算

進入正題，除了布林代數可以做以上那些運算以外，int、long long 這樣的整數型態也可以做這些運算，做法是「逐位」，也就是每個位元分別做運算，例如：

$(100110{)}_2$ 和

$(011000{)}_2$ 做逐位的 or 運算會是：

bit	5	4	3	2	1	0
A	1	0	0	1	1	0
B	0	1	1	0	0	0
ANS	1	1	1	1	1	0

這叫做 bitwise operation，像是逐位的 or 就稱為 bitwise or、逐位 xor 稱為 bitwise xor 等等。

以下是 C++ 的位元運算子列表：

	運算子	說明
AND	A & B	bitwise and
OR	A | B	bitwise or
XOR	A ^ B	bitwise xor
左移	A << n	將 A 的每個位元左移 $n$ 位，右方補 0
右移	A >> n	將 A 的每個位元右移 $n$ 位，右方補 0 或 1 依 A 本來的最高位決定
NOT	~A	bitwise not，將 A 為 0 的位元換成 1，為 1 換成 0，也就是取補數

一些範例：

• 要判斷一個數
  $A$ 的右方數來第
  $n$ 位是 0 還是 1：
  ​​​​A & (1 << n) //>0 的話為 1，否則為 0
  

• 把一個數
  $A$ 用很怪的方式換成相反數：
  ​​​​~A+1
  

• 把
  $A$ 除了最低位的 1 以外的 1 都換成 0（Binary Indexed Tree 的部分會細講）：
  ​​​​A & -A
  

Bitwise XOR

因為 XOR 太多常用性質，所以特別拿出來講。先來幾個基本原則（bitwise xor 的符號一樣用

$\oplus$）：

• $A\oplus B=B\oplus A$，
  $(A\oplus B)\oplus C=A\oplus (B\oplus C)$，也就是運算順序不影響結果。
• $A\oplus A=0$
• 若
  $A\oplus B=C$，則
  $A\oplus C=B$
• $A\oplus 0=A$

這些只要稍微想一下就可以得出來了，如果覺得很難想，可以先用布林代數（也就是只有一個 bit）來想，反正每一個位元互不干擾。

舉例來說，把兩個變數 a、b 互換可以這樣做：

a = a ^ b;
b = a ^ b;
a = a ^ b;

稍微解釋一下，若 a、b 的原始值分別為

$a_0$、

$b_0$，新值為

$a_1$、

$b_1$，那麼：
設

$t=a_0\oplus b_0$

$b_1=t\oplus b_0=a_0\oplus b_0\oplus b_0=a_0$

$a_1=t\oplus b_1=a_0\oplus b_0\oplus a_0=b_0$

還有一個很重要的，就是「序列前綴 xor」，可以進而得到區間 xor。在需要用到序列的各個區間和的時候，常用的手法是先算出每一個前綴和，若要得到序列

$S$ 的

$[l,r]$ （

$l\le r$）這個區間範圍的和，令

$p_n=\sum _{i=1}^n{S}_i$ （

$S$ 的索引值從

$1$ 開始編號），那麼

$\sum _{i=l}^r{S}_i$ 就是

$p_r-p_{l-1}=(\sum _{i=1}^r{S}_i)-(\sum _{i=1}^{l-1}{S}_i)$，這應該不難理解。而 xor 因為滿足

$A\oplus A=0$，所以也可以用這樣的方式來取得區間：

$$S_l\oplus S_{l+1}\oplus ...\oplus S_{r-1}\oplus S_r$$ 等同於

$$(S_1\oplus S_2\oplus ...\oplus S_{r-1}\oplus S_r)\oplus (S_1\oplus S_2\oplus ...\oplus S_{l-2}\oplus S_{l-1})$$