---
# System prepended metadata

title: 位元運算

---

# 位元運算

## 進位制
人類使用進位制以有限數字表達無限大小，常見的進位制有:十進位、二進位、八進位、十六進位等，我們平常使用的就是十進位制(因為人類有十根手指)。

關於進位制的計算方式，會是以當前位數(以0為初始，從右往左數)作為上標，再將每位相加。我以十進位舉例如下:
```
314 = 3 x 10^2 + 1 x 10^1 + 4 x 10^0
```
以同樣的方式我們可以計算其他進位制的大小，我給幾個數字，你可以先試看看:
```
0b1011 = 11 // ob開頭表示二進位(binary)

0o125 = 85// 0o開頭表示八進位(octal)

// 十六進位數以數字0~9和英文字母a(10)~f(15)組成
oxA7 = 167 // 0x開頭表示十六進位(hexadecimal)
```

在計算機中，我們使用二進位表示一切，包括圖片，原因是二進位最好實現，可以簡單的用1和0分別表示電路通電和不通電(高電壓和低電壓)。

## 位元運算
計算機中的每一位二進位數稱作**位元(bit)**，而為了方便管理，將每八位元定義為**位元組(byte)**。

位元運算就是將數字逐位元的計算，不常用，但在某些地方會有奇效。

|    位元運算子    |    名稱   |
|    -----    |    --    |
|    &    |    AND   |
|    \    |    OR    |
|    ^    |    XOR    |
|    ~    |    補數    |
|    <<    |    左移    |
|    >>    |    右移    |

>[!Note]使用位元運算時請注意運算子的優先順序!

### & 和 |
| & | a為0 | a為1 |
| --- | ---- | ----- |
| b為0 | 0 | 0 |
| b為1 | 0 | 1 |

| \| | a為0 | a為1 |
| -- | ---- | ----- |
| b為0 | 0 | 1 |
| b為1 | 1 | 1 |

可以發現它們的名字和邏輯運算子相同，兩者確實有一定的相似性，但不是同種東西。

因為我們會將數字轉成二進位來看，因此只會有0和1的比較。當進行AND運算時，除非兩者皆為1，否則為0 ; 進行OR運算時，除非兩者皆為0，否則為1。

```cpp=
// << 和 >>的優先級大於&和|，因此需要括號防止邏輯錯誤
cout << (5 & 9) << "\n";     // 5 & 9 => 0101 & 1001 => 1
cout << (7 | 11) << "\n";   // 7 | 11 => 0111 | 1011 => 1111 => 15
```
output
```
1
15
```
在除數是2的冪次時，&可以代替%進行更有效率的取餘數，像是判斷某數是否為偶數時一般是寫```a % 2 == 0```，但可以用AND寫成```(a & 1) == 0```。
```cpp=
int num = 5;
if ((num & 1) == 0) // 0101 & 0001 -> 0001 = 1
    cout << num << "是偶數" << "\n";
else
    cout << num << "是奇數" << "\n";
```
output
```
5是奇數
```

### ^
XOR有一種很特殊的轉換方式，因此常用於訊息加密，規則如下
| ^ | a為0 | a為1 |
| --- | ---- | ----- |
| b為0 | 0 | 1 |
| b為1 | 1 | 0 |

你可以理解為 : 當兩數相異且不為零時等於1，否則為0。

從這規則可以推導出XOR的3大特性 : 
1. 相同數字經過 XOR 後會等於0 
    ```
    a ^ a => 0
    ```
2. 任何數和0 XOR 後會等於自己
    ```
    a ^ 0 => a
    ```
3. XOR運算具有交換律
    ```
    a ^ 0 => 0 ^ a
    ```
----

根據上述特性，我們主要可對XOR進行兩種應用
#### 1. 進階兩數交換 
當我們想將兩個變數內的值進行互換時，最直覺的方法是使用第三個變數儲存，這在之前就說明過了，雖然簡單，但有一個缺點，為了暫存值我們被迫創建了一個不怎麼會使用的變數，從而消耗了更多的記憶體，而這是可避免的，方法是使用XOR來代替。
```cpp=
int a = 3, b = 5;

a ^= b; // a = 011(a) ^ 101(b) => 0110 => 6 , b = 5
b ^= a; // b = 101(b) ^ 110(a) => 0011 => 3 , a = 6
a ^= b; // a = 110(a) ^ 011(b) => 0101 => 5 , b = 3

cout << "a = " << a << "\n";
cout << "b = " << b << "\n";
```

如果要追求簡潔，你甚至可以寫成
```cpp=
int a = 3, b = 5;

a ^= b ^= a ^= b;

cout << "a = " << a << "\n";
cout << "b = " << b << "\n";
```

output
```
a = 5
b = 3
```
上述程式有一個小bug，就是當a和b相等時，使用XOR交換會導致兩者的值皆變為零，因此請加上一個a和b不相等的判斷:
```cpp=
void swap(int &a, int &b) {
    if (a != b) {
        a ^= b ^= a ^= b; // 這樣就完美啦!
    }
}
```

#### 2. Single Number
這是一種**演算法**問題，有很多種解法，而使用XOR是最優解的其中之一。

問題描述 : 給定一個由整數組成的列表，陣列中大部分的數皆兩兩成對，唯有一個例外，請找出該陣列中只出現過一次的數值。
```
example : [1, 2, 2, 4, 3, 1, 3] => single number = 4
```

想想看剛才提到的XOR三大特性，該怎麼運用他們解決 ? 

<details>
<summary>Answer Code</summary>
    
```cpp=
int nums = {1, 2, 2, 4, 3, 1, 3};
int singleNum = 0;
    
for (const int& num : nums)
    singleNum ^= num;

    cout << singleNum << "\n";
```
</details>

讓我們看看為什麼可以這樣寫 : 首先，根據XOR的交換律，```[1, 2, 2, 4, 3, 1, 3] => [1, 1, 2, 2, 3, 3, 4]``` ; 再來，把這些數字都進行XOR，根據**相同數經過XOR會得到0**和**任何數經過XOR都會得到自己**的特性，可以寫成下列樣式
```
1 ^ 1 => 0
2 ^ 2 => 0
3 ^ 3 => 0
0 ^ 4 => 4
```
因此，我們成功的找出了single number。

題目連結
- [136. Single Number](https://leetcode.com/problems/single-number/description/)

##### AC Code (0ms, 20.81MB)
<details>
<summary>Code</summary>
    
```cpp=
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(const int &num : nums){
            ans ^= num;
        }
        return ans;
    }
};
```
</details>

### >> 和 <<
就只是乘除2的冪次而已，稍快於*和/
```cpp=
int num = 10;
    
cout << num << " << 2 = " << (num << 2) << "\n";
// 10 => 01010 => 00010 => 2
    
cout << num << " >> 2 = " << (num >> 2) << "\n";
// 10 => 0001010 => 0101000 => 4
```

output
```
10 << 2 = 40
10 >> 2 = 2
```

將數字轉成二進位來看更明顯，左移是將每位元往左移動，跑出去的零丟到後面，也就是乘2 ; 右移則是將每位元往右移動，比較特別，整除時是除以2，但不整除時會有一種叫位元遮罩的東西，不管是0 和 1都會捨棄。

## ~ 
補數運算的規則很簡單，0變成1 ; 1變成0。
| 補數 | a為0 | a為1 |
| --- | ---- | ----- |
| 結果 | 1 | 0 |

值得一提的是，它負責處理電腦二進位的減法邏輯，是負數的轉換方法，稱為「**二補數**」。

以int型態的11舉例，其二進位為
```
00000000 00000000 00000000 00001011
```
而-11的二進位數字就是將11進行補數運算後的結果
```
11111111 11111111 11111111 11110100 
```

## 總結
計算機以二進位表示一切，而二進位數字間有獨特的運算方式，稱作**位元運算**。

位元運算共有六種，分別為```&、|、^、~、<<、>>```，其中```&```用來進行二冪次的取餘數，```^```用來進行兩數交換，```~```可以轉換二進位制下的負數，```|```則是幾乎不會使用到。