# 位元運算
###### tags: `Competitive Programming Note`

本文已停止更新，新版請至 [WiwiHo 的競程筆記](https://cp.wiwiho.me/)

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

## 布林代數

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

| |邏輯運算符|布林運算符|C++ 布林運算子|
|--|------|-----|----|
|AND| $\land$ | $\cdot$（就是乘法的那顆點） | `a && b` |
|NOT| $\lnot$ | $\overline{A}$（上劃線） | `!a` |
|OR| $\lor$ | $+$ | `a || b` |
|XOR| | $\oplus$ | `a != b` |

邏輯運算符就是數學課會學的那種，這個表應該有至少一欄可以讓你知道這些運算表示什麼，不知道的話可以 Google 個真值表。[維基百科](https://zh.wikipedia.org/wiki/%E5%B8%83%E5%B0%94%E9%80%BB%E8%BE%91)有非常多布林運算的規則。

:::info
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 \leq 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})$$