--- 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$ 。 ![](https://i.imgur.com/Hr0t3Yf.png) --- ## 位元運算子 * **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` * 兩數互換: 兩數互換有一種最簡單的方式，是使用: ```cpp int temp = x; x = y; y = temp; ``` 但是還有一種不需要新變數的單行寫法 ([XOR Swap Algorithm](https://en.wikipedia.org/wiki/XOR_swap_algorithm)) : ```cpp x ^= y ^= x ^= y; ``` 這樣可能不太好理解，我們可以把它拆開來看: ```cpp= 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$