---
tags: C++教學筆記
---

# 位元運算

## 二進制

要學習位元運算，必須要先學會二進制的數字表示法，
二進制與我們常用的十進制看起來非常不一樣，但核心概念是相同的。

* **二進制與十進制**

二進制與十進制的「進」代表的是進位，而前面的數字代表的是遇到多少要進位，
十進制是遇到10就進位 ~~**`看吧！變兩位數了`**~~ ，二進制則是遇到2就進位，
所以其實也有八進制、十六進制等不同的進位方式。

* **數字的位數**

我們如果去觀察一個十進制數字，其實可以發現最右邊(個位數)其實代表的是$10^0$的數，往左一位(十位數)代表$10^1$的數，以此類推。

二進制其實也是如此，但是把10都改成2，
例如二進制的`1001` 代表的是 $1\times 2^3 + 0\times 2^2 + 0\times 2^1 + 1\times 2^0 = 9$ 。

---
## 位元

大家應該都知道，電腦儲存資料的方法只有用`0`和`1`，而我們將一個儲存`0`或`1`的單位稱為位元`Bit`，又將8個位元合稱為一個位元組`Byte`。
如果去看資料型態的表格，你可以知道一個整數的記憶體空間是`4 bytes`，也就是`4x8 = 32 bits`
其中是用二進制儲存的，而有`1 bit`要被用來代表正負號，所以實際可以儲存的範圍是 $-2^{31}$**~**$2^{31}-1$ 。


---
## 位元運算子

* **NOT運算子 `~`**

* 使用方法: `~n`
* 功能: 將一個數字內所有位元的`1`變成`0`，`0`變成`1`

| | $\cdots$ | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 值 |
| - | :-: | - | - | - | - | - | - | - | - | :-: |
| `n` | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 158 |
| `~n` | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | -159 |

* **AND運算子 `&`**

| | 1 | 0 |
| ----- | - | - |
| **1** | 1 | 0 |
| **0** | 0 | 0 |

* 使用方法: `a & b`
* 功能: 將兩個數字內的位元位置對齊做AND邏輯運算(請見上表)

| | $\cdots$ | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 值 |
| - | :-: | - | - | - | - | - | - | - | - | :-: |
| `a` | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 154 |
| `b` | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 57 |
| `a & b` | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 24 |

* **OR運算子 `|`**

| | 1 | 0 |
| ----- | - | - |
| **1** | 1 | 1 |
| **0** | 1 | 0 |

* 使用方法: `a | b`
* 功能: 將兩個數字內的位元位置對齊做OR邏輯運算(請見上表)

| | $\cdots$ | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 值 |
| - | :-: | - | - | - | - | - | - | - | - | :-: |
| `a` | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 154 |
| `b` | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 57 |
| `a \| b` | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 187 |

* **XOR運算子 `^`**

| | 1 | 0 |
| ----- | - | - |
| **1** | 0 | 1 |
| **0** | 1 | 0 |

* 使用方法: `a ^ b`
* 功能: 將兩個數字內的位元位置對齊做XOR邏輯運算(請見上表)

| | $\cdots$ | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 值 |
| - | :-: | - | - | - | - | - | - | - | - | :-: |
| `a` | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 154 |
| `b` | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 57 |
| `a ^ b` | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 163 |

* **右移運算子 `>>`**

* 使用方法: `a >> b`
* 功能: 將數字`a`內的位元向右推移`b`格 `(左邊正數補0，負數補1，右邊自動丟棄)`

| | $\cdots$ | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 值 |
| - | :-: | - | - | - | - | - | - | - | - | :-: |
| `a` | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 154 |
| `a >> 2` | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 38 |

* **左移運算子 `<<`**

* 使用方法: `a << b`
* 功能: 將數字`a`內的位元向左推移`b`格 `(右邊自動補0)`

| | $\cdots$ | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 值 |
| - | :-: | - | - | - | - | - | - | - | - | :-: |
| `a` | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 26 |
| `a << 2` | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 104 |

> 其實右移運算子 `>>` 及左移運算子 `<<` 做的事情非常簡單，分別是將數值除以2的i次方(整數除法)以及乘以2的i次方而已，可以思考看看為什麼。

* **應用**

* 判斷奇偶數:

前面(三元運算子)有稍微帶到判斷奇偶數可以使用 `n & 1`，不過沒有解釋為什麼，
現在講到位元運算子就有辦法解釋了，你可以自己先想想看:

幾個重要的點:
`1的二進制是 00000001` 、`只要是奇數，最後一個位元必定是1` 、`AND運算子`

因為`1`除了$2^0$之外，其他都是0，所以AND的結果必定會是`0`。
當我們對任何數`n`做 `n & 1` 時，只會有$2^0$項的區別，
而且我們知道奇數最後一個位元一定是1、偶數最後一個位元一定是0，
因此我們可以用`n & 1`來判斷一個數的奇偶性。

* 2的i次方:

我們知道了左移運算子其實就是將數值乘以2，所以只要簡單的用`1 << i`便可以達到2的i次方的目的。

* `2147483647(?`:

要做出 `2147483647` 只要使用 `~(1 << 31)` 就可以了，也不會很難理解。

* 判斷兩數相等:

`a ^ b == 0`

* 兩數互換:

兩數互換有一種最簡單的方式，是使用:

        int temp = x;
        x = y;
        y = temp;

但是還有一種不需要新變數的單行寫法 ([XOR Swap Algorithm](https://en.wikipedia.org/wiki/XOR_swap_algorithm)) :

        x ^= y ^= x ^= y;

這樣可能不太好理解，我們可以把它拆開來看:

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

> **引理:**
> XOR 位元運算具有下列性質
> 1. 交換律: $A\oplus B=B\oplus A$
> 2. 結合律: $(A\oplus B)\oplus C=A\oplus (B\oplus C)$
> 3. 單位元素: $A\oplus 0=A$
> 4. 元素是自己的反元素: $A\oplus A=0$

1. $X_1 = X_0\oplus Y_0$
2. $Y_1 = Y_0 \oplus X_1 = Y_0 \oplus X_0 \oplus Y_0 = X_0 \oplus (Y_0 \oplus Y_0) = X_0 \oplus 0 = X_0$
3. $X_2 = X_1\oplus Y_1 = (X_0\oplus Y_0)\oplus X_0 = (X_0\oplus X_0)\oplus Y_0 = 0\oplus Y_0 = Y_0$