# 位元運算 Bitwise Operation
我們一般看到的數字都是十進位的數字，十進位的數字意旨每十個數字進一位，因此每位數字只能是 $0$~$9$。那麼二進位就是每二個數字進一位，數字只能是 $0$ 或者 $1$。這特性剛好與電路通電與不通電的特性合得來，因此電腦的底層儲存的都是二進位的數字
這篇主要會介紹三個東西 : 不同的進位制、資料型態儲存、布林代數。透過這三者，我們才能完整地介紹位元運算，最後會介紹位元運算在競賽上的常見用法
## 不同進位數字的表示法
### 範例說明
基本上就是數字加小括號，右下角加小標代表進位制
- 十進位 : $(1782)_{10}$
- 二進位 : $(1011)_{2}$
- 八進位 : $(3254)_{8}$
### 換種方式來看十進位、二進位與八進位
我們可以把十進位數字 $(1782)_{10}$ 粗略的這樣做拆分
$$
(1782)_{10}=1\cdot 10^{3}+7\cdot 10^{2}+8\cdot 10^{1}+2\cdot 10^0
$$
二進位數字 $(1011)_{2}$ 大概就會長這樣
$$
(1011)_{2}=1\times 2^3+0\times 2^2+1\times 2^1+1\times 2^0=(11)_{10}
$$
八進位數字 $(3254)_{8}$ 大概就會是長這樣
$$
(3254)_{8}=3\cdot8^3+2\cdot8^2+5\cdot8^1+4\cdot8^0=(1708)_{10}
$$
### $k$ 進位數字
藉由上面的規律不難發現，今天若有一個 $k$ 進位的數字，我們知道他共會由 $0$~$k-1$ 這些符號組成。設一個序列長度為 $n$ 的 $k$ 進位數字 $a$，轉成十進位可以寫成這種形式 :
$$
a_{n-1} \cdots a_2a_1a_0=a_{n-1} \cdot k^{n-1}+\cdots+ a_2\cdot k^2+a_1\cdot k^1+a_0\cdot k^0
$$
### 十六進位
十六進位在資訊領域也是蠻常見的，基本上會把 $10$\~$15$ 寫成 $A$\~$F$。轉換方法跟前面提及的差不多，很 trivial 所以在此不多贅述
### 實作十進位轉八進位
由於十進位與二進位以外的進位法難以用現有的資料型態表達，所以直接使用字串來做為輸出。若要手算的話，短除法就可以達成了，在程式上也是差不多的作法，只是用 `while` 迴圈來實作
```cpp
string convert(int x){
string ret;
while(x > 1){ // 除到變成 1 就完成了
ret.push_back('0' + x % 8); // 這邊就取餘數就好，記得要轉成字元
x /= 8; // 短除法，每次除 8
}
reverse(ret.begin(), ret.end()); // 因每次都 push_back()，最後要反過來
return ret;
}
```
要轉成其他進位制也很 trivial，請自己當作練習試試看
## 資料型態的儲存
這邊只是粗淺地講 C/C++ 中各資料型態是怎麼儲存。如果想知道完整的知識，可以去學計算機組織與架構、計算機概論與數位邏輯設計，這些課應該都會提到
### 原理說明
電腦是通過電壓的大小 (high / low) 來看要存哪一種資料，因此只會有兩種狀態 : $0$、$1$。在每一個位元 (bit) 中，我們只會用 $0$、$1$ 表示，bit 是儲存資料的基本單位，想像成格子就好
### 整數 int
電腦中儲存整數有固定的大小，每個 int 用 $4$ bytes 也就是 $32$ bits 儲存，可以用 $32$ 個格子來表示
#### Sign Bit
第一個格子叫做 sign bit，如果是 $0$ 就是正的 $1$ 就是負的
<center>
<img src="https://hackmd.io/_uploads/S1HDY1_teg.png" style="margin: 0 auto; display: block; width: 600px">
</center>
#### 舉例說明
以一個 $3$ bit 的系統來說，所有能代表的數字大概長這樣
|bit|value|
|---|---|
|011|3|
|010|2|
|001|1|
|000|0|
|111|-1|
|110|-2|
|101|-3|
|100|-4|
這種表示法叫做二補數，如果要把正的變成負的就要把 $0$ 變成 $1$、把 $1$ 變成 $0$，然後 $+ 1$，然後你就會發現最後的 $-4$ 不適用
### 浮點數 float
用 $4$ bytes 也就是 $32$ bits 儲存，大致可以分為三個部分 :
- sign : 正負號($S$)
- exponent : 位移量($E$)
- mantissa : 尾數($M$)
<center>
<img src="https://hackmd.io/_uploads/SyjgpkuKee.png" style="margin: 0 auto; display: block; width: 600px">
</center>
一個浮點數寫起來就會是 $S\times M\times 2^E$
#### 舉例說明
**$7.25$ 化成浮點數儲存**
1. 判斷正負 : 正
2. 將其化為二進制 : $111.01$
3. 將小數點移到最前面 : $1.1101$
發現位移量為$2$ 並捨去最前面的$1$
4. 計算 $E$ 加上 $2^8-1$ 其中 $8$ 為格子數量 : $E=(2^8-1)+2=(129)_{10}=(1000 0001)_{2}$
5. 寫答案 : $01000000111010000000000000000000$
**可以驗算一下答案**
$S=+1$
$E=129-127=2$
$M=(0.1101)_{2}+1=1.8125$
$S\times M\times 2^E=7.25$
### 備註
- 因為格子都是有限的，所以當紀錄的數字超出格子時就會溢位，導致數字出現錯誤
- 以上浮點數看不懂沒關係，不是資工系其實沒必要知道
## 布林代數
電腦處理位元運算是基於電路的邏輯閘，邏輯閘的基礎是基於布林代數，所以先來講講布林代數在幹嘛
### 簡介
布林代數是由[喬治·布爾](https://zh.wikipedia.org/zh-tw/%E4%B9%94%E6%B2%BB%C2%B7%E5%B8%83%E5%B0%94)提出。主要是處理邏輯問題，將邏輯從哲學轉化成數學。整個代數只有兩種元素 : $\text{Ture}$ ($1$), $\text{False}$ ($0$)，有時會寫成 T/F。這東西被信息學之父[克勞德·香農](https://zh.wikipedia.org/zh-tw/%E5%85%8B%E5%8A%B3%E5%BE%B7%C2%B7%E9%A6%99%E5%86%9C)用於處理電路問題，現今主要用於數學論證與電路設計上 ||討厭數位邏輯設計的，應該知道要怪誰了吧||
### 運算子
主要有三種運算子
- OR $\lor$ : 或
- AND $\land$ : 且
- NOT $\neg$ : 否
要注意的是，OR $\lor$ 跟 AND $\land$ 是二元運算子 (左右各放一個數字)，NOT $\neg$ 是一元運算子 (只能放右邊的數字)
### 真值表 Truth Table
我們可以用「真值表」來看所有的運算，有課本寫說真值表就是運算子的定義。左邊是 $P$、$Q$ 分別代入的數字 (T/F)；右邊是運算結果
**這是 OR $\lor$ 跟 AND $\land$ 的真值表**
|$P$|$Q$|$P\lor Q$|$P\land Q$|
|----|----|----|----|
|0|0|0|0|
|0|1|1|0|
|1|0|1|0|
|1|1|1|1|
**這是 NOT$\neg$ 的真值表**
|$P$|$\neg P$|
|----|----|
|0|1|
|1|0|
### 互斥或 XOR
有了上面三個運算子，我們就可以進行運算，也可以創造出新的運算子。接下來的 XOR $\oplus$ 運算子也算是很常用的運算子，真值表如下
|$P$|$Q$|$P\oplus Q$|
|----|----|----|
|0|0|0|
|0|1|1|
|1|0|1|
|1|1|0|
以下真值表也可以當作我們合成新運算子的工具，算是我們從基本的 AND、OR 與 NOT 推導出來的結果
|$P$|$Q$|$P\lor Q$|$P\land Q$|$\neg(P\land Q)$|$(P\lor Q)\land \neg(P\land Q)$|$P\oplus Q$|
|----|----|----|----|----|----|----|
|0|0|0|0|1|0|0|
|0|1|1|0|1|1|1|
|1|0|1|0|1|1|1|
|1|1|1|1|0|0|0|
會發現 $(P\lor Q)\land \neg(P\land Q)$ 與 $P\oplus Q$ 的真值表是相同的，這時我們就可以寫作 :
$$
P\oplus Q\equiv (P\lor Q)\land \neg(P\land Q)
$$
符號 $\equiv$ 我們稱為邏輯等價
### 用於敘述
設 $P$、$Q$ 敘述分別為「會下雨」、「地面會溼」，那這樣的敘述「若下雨，則地板會溼」就可以寫成 $\neg P\lor Q$，可以用真值表來寫寫看
|情況|$P$|$Q$|$\neg P\lor Q$|結果|
|----|----|----|----|----|
|沒下雨、地面沒溼|0|0|1|成立 (沒有下雨，無論地面有沒有溼都是對的)|
|沒下雨、面板溼|0|1|1|成立 (同上)|
|下雨、地面沒溼|1|0|0|不成立|
|下雨、地面溼|1|1|1|成立|
冷知識 : 「若 $p$ 則 $q$」的邏輯我們會用運算子 $p\rightarrow q$ 來表示
### 備註
這部分非常深，簡化這些邏輯有非常多技巧，在不同領域應用也很多，建議自己找書來看。關鍵字如下 :
- [mathatical logic](https://www.reddit.com/r/math/comments/1418n9n/whats_a_good_book_to_learn_rigorous_mathematical/)
- [digital logic design](https://www.tenlong.com.tw/products/9789867696274)
## 位元運算
當我們使用布林代數來處理位元問題時，就稱為位元運算。為了與邏輯運算做出區隔，跟別人講的時候記得加上 (bitwise)，比如說 bitwise OR、bitwise AND 等等
### 位元運算子
邏輯運算與位元運算的整體使用起來非常相似，只是邏輯運算只作用於一個 T/F，位元運算則是作用於一整排 int (bit string) 上的 0/1
|運算|邏輯運算子|位元運算子|
|---|---|----|
|OR|$\lor$|\||
|AND|$\land$|&|
|XOR|$\oplus$|^|
|NOT|$\neg$|\~|
比較特別的是 $>>$、$<<$，在十進位的意思就是 $\div 2$、$\times 2$，但是在二進位的意思就是左移與右移
|運算|數學運算子|位元運算子|
|---|---|---|
|左移|$\div 2$ (向下取整)|<<|
|右移|$\times 2$|>>|
舉例來說
$$
5 \times 2 = 5 << 1 = (101)_2 << 1=(1010)_2=10
$$
$$
5 \div 2 = 5 >> 1 = (101)_2 >> 1=(10)_2=2
$$
左移後最右邊的位置要補 $0$
**注意 : C 語言中的位元運算子只適用於整數 int**
### 舉例說明
**在 C 語言寫 `5|6` 就會得到 $7$ :**
- $5=(101)_{2}$、$6=(110)_{2}$
<center>
<img src="https://hackmd.io/_uploads/Hy4nrl_Yxe.png" style="margin: 0 auto; display: block; width: 600px">
</center>
**在 C 語言寫 `5^6` 就會得到 $3$ :**
- $5=(101)_{2}$、$6=(110)_{2}$
<center>
<img src="https://hackmd.io/_uploads/SJ9NLlOFle.png" style="margin: 0 auto; display: block; width: 600px">
</center>
### 備註
- 這些位元運算子也可以加個`=`變成賦值運算子
- 由於位元運算子在 C 語言優先度非常低，要使用時記得括號括好
- 有一個好用的函式 `__builtin_popcount()`，可以帶入數字計算二進位中 $1$ 的數量
## 程式範例
### 二進位轉十進位
可以先用字串儲存二進位
```cpp
// bi[]: 輸入的字串, ans: 儲存答案
void binary_to_decimal(char bi[], int &ans){
int len = strlen(bi), ret = 0, ep = 1;
// len: 字串長度, ret: 紀錄運算過程, ep: 2的次方數
for(int i = len - 1; i >= 0; i--){
ret += (bi[i] - '0') * ep;
ep <<= 1;
}
ans = ret;
}
```
### 十進位轉二進位
答案以字串儲存
```cpp
void decimal_to_binary(int &n, char ans[]){
int idx = 0; // 這就是陣列編號
while(n){ // 這過程相當於短除法
ans[idx++] = (n & 1) + '0'; // (n & 1) 就是 (n % 2)
n >>= 1; // 除以 2
}
ans[idx] = '\0'; // 字串末尾一定要加上 '\0'
int len = strlen(ans); // 字串長度
for(int i = 0; i < len / 2; i++){ // 字串前後reverse過來
char tmp = ans[i]; // 做交換
ans[i] = ans[len - 1 - i];
ans[len - 1 - i] = tmp;
}
}
```
## 位元運算常見應用
以下這些都是常見手法，你可以自己寫寫真值表看檢驗是不是正確的。如果你是個注意力驚人的同學，應該可以注意到更多「trivial」的做法 (?
### 計算 $2^i$
```cpp
int ans = (1 << i); // 1 向左移 i 格就是算完了，輕輕鬆鬆
```
### 找出整數 $s$ 的第 $i$ 位 bit 是 $0$ 還是 $1$
```cpp
int ans = s & (1 << i);
if (ans) cout << "1"; // 若不為 0 則 ans 會是 2^i
else cout << "0"; // 若為 0 則 ans 會是 0
```
### 整數 $x$ 除以 $2$ / 乘以 $2$
```cpp
int d = x >> 1; // x 除以 2
int m = x << 1; // x 乘以 2
```
注意到 $x\cdot 2^i$ 就可以這樣寫
```cpp
int d = x >> i; // x 除以 2^i
int m = x << i; // x 乘以 2^i
```
小心這裡的除法都是向下取整，因為資料型態 `int` 無法儲存到小數位
### $0$/$1$ 取反
```cpp
x = ~x; // 其實就是 bitwise NOT
```
### 取整數 $a$ 的補數
前面有提到我們用的系統是二補數的整數系統，因此以下兩種寫法是一樣的 (不溢位的話)
```cpp
int ans = -a;
```
```cpp
int ans = (~a) + 1;
```
### 將 $s$ 的第 $i$ 位設為 $1$
如果第 $i$ 位已經是 $1$ 了，就不會改到任何的值
```cpp
s |= (1 << i);
```
### 將 $s$ 的第 $i$ 位 $0$/$1$ 翻轉
望周知，這種寫法不會改變第 $i$ 位以外的值，因為 $0\oplus0=0$ 且 $1\oplus 0=1$
```cpp
s ^= (1 << i);
```
### 將 $s$ 的第 $i$ 位設為 $0$
如果第 $i$ 位已經是 $0$ 了，就不會改到任何的值
```cpp
s &= ~(1 << i);
```
### 求出 $x$ 最低的 $1$ 在第幾位
假設答案是第 $i$ 位，這裡會回傳 $2^i$
```cpp
int ans = x & -x;
```
### 判斷整數 $x$ 是不是 $2$ 的冪次
```cpp
return (x & -x) == x;
```
### 整數 $x, y$ 交換
相當於 `swap(x, y)`
```cpp
x = x ^ y;
y = y ^ x;
x = x ^ y;
```
**這寫法有點玄，但是容我用幾句解釋 :**
- 設 $z=x\oplus y$，則 $z$ 所儲存的是「每一位是否不同」的 bit string
- $x\oplus z$ 就是 $x$ 把每一位與 $y$ 不相同的 bit 翻轉
- $y\oplus z$ 就是 $y$ 把每一位與 $x$ 不相同的 bit 翻轉
**舉個例子 :**
$x=10$ 與 $y=12$ 交換得到 $x'=12$ 與 $y'=10$
|第 $i$ 位|$x$|$y$|$z$ (是否不同)|$x'=x\oplus z$|$y'=y\oplus z$|
|---|---|---|---|---|---|
|4|1|1|0|1|1|
|3|0|1|1|1|0|
|2|1|0|1|0|1|
|1|0|0|0|0|0|
**所以程式碼就是這個意思**
1. 我們把 $z$ 的角色交給 $x$
```cpp
x = x ^ y;
```
2. 接下來把 $y$ 變成原本的 $x$
```cpp
y = y ^ x;
```
3. 最後把原本 $x$ 中「不相同的位元」翻過來
```cpp
x = x ^ y;
```
**最後，這裡還有個噁心的寫法**
```cpp
x ^= y ^= x ^= y;
```
### 判斷整數 $x$ 是不是奇數
這很簡單
```cpp
if(x & 1) cout << "YES\n";
else cout << "NO\n";
```
## 題目練習
[Zerojudge c461. apcs 邏輯運算子 (Logic Operators)](https://zerojudge.tw/ShowProblem?problemid=c461)
[Zerojudge e797. p4. 數位邏輯運算](https://zerojudge.tw/ShowProblem?problemid=e797)
[Zerojudge a132. 10931 - Parity](https://zerojudge.tw/ShowProblem?problemid=a132)
[Zerojudge b005. 布林矩陣的等價短陣](https://zerojudge.tw/ShowProblem?problemid=b005)
[Zerojudge a414. 位元運算之進位篇](https://zerojudge.tw/ShowProblem?problemid=a414)
[Zerojudge d632. C and S ??](https://zerojudge.tw/ShowProblem?problemid=d632)
[Zerojudge e253. a + b problem](https://zerojudge.tw/ShowProblem?problemid=e253)
[Zerojudge e545. 10019 - Funny Encryption Method](https://zerojudge.tw/ShowProblem?problemid=e545)
[Zerojudge e799. p6. 資工系的浪漫](https://zerojudge.tw/ShowProblem?problemid=e799)
[CSES Range Xor Queries](https://cses.fi/problemset/task/1650/) (bitwise XOR 可以差分喔)
[CSES Prime Multiples](https://cses.fi/problemset/task/2185)
----
## 參考資料
- [海大競程 - Time Complexity and Bitwise](https://hackmd.io/@LeeShoWhaodian/ComplexityandBitwise#/)
- [維基百科 - Bitwise operation](https://en.wikipedia.org/wiki/Bitwise_operation)
- [台師大演算法筆記 - bit](https://web.ntnu.edu.tw/~algo/Bit.html)
- [哈哈屁眼 - 位元運算](https://hackmd.io/@HAHAHAHAHA/bitwise)
----
> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/8/25
Sign in with Wallet
Connect another wallet