# 數值系統 整數，無號數
###### tags: `Computer System`
<!-- :::info
https://www.bilibili.com/video/BV1iW411d7hd?p=3
https://hackmd.io/@sysprog/CSAPP/https%3A%2F%2Fhackmd.io%2Fs%2FrJoxSsiuG?type=book&fbclid=IwAR05tfXp9v7Q_MZVey5kh5nsV7loKIMApnahj2aDkzo1dNGG8lasZhw2eJU
https://www.bilibili.com/video/BV1fC4y147iZ?p=5
::: -->
## 數值系統簡介
在數值系統中，要討論的部分為如何表示一個數字，在這邊我們先關注對於一個正整數，我們應該如何進行表示。
在我們的文化中，我們最常接觸到的數值系統，莫過於 10 進位制，也就是逢 10 即進位，如下面所展示
```
0 1 2 3 4 5 6 7 8 9 10 (進位)
```
而在時間上，每過 60 秒即為 1 分鐘，這種每過 60 個單位，就進位的表示法，稱為 60 進位制。
在電腦系統中，常見的進位制為 2 進位，8 進位，16 進位。
以下為 8 進位制的展示
```
0 1 2 3 4 5 6 7 10 (進位)
```
在 16 進位中，我們需要思考如果超過了 9，在不進位的前提下我們應該如何表示? 在 16 進位中我們將 10 到 15 以 A 到 F 進行表示，如下面所展示
```
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E F
```
對於一個 10 進制的數值 1234，我們可以將其表示成以下
$1234_{10}$ = `1000 + 200 + 30 + 4`
`1234_10` 表示為 1234 為一 10 進位制下的數值
1 位於千位數
2 位於百位數
3 位於十位數
4 位於個位數
我們可以將其表示成以下
```
1234_10 = 1 * 10^3 + 2 * 10^2 + 3 * 10^1 + 4 * 10^0
```
`10^n` 表示為 10 的 n 次方
而如果 1234 為一個 16 進位數，則為以下
```
1234_16 = 1 * 16^3 + 2 * 16^2 + 3 * 16^1 + 4 * 16^0 = 4660_10
```
這裡我們可以簡單的得到一個通式，對於一個在 B 進制底下的 n 位數，其數值轉換可以表示成以下
$d_{n-1}d_{n-2}...d_1d_0$
$= d_{n-1} * b_{n-1} + d_{n-2} * b_{n-2} + ... d_1 * b_1 + d_0 + b_0$
整個電腦中所有東西皆以數值進行表示，我們可以將數值視為一個字元，或是記憶體中的某一個地址等等，但是我們要怎麼知道一個數值背後所表示的意思? 這取決於我們如何看待這一些數值，數值可以表示以下資訊
- 字元 (character)
- 也許我們可以使用一個 $2^5$ 的二進位數表示所有小寫字母的組合，以 `00000` 表示 'a'，以 `11001` 表示 'z'。
- 如果加上了大寫符號，標點符號等等，我們可能會需要 $2^7$ 來表示這全部的組合，而對於一個 $2^7$ 數和大小寫符號以及標點符號的對應關係表，我們稱為 ASCII 表。
- 邏輯符號 (boolean)
- 使用一個 $2^1$ 表示邏輯真和假，`0` 表示為假，`1` 表示為真
- 顏色 (color)
- 使用一個 $2^2$ 表示三原色，`00` 表示紅色，`01` 表示藍色，`10` 表示綠色
- 對於一張灰階圖片，也就是只有黑色和白色的圖片，如果只使用 `0` 表示黑色，`1` 表示白色，圖片會變得如何?
- 如果 `0000,0000` 表示黑色，`0000,0100` 表示有一點點白的黑色，`1111,1111` 表示為白色，在黑色和白色之間有 255 個過渡色，圖片會是如何?
source: [1 bit, 2 bits, 3 bits, 4 bits, 5 bits, and 8 bits](https://theasc.com/magazine/april05/conundrum2/image11.html)
上圖為當我們使用 1 個二進位數黑白，2 個二進位數一路到 8 個二進位數表示黑白的比較。
**位元 (bit)**: 1 個二進位數，又稱為一個 bit
**位元組 (bytes)**: 8 個二進位數所組成，稱為一個 bytes
**色深 (color depth)**: 儲存一個像素所使用的位元數，如果色彩深度為 1 位元，表示一個像素只有 $2^1$ 個顏色可以選擇，黑色或是白色。
二進位制可以將任何信號進行量化表示，如上面黑白影像的例子，我們可以將數位影像視為一種訊號，我們可以使用二進制表示訊號，也就是表示整個影像，每一個像素點使用一個二進位制數進行表示。
下面為一個數位信號
source: [Digital_signal](https://en.wikipedia.org/wiki/Digital_signal#/media/File:Digital-signal-noise.svg)
如果我們將某一個電壓範圍表示為 0，某一電壓範圍表示為 1，在考慮到電流中存在電阻，干擾，噪聲等等雜訊的情況下，只要表示的範圍不超過我們所設定的閥值，我們就可以得到一個清晰的訊號。
在考慮抗干擾的情況下，數位處理相比於模擬處理訊號來得更加的有優勢。
二進位制的優勢
- 對於一個電路的實現，0 表示低電位，1 表示高電位，電路實作上較為簡單
- 可以簡單的表示邏輯，低電位對應到 0，0 對應到為假，高電位對應到 1，1 表示為真 (非 0 即為真)
- 僅使用兩種狀態表示訊號，對於數據的儲存，傳遞，處理都來得更加的可靠 (儲存一個訊號的數位數值比模擬一個訊號數值來得簡單的許多)
關於一個數字的表示，也就是在數值系統中，我們主要討論三個部分
- 無號數 (unsigned): 基於傳統的二進位表示法，表示大於或是等於 0 的數字
- 補數 (two's-complement): 表示有號數的最常見方式
- 浮點數 (floating-point): 表示一個實數，以 2 作為底數
在電腦中我們是使用有限的 bit 去表示一個數字，當數值結果過大以至於我們不能夠表示時，就會產生溢位 (overflow) 的現象，諸如產生兩個數字相乘產生負數的結果等等。
對於一個整數的計算，應該滿足一些運算性質，如在乘法的計算中，需要滿足結合律與交換律，考慮以下 C 語言表達式，都會產生出相同的結果
```c
#include <stdio.h>
int main(void)
{
printf("%d\n", (500 * 400) * (300 * 200));
printf("%d\n", ((500 * 400) * 300) * 200);
printf("%d\n", ((200 * 500) * 300) * 400);
printf("%d\n", 400 * (200 * (300 * 500)));
}
```
output
```
-884901888
-884901888
-884901888
-884901888
```
但是對於浮點數的計算，由於浮點數的精度有限，浮點數運算上的結合律可能會無法滿足，考慮以下實作
```c
#include <stdio.h>
int main(void)
{
printf("%f\n", (3.14 + 1e20) - 1e20);
printf("%f\n", 3.14 + (1e20 - 1e20));
}
```
output
```
0.000000
3.140000
```
正整數表示的數字範圍是有限的，也就是表示的是一個較小的數字範圍，因此是精確的，而對於浮點數，浮點數表示的是實數集合，實數集合中的數字範圍是無限的，因此浮點數表示實際上表示的是一個近似的結果。
<!-- ## 關於 `hello world.c`
以下為 `hello world.c` C 語言程式碼
```c
#include <stdio.h>
int main(void)
{
printf("Hello World");
return 0;
}
```
`hello world.c` 為一個 C 語言檔案，本質上，其實就是由 0 和 1 所組合而成的一個檔案，而在現代電腦系統中，一個字元 (character) 和其背後的二進位表示的對應，我們會使用 ASCII 進行表示，如下面所展示
source: [ASCII Table: Printable Reference & Guide](https://www.alpharithms.com/ascii-table-512119/)
在 `hello world.c` 這個檔案中，第一個字元為 '#'，在 ASCII 表中對應到的十進位表示法為 35，對應的二進位為 `0010,0011`，我們可以使用這樣的方式，使用二進制表示整個 `hello world.c` 這個檔案。
從這裡我們可以看到一個主要的想法，在電腦系統中所有的資訊，如檔案，記憶體中的數據等等，都是使用一連串的 bit 構成，而對於一個整數，浮點數，負數等等，也是使用 bit 構成，對於數值與 bit 之間的關係，我們將在下面進行討論。
## 關於布林值與布林運算
對於二進位數，我們時常會使用到布林運算子，而布林運算子包含 AND, OR, NOT, XOR 等，以下範例
## 關於負數與補數
在上面我們看到了一個二進位無號數如何轉換成十進位數，也就是上面提及的 $B2U$，而對於一個有號數，也就是考慮到負數的情況，我們將最高位視為負數，其他位視為正數，公式如下
$B2T(X) = -x_{w-1} * 2^{w-1}+\sum_{i=0}^{w-2}x_i*2^i$
概念上為下面所表示，假設有一個二進位有號數 `1,0110`
對於二進位有號數，有時候我們會將最左方的位稱作為有號位 (signed bit)，1 表示為負數，0 表示為正數。上面我們看到了
## 關於浮點數
在上面我們看到的都是正整數的處理， -->
## word size
每一台電腦都有一個 字組 (word size)，word size 決定了電腦中暫存器大小，許多暫存器大小是一個 word size 的大小，CPU 和記憶體之間資料傳送單位也是一個 word size，一個指標變數的大小也是該電腦系統 word size 的大小，word size 決定了一台電腦中虛擬記憶體能夠存取的記憶體空間大小，對於一台 32 位元的機器，虛擬記憶體的存取範圍為$0 \sim 2^{32} - 1$，也就是一個 Process 能夠存取的記憶體地址範圍。
如果一台電腦中總共有 16 GB 的實體物理記憶體，但卻執行在 32 位元的系統下，由於 32 位元的虛擬記憶體存取範圍最大大約 4GB，因此並無法有效利用多餘的實體物理記憶體地址。而對於 64 位元的電腦，最大虛擬記憶體地址為 16EB。
對於一個程式，我們可以把它編譯成 32 位元或是 64 位元的程式，如果使用 gcc 進行編譯，只要在後面加上編譯選項便可以完成
```c
gcc test.c -m32
```
如此我們就可以把程式編譯成 32 位元的程式，這個 32 位元的程式可以在 32 或是 64 位元的電腦上執行，而如果使用編譯選項 `-m64` 編譯成 64 位元的程式，則只能在 64 位元的電腦上執行。對於一隻程式，無論是 32 位元的程式還是 64 位元的程式，差別在於程式如何被編譯，而不是能夠在什麼樣的電腦上面執行。
在 C 語言中支援了許多的型別，包含整數，浮點數等等，如下表所示
可以看到對於 long 型別，編譯成 32 位元的程式和編譯成 64 位元的程式大小並不相同，以下使用 godbolt 進行實現，分別使用 `-m64` 和 `-m32` 進行編譯以下程式碼
```c
#include<stdio.h>
int main(void)
{
printf("%d", sizeof(long));
}
```
`-m32` 結果
```
ASM generation compiler returned: 0
Execution build compiler returned: 0
Program returned: 0
4
```
`-m64` 結果
```
ASM generation compiler returned: 0
Execution build compiler returned: 0
Program returned: 0
8
```
而為了避免型別的資料表示範圍依賴於編譯器是如何對程式進行編譯，在 ISO C99 中引入了一種資料型別，資料表示範圍固定，不隨著編譯器和電腦環境所變化，分別為 `int32_t` 和 `int64_t`
`int` 型別不一定是 32 bit，有可能在不同的機器會有不同的情況，如果要保證 `int` 資料型別的位元數，可以使用 `int32_t`。使用 `int32_t` 可以保證 32 bit，但是注意到，並不保證 `sizeof(int32_t) == 4`，在某一些平台上，可能 1 bytes 為 16 bit，因此可能會出現 `sizeof(int32_t) == 2` 的情況，`sizeof()` 運算子得到的是位元組數，而非位元數。
使用 `intN_t` 這種型別，還能夠保證一定是使用二補數系統，且不存在陷阱表示法。
### 陷阱表示法
我們可以使用位元組合去表示某一個數字，但並非是所有的位元組合都可以合理的去表示一個數字，如果某一些位元組合可能會造成目標機器嚴重的錯誤，或是導致 trap exception 的發生，我們就稱為這一種位元組合稱之為陷阱表示法。
舉例來說，假設在某一個機器 A 中，使用 32-bit 來表示一個有號整數，最高位為符號位，0 表示為正數，1 表示為負數，並將 0 定義為 `0x00000000`，那麼 `0x80000000` 就是一種陷阱表示法，因為這個值在機器 A 中是沒有意義的。
在一般的運算中，是不會產生出陷阱表示法的，除非我們使用位元運算或是其他違反標準，如溢位等等操作
## 定址模式與位元組順序
假設現在有一個變數 x，型別為 int，存在於記憶體地址 `0x100` 中，也就是 `&x = 0x100`，而假設一個 int 為 4 bytes，則變數 x 的 4 個位元組將被儲存在記憶體中 `0x100`, `0x101`, `0x102`, `0x103` 的位置。
在現今電腦系統中，有兩種常見的位元組順序 (Endianness)，分別為 little endian 和 big endian
- little endian: 在記憶體中按照最低有效位元組到最高有效位元組順序儲存一個物件
- big endian: 在記憶體中按照最高有效位元組到最低有效位元組儲存一個物件
延續上面的假設，假設 x 的值以十六進位進行表示為 `0x01234567`，則使用 big endian 和 little endian 的表示法分別為以下
可以看到在 big endian 中，最高位的十六進位的值為 `0x01`，最低位的十六進位的值為 `0x67`。
對於某一些情況，little endian 與 big endian 會造成許多的問題。
### 第一種情況: 資料傳輸
如兩台不同的機器通過網路進行通訊，如果一台使用 little endian，另外一台使用 big endian，則會發生接收到的位元組變成逆序的。
### 第二種情況: 反組譯
假設有一段針對於 Intel x86-64 處理器的機器語言
```
4004d3: 01 05 43 0b 20 00 add %eax,0x200b43(%rip)
```
這邊可以看到會從 `0x200b43` 取得值和 eax 暫存器的值相加，而我們觀察一下這一段組合語言，對應到的機器語言是 `01 05 43 0b 20 00`，在機器語言中會有某個操作對應到的機器碼和該操作的操作數，我們取出最後 4 個位元組 `43 0b 20 00`，如果去除最後面的 00，並且將數值反向輸出，我們就可以得到 `0x200b43`，可以發現到最低有效位元組在左邊，最高有效位元組在右邊，與書寫的習慣是相反的。
### 第三種情況: 泛用性考量
當我們想要繞過正常的型別規範時，我們就需要面對 big endian 與 little endian 的問題了，在 C 語言中，我們可以通過 union 或是強制轉型將某一個物件以特定型別進行使用，以下為一段 C 語言程式碼，使用了強制轉型印出不同的物件
```c
#include <stdio.h>
typedef unsigned char *byte_pointer;
void show_bytes(byte_pointer, size_t);
void show_int(int);
void show_float(float);
void show_pointer(void*);
void test_show_bytes(int val);
int main(void){
test_show_bytes(12345);
}
void show_bytes(byte_pointer start, size_t len){
size_t i;
for(i = 0; i < len; i++)
printf(" %.2x", start[i]);
printf("\n");
}
void show_int(int x){
show_bytes((byte_pointer) &x, sizeof(int));
}
void show_float(float x){
show_bytes((byte_pointer) &x, sizeof(float));
}
void show_pointer(void *x){
show_bytes((byte_pointer) &x, sizeof(void *));
}
void test_show_bytes(int val){
int ival = val;
float fval = (float) ival;
int *pval = &ival;
show_int(ival);
show_float(fval);
show_pointer(pval);
}
```
在 `show_int()`, `show_float()`, `show_pointer()` 都可以看到將傳入的參數強制轉型成 `unsigned char*`，這邊意義為告訴編譯器要把指標當作位元組序列看待，而多少位元組使用 `sizeof()` 運算子取得某一個型別的位元組數，由於 `sizeof()` 的結果根據不同的機器有不同的值，因此這一段程式碼是相對來說較有移植性的。
而根據這一段程式的輸出，可以看到在不同機器上面是使用 big endian 還是 little endian
在 windows
```
39 30 00 00
00 e4 40 46
f4 fe 61 00
```
在 Linux
```
39 30 00 00
00 e4 40 46
08 01 be b3 ff 7f 00 00
```
12345 的十六進位表示為 `0x00003039`，而在 windows 中可以看到最低有效數 `0x39` 輸出在低位記憶體上，而 Liunx 也是如此，因此判斷這兩個系統都是 little endian。而可以看到，在 Linux 中指標大小為 8 個位元組。
## 布林代數與位元運算
布林代數是在一個二元集合 $\{ 0,1 \}$ 下定義的，在這個集合中定義了四種運算符號，分別為 NOT, AND, OR, Exclusive-OR
### 位元運算應用: 交換兩數，XOR swap
對於任一向量 $a$，具有 $a \wedge a = 0$，運用這個特性，考慮以下程式碼
```c
void inplace_swap(int *x, int *y)
{
*y = *x ^ *y;//Step 1
*x = *x ^ *y;//Step 2
*y = *x ^ *y;//Step 3
}
```
這是一段運用指標交換兩變數的程式碼，而這與常規交換兩個值不同之處在於沒有使用到第三個變數，我們可以參考以下表格看到這個交換變數的過程
<img src = "https://i.imgur.com/x82GUGS.png" width=400>
將上面的程式碼進行延伸，下面為一段反轉陣列的程式碼
```c
#include <stdio.h>
void reverse_array(int [], int);
void inplace_swap(int *, int *);
void print_array(int [], int);
int main(void)
{
int a[4] = {1, 2, 3, 4};
reverse_array(a, sizeof(a) / sizeof(int));
print_array(a, sizeof(a) / sizeof(int));
}
void reverse_array(int a[], int cnt)
{
for(int left = 0, right = cnt - 1; left <= right; left++, right--)
inplace_swap(&a[left], &a[right]);
}
void inplace_swap(int *a, int *b)
{
*b = *a ^ *b;
*a = *a ^ *b;
*b = *a ^ *b;
}
void print_array(int a[], int cnt)
{
for(int i = 0; i < cnt; i++)
printf("%d ", a[i]);
}
```
output
```
4 3 2 1
```
但是如果我們給定長度為奇數的陣列，則反轉的結果便會出現問題，如果將陣列 `a` 設為 `{1,2,3,4,5}`，則會產生以下輸出
output
```
5 4 0 2 1
```
對於這個情況，我們可以思考在 `reverse_array` 的最後一次迭代，也就是 left = 2, right = 2 的情況，我們會發現到這兩個是同一個數字，兩相同數字進行 XOR 運算會得到 0，因此產生了這個現象，只要將判斷式改成 `left < right` 即可解決
### 位元運算應用: 遮罩
假設我們現在有一個數字，`0x89ABCDEF`，如果我們想要保留最後兩位的，我們可以將 `0xFF` 作為遮罩，則我們可以得到 `0x000000EF`。同理，如果我們要保留最後四位，則我們可以將 `0xFFFF` 作為遮罩，我們可以得到 `0x0000CDEF`
### 位元運算應用: 大小寫轉換
以下為使用 `if-else` 的大小寫轉換實作
```c
#include <stdio.h>
char to_upper(char a)
{
if (a >= 'a' && a <= 'z')
a -= 32;
return a;
}
char to_lower(char a)
{
if (a >= 'A' && a <= 'Z')
a += 32;
return a;
}
int main(void)
{
printf("%c\n",to_upper('a'));
printf("%c",to_lower('A'));
}
```
我們可以使用 bit-wise 操作免除使用分支判斷，大小寫字元的 ASCII 編碼相差了 32，我們可以觀察其二進位表示法
```
A = 01000001
a = 01100001
```
如果我們要從 'A' 轉換到 'a'，只需要將 'A' 對 `100000` 進行 OR 操作，即可得到 'A'。
而如果要從 'a' 轉換到 'A'，只需要將 'a' 對 `01011111` 進行 AND 操作，即可得到 'A'。
改寫後的程式碼如下
```c
#include <stdio.h>
char to_upper(char a)
{
return a & 95;
}
char to_lower(char a)
{
return a | 32;
}
int main(void)
{
printf("%c\n",to_upper('a'));
printf("%c",to_lower('A'));
}
```
### 位元運算應用: 二進位加法器
考慮 1 位元情況下的加法所產生的所有可能
```
0 + 0 = 00
0 + 1 = 01
1 + 0 = 01
1 + 1 = 10
```
可以觀察到，進位的部分行為和 AND 電路相同，而低位數的部分和 XOR 相同，因此對於 1 位元的加法，我們可以使用 XOR 電路處理 A + B 的低位部分，使用 AND 電路處理 A + B 進位的部分，電路圖如下
<img src = "https://i.imgur.com/AM78s9Y.png" width = 250>
- S 表示 Sum
- C 表示 Carry
而以上電路又稱作為半加器 (half adder)，功能為將兩個一位元的二進位數進行相加，得到兩個輸出，分別為 Sum 和 Carry。
### 位元運算應用: 避免 overflow
在 Binary Search 的操作中，我們可以看到取得 `mid` 時，可能會出現 `(left + right) / 2` 這樣的操作，但有可能 `(left + right)` 會導致 overflow 的發生，我們可以使用位元運算的手法進行改寫，使用上方加法器的想法進行改寫
對於除以 2 的操作，對應到的 bit-wise 操作為左移 `>>` 操作，而 `left + right`，我們需要處理其 Sum 和 Carry 的部分
- Sum 的部分為 `left ^ right`
- Carry 的部分為 `left & right`
只要將 Carry 左移 1 個單位 (因為進位)，加上 Sum 的部分，我們就可以得到兩數相加的結果
因此，我們能夠進行以下改寫
`(left + right) / 2`
= `(left + right) >> 1`
= `((left ^ right) + ((left & right) << 1)) >> 1`
= `(left & right) + ((left ^ right) >> 1)`
a 先左移 1 再右移 1 結果還是 a
以下為對應的 C 語言實作
```c
#include <stdio.h>
#include <limits.h>
int func(int x, int y)
{
return (x & y) + ((x ^ y) >> 1);
}
int main(void)
{
printf("(4 + 2) / 2 = %d\n", func(4,2));
printf("(3 + 2) / 2 = %d\n", func(3,2));
printf("((INT_MAX) + (INT_MAX)) / 2 = %d\n", func(INT_MAX, INT_MAX));
printf("((INT_MAX) + (INT_MAX)) / 2 = %d\n", ((INT_MAX) + (INT_MAX)) / 2);
}
```
output
```
(4 + 2) / 2 = 3
(3 + 2) / 2 = 2
((INT_MAX) + (INT_MAX)) / 2 = 2147483647
((INT_MAX) + (INT_MAX)) / 2 = -1
```
可以看到使用位元操作的 `(x + y) / 2` 在極端值，`INT_MAX` 時還是有正確的結果
### 位元運算應用: 偵測 NULL Byte
考續以下 C 語言巨集 DETECT
```c
#if LONG_MAX == 2147483647L
#define DETECT(X) \
(((X) - 0x01010101) & ~(X) & 0x80808080)
#else
#if LONG_MAX == 9223372036854775807L
#define DETECT(X) \
(((X) - 0x0101010101010101) & ~(X) & 0x8080808080808080)
#else
#error long int is not a 32bit or 64bit type.
#endif
#endif
```
這是一段巨集程式碼，作用為偵測是否為 NULL byte，在 `strlen()` 中，我們會通過 NULL byte 去判斷ㄧ個字串的長度，考慮以下實作
```c
size_t strlen(const char *s)
{
char *p = s;
while (*p != "\0")
p++;
return (p - s);
}
```
上面這一段程式碼，ㄧ次ㄧ個 byte 的走訪 `p` 所指向的記憶體空間，直到檢查到 NULL byte。
對於ㄧ個 32-bit 的 CPU，我們可以一次處理 4-bytes 大小的資料，我們可以運用ㄧ些手法進行加速
我們看到程式中出現了 `(((X) - 0x01010101) & ~(X) & 0x80808080)`，這是在 32-bit 條件下的 NULL Byte 檢查巨集，我們可以將其縮減成 8-bit 的情況，判斷變成 `(((X) - 0x01) & ~(X) & 0x80)`，並逐步進行分析
```
(((X) - 0x01) & ~(X) & 0x80)
```
令 $p$ 為 `((X) - 0x01)`，$q$ 為 `~(X)`，則
```
((p & q) & 0x80) == ~(~(p & q)) & 0x80
```
由迪摩根定理，${\displaystyle \neg (p\land q)\equiv (\neg p)\lor (\neg q)}$，我們可以得到以下
```
~(~(p) | ~(q)) & 0x80
```
將 $p$ 和 $q$ 代回，得到以下
```
~(~(X - 0x01) | X) & 0x80
```
先看到 `~(X - 0x01) | X`，將 8-bit 組合進行枚舉並代入
```
X = 0000 0000, ~(X - 0x01) | X = 0000 0000
X = 0000 0001, ~(X - 0x01) | X = 1111 1111
X = 0000 0010, ~(X - 0x01) | X = 1111 1110
X = 0000 0011, ~(X - 0x01) | X = 1111 1111
X = 0000 0100, ~(X - 0x01) | X = 1111 1100
X = 0000 0101, ~(X - 0x01) | X = 1111 1111
...
X = 1111 1110, ~(X - 0x01) | X = 1111 1110
X = 1111 1111, ~(X - 0x01) | X = 1111 1111
```
可以看到，`~(X - 0x01) | X` 作用為取出低位的所有 0，並將其他位元設為 1。
如果 `~(~(X - 0x01) | X)`，則意義變成將偶數低位 0 的部分設為 1，其餘部分皆設為 0。
```
X = 0000 0000, ~(~(X - 0x01) | X) = 1111 1111
X = 0000 0001, ~(~(X - 0x01) | X) = 0000 0000
X = 0000 0010, ~(~(X - 0x01) | X) = 0000 0001
X = 0000 0011, ~(~(X - 0x01) | X) = 0000 0000
X = 0000 0100, ~(~(X - 0x01) | X) = 0000 0011
X = 0000 0101, ~(~(X - 0x01) | X) = 0000 0000
...
X = 1111 1110, ~(~(X - 0x01) | X) = 0000 0001
X = 1111 1111, ~(~(X - 0x01) | X) = 0000 0000
```
接著看到 `0x80`，其二進位為 `1000 0000`，也就是針對最高位進行判斷，由上面的枚舉我們可以看到，除了 0 之外，其餘最高位皆為 0，因此和 `0x80` 進行 AND 運算只有當 X = 0 時輸出為 `0x80`。
而我們將這個情況拓展到 32 位元的情況
- 如果 32-bit 全部都是 0，那麼會輸出 `0x80808080`
- 如果 32-bit 只有最低 8 位為 0，其餘都是 1，輸出為 `0x80`
- 如果 32-bit 最高位 8 位和最低位 8 位皆為 0，其餘皆為 1，輸出為 `0x80000080`，由 `0x80` 的位置可以判斷出最高位的 byte 和最低位的 byte 皆為 0，由這個輸出我們可以判斷出 NULL Byte 所在的位置
使用以上方法對 `strlen()` 進行實作，可以一次判斷 4 個 bytes，有機會加速原先使用 `char` 一個一個 byte 比較的實作。
==TODO 實驗驗證==
### 位元運算應用: 一個數字的二進位表示法中存在多少個一
```c
int count_bits(int x)
{
x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);
x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);
x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);
x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);
x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);
return x;
}
```
## C 語言邏輯運算
在布林運算中，我們看到了 AND, OR, NOT, Exclusive-OR 等操作，以 C 語言中運算子表示為 `&`, `|`, `~`, `^`，而如果是邏輯上的操作，如邏輯上的 AND, OR, NOT，則為 `&&`, `||`, `!`，運算完如果非零，則為 TRUE，如果為零，即為 FALSE，也就是在任意的邏輯運算底下，產生的輸出只有兩種，TRUE 以及 FALSE，這是和位元運算不同之處。
第二個則是如果第一個參數就能夠確定一個表達式的結果，那麼邏輯運算符號不會對第二個值求值，以下說明
假設是 AND 邏輯運算，如果 0 && x，由於 AND 必須兩個參數皆為真，也就是非零才即為真，而我們第一個參數為 0，已經確定這個表達式為假了，因此不會對第二個參數求值。
- 對於 `a && 5/a`，如果 a 為 0，則確定這個運算式的結果為假，因此不會對 `5/a` 求值，也就不會產生出除以 0 的情況。
- 對於 `p && *p++`，p 為一個指標變數，如果 p 為 NULL，NULL 為 0，則確定這個運算式的結果為假，因此不會發生反參考空指標的情況
## C 語言位移運算
前面看到了 C 語言中存在邏輯的 AND, OR, NOT 運算，以及位元運算，AND, OR, NOT, Excusive-OR，在 C 語言的位元運算中，還存在右移運算以及左移運算。
### 位移運算: 左移運算
對於一個位所構成的向量，$[x_{w-1}, x_{w-2}, ..., x_0]$，如果經過 `x << k` x 向左位移 k 單位，則表示為 $[x_{w-k-1}, x_{w-k-2}, x_0, 0, 0, 0]$，`x` 向左移 `k` 位，丟棄最高的 `k` 位，並在右邊補上 `k` 個 0。移位運算具有結合律，如 `x << j << k == (x << j) << k`。
### 位移運算: 右移運算
在右移運算中，我們會看到兩種行為，一種為邏輯的右移運算，另外一種為算術的右移運算
- 邏輯右移運算: 對於一個位所構成的向量，$[x_{w-1}, x_{w-2}, ..., x_0]$，如果經過 `x >> k` x 向右位移 k 單位，結果為 $[0,0,0...,x_{w-1}, x_{w-2}, ..., x_k]$。
- 算術右移運算: 對於一個位所構成的向量，$[x_{w-1}, x_{w-2}, ..., x_0]$，如果經過 `x >> k` x 向右位移 k 單位，結果為 $[x_{w-1},x_{w-1},x_{w-1}...,x_{w-1}, x_{w-2}, ..., x_k]$，也就是在左端補上了 `k` 個最高有效位元的值。
下面舉例說明，假設給定數值 `0110,0011`，則經過位移運算後結果如下表所展示
<img src="https://i.imgur.com/yrUkKUk.png" width=300>
這裡可以看到，我們右移的結果為邏輯右移運算，而至於右移操作為邏輯運算還是算術運算，取決於實作定義，在許多編譯器中，對於有號數的右移操作，使用算術右移，如以下展示，給定 `int8_t = 149`，二進位表示法為 `1001,0101`，最高有效位為 1，因此，預期算術右移的結果為 `1100,1010`
```c
#include <stdio.h>
#include <stdint.h>
#define BYTE_TO_BINARY_PATTERN "%c%c%c%c%c%c%c%c"
#define BYTE_TO_BINARY(byte) \
(byte & 0x80 ? '1' : '0'), \
(byte & 0x40 ? '1' : '0'), \
(byte & 0x20 ? '1' : '0'), \
(byte & 0x10 ? '1' : '0'), \
(byte & 0x08 ? '1' : '0'), \
(byte & 0x04 ? '1' : '0'), \
(byte & 0x02 ? '1' : '0'), \
(byte & 0x01 ? '1' : '0')
int main(void)
{
int8_t a = 149;
uint8_t b = 149;
printf(BYTE_TO_BINARY_PATTERN "\n", BYTE_TO_BINARY(a));
printf(BYTE_TO_BINARY_PATTERN "\n", BYTE_TO_BINARY(a >> 1));
printf(BYTE_TO_BINARY_PATTERN "\n", BYTE_TO_BINARY(b >> 1));
}
```
output
```
10010101
11001010
01001010
```
可以看到對於有號數以及無號數進行右移操作的差異。
### 位移操作超出該資料型別的位元數
假設我們有一個 32 位元的數，如果我們要執行位移的位元數超過 32 位，會出現什麼樣的行為? 考慮以下情況
```c
int main(void)
{
int32_t a = 0xFEDCBA98;
uint32_t b = 0xFEDCBA98u;
printf("%08X\n", a << 32);
printf("%08X\n", a >> 36);
printf("%08X\n", b >> 40);
}
```
output
```
FEDCBA98
FFEDCBA9
00FEDCBA
```
對於這種情況，可以看到假設對於一個 `w` 位元的資料，如果我們要進行位移操作 `k` 位元，則結果為 `w` 位元的資料位移了 `k mod w` 位元的值，但是這一件事情是根據實作定義的，在 C 語言中並沒有保證這一件事情發生，因此，在進行位移操作時，盡可能保證 `w > k`。
## 整數的表示
在這裡會看到兩種整數的表示法，一種只能表示正數，另外一種可以表示負數，零，以及正數。下面看到一些常用於數值編碼以及數值操作的術語
### 整數資料型別
C 語言中支援許多整數的資料型別，用來表示有限範圍的整數，包含關鍵字 `char`, `short`, `long`，我們還能夠指定這一些數字是整數或是非整數，使用關鍵字 `unsigned`, `signed` 進行修飾，而這一些關鍵字能夠表示的整數範圍又會因為程式被如何進行編譯而有所不同，如 32 位元和 64 位元在 `long` 型別表示的範圍不同，而為了避免硬體架構造成關鍵字對應到的整數範圍不同，因此定義了如 `int32_t` 等等資料型別，以下為 32 位元的程式中， C 語言中常見的資料型別
可以發現到負數範圍和正數的範圍是不對稱的，我們將無號數最大值使用 `UMax` 進行表示，有號數最小值使用 `TMin` 進行表示，有號數最大值使用 `TMax` 進行表示，則我們可以得到下表
從上面我們可以發現到，$|TMin| = |TMax| + 1$，正數的表示範圍和負數的表示範圍是不同的，相差了 1，原因在於對於有號數，最左邊的位元 1 表示負數，0 表示正數，而 `0000,0000` 為非負數，因此正數的表示範圍比負數的表示範圍少了 1。還能夠發現到，$|UMax| = 2*TMax + 1$。
在 C 語言標準中沒有要求使用補數表示有號數，但實作上幾乎都是使用補數系統表示有號數，而對於不同型別取值的上限，在 `limits.h` 中定義了諸如 `INT_MAX`, `INT_MIN` 和 `UINT_MAX`。
前面我們提及到為了程式的移植考量，在 C99 中定義了 `int32_t` 等型別，如果我們要將其數值通過 printf 印出，我們同樣也需要藉由巨集的幫助，需要引入 `#include <inttypes.h>`，以印出一個 `int32_t` 為例子，程式片段如下
```c
int main(void)
{
int32_t a = 1;
printf("a = %" PRId32 "", a);
}
```
`PRId32` 巨集展開為字串 `"d"`，因此上面的 printf 展開後，變成以下
```c
printf("a = %d", a);
```
這裡可以看到，使用巨集可以保證程式的可移植性。
### 補數系統
對於有號數的表示，存在二的補數表示法，一的補數表示法，最高位做為正負的表示法。
#### 二的補數 (Two's complement)
定義 $B2T$ 如下
$B2T(x) = -x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i$
#### 一的補數 (Ones' complement)
定義 $B2O$ 如下
$B2O_w(x) = -x_{w-1}(2^{w-1}-1)+\sum_{i=0}^{w-2}x_i2^i$
#### 最高位正負表示法
定義 $B2S$ 如下
$B2S_w(x) = (-1)^x_{w-1}*(\sum_{i=0}^{w-2}x_i2^i)$
注意: 二的補數和一的補數在英文中，`'` 的位置是不同的。
下表為二的補數，一的補數，最高位正負表示法的比較
可以看到對於一的補數，最高位正負表示法中，0 皆有兩種表示法，這可能會造成歧異且增加電路設計的複雜度，對於大多數電腦系統，目前有號數表示使用二的補數做為表示
下面我們看到一個關於補數的程式碼
```c
#include <stdio.h>
#include <stdint.h>
#include <limits.h>
#include <inttypes.h>
#define BYTE_TO_BINARY_PATTERN "%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c"
#define BYTE_TO_BINARY(byte) \
(byte & 0x8000 ? '1' : '0'), \
(byte & 0x4000 ? '1' : '0'), \
(byte & 0x2000 ? '1' : '0'), \
(byte & 0x1000 ? '1' : '0'), \
(byte & 0x800 ? '1' : '0'), \
(byte & 0x400 ? '1' : '0'), \
(byte & 0x200 ? '1' : '0'), \
(byte & 0x100 ? '1' : '0'), \
(byte & 0x80 ? '1' : '0'), \
(byte & 0x40 ? '1' : '0'), \
(byte & 0x20 ? '1' : '0'), \
(byte & 0x10 ? '1' : '0'), \
(byte & 0x08 ? '1' : '0'), \
(byte & 0x04 ? '1' : '0'), \
(byte & 0x02 ? '1' : '0'), \
(byte & 0x01 ? '1' : '0')
int main(void)
{
int16_t x = 12345;
int16_t mx = -x;
uint16_t ux = -x;
printf("x = " BYTE_TO_BINARY_PATTERN "\n", BYTE_TO_BINARY(x));
printf("mx = " BYTE_TO_BINARY_PATTERN "\n", BYTE_TO_BINARY(mx));
printf("ux = %" PRId16, ux);
}
```
output
```
x = 0011000000111001
mx = 1100111111000111
ux = 53191
```
首先可以看到，有號數的表示為二的補數表示法，接著看到一個負數對於一個無號數而言，最高有效位元不會被視為正負符號，而是單純的數字，因此 `1100,1111,1100,0111` 對應到的十進位數值即為 53191。
## C 語言有號數與無號數
### Ex1
延伸上面例子，考慮到有號數與無號數之間的轉換
```c
int main(void)
{
int16_t v = -12345;
uint16_t mv = v;
printf("v = %d\nmv = %d", v, mv);
}
```
output
```
v = -12345
mv = 53191
```
可以看到這個結果如我們預期，改變型別，並沒有改變數字背後的二進位位元的組合，而是改變了我們對於位元的解釋方式，對於有號數，最高有效位元為符號位，對於無號數，最高有效位僅僅是單純的數字。
以下情況同理
### Ex2
```c
int main(void)
{
uint32_t v = 4294967295u;
int32_t mv = (int32_t) v;
printf("v = %" PRIu32 "\nmv = %" PRId32, v, mv);
}
```
output
```
v = 4294967295
mv = -1
```
下面看到的是 C 對於無號數與有號數處理方式的不同，當我們執行運算時，運算子作用於兩個型別不同的操作數時可能會發生隱式轉型，以下範例
### Ex3
```c
int main(void)
{
printf("%d\n", -1 < 0u);
}
```
output
```
0
```
可以看到輸出結果為假，原因為有號數和無號數進行運算時，有號數會被轉型成無號數，而對於無號數來說，-1 的二進位組合相當於 4294967295，而 4294967295 < 0 為假，因此輸出為假。
### Ex4
如果我們將小的型別轉型成比較大的型別表示法，會需要注意一些狀況
以下舉例
```c
#include <stdio.h>
#include <inttypes.h>
int main(void) {
int8_t a = -125;
int16_t a16 = a;
uint16_t au16 = a;
printf("%"PRId8 " " "%"PRId16 " " "%"PRIu16 "\n", a, a16, au16);
int8_t b = 124;
int16_t b16 = b;
uint16_t bu16 = b;
printf("%"PRId8 " " "%"PRId16 " " "%"PRIu16 "\n", b, b16, bu16);
return 0;
}
```
output
```
-125 -125 65411
124 124 124
```
`-125` 的二進位表示法為 `1000 0011`，而如果我們將這個二進位表示法放到更大的資料型別中，我們可以看到會以最高位進行擴展，`1000 0011` 會變成 `1111 1111 1000 0011`，結果也是 `-125`，而這個二進位表示法如果以無號數進行解讀，則為 `65411`
`124` 的二進位表示法為 `0111 1100`，如果我們將這個二進位表示法放到更大的資料型別中，我們同樣可以看到會以最高位進行擴展的現象，`0111 1100` 會變成 `0000 0000 0111 1100`，結果同樣也是 `124`，對於無號數表示法也是如此。
如果我們使用的最高位為 0 進行擴展，我們又稱之為 Zero extension，反之則 Sign extension。
### 關於 TMin
在前面我們提及 `limits.h` 這個函式庫，我們看到其中 `INT_MIN` 和 `INT_MAX`
```c
#define INT_MIN (-2147483647 - 1) // minimum (signed) int value
#define INT_MAX 2147483647 // maximum (signed) int value
```
這裡思考，為什麼不將 `INT_MIN` 表示成 -2147483648，而是採用上述寫法?
假設我們將 `INT_MIN` 表示成 -2147483648，並將該程式碼編譯成 32 位元的程式碼，如果編譯器遇到了一個數字如 `-X` 這種形式，首先會先確定 `X` 的資料型別和其數值，接著使用一元運算子 `-` 對 `X` 取負數。至於編譯器是如何決定 `X` 的資料型別，我們可以參考下表
假設我們指定 C90 版本，則對於 2147483648 這個十進位數，編譯器會開始尋找一個合適的資料型別，首先看到 `int`，發現 `int` 無法表示，接著來到 `long` 發現也無法，接著來到 unsigned，發現能夠表示，因此，在 C90 底下，2147483648 這個常數整數的型別為 `unsigned`。
如果我們嘗試將 2147483648 轉換成十六進位制，表示成 `0x8000,0000`，則我們知道，在 C90 底下，會被表示成 `unsigned`，如果我們將這個程式編譯成 C99 版本，則會發現到，2147483648 這個整數常數型別為 `long long`，根據這一些情況，我們列出下表
在 32 位元底下，2147483648 和 -2147483648 的二進位表示法相同，其常數為 `unsigned`，值為 2147483648。當我們切換到 C99 版本，則常數為 `long long`，值為 -2147483648。所有情況如上表所展現。
```c
int main(void)
{
int dcomp = (-2147483648 < 0);
int hcomp = (0x80000000 < 0);
printf("%d\n%d", dcomp, hcomp);
}
```
以上程式碼在 C90 底下，32 位元和 64 位元結果並不相同，-2147483648 在 32 位元底下為 unsigned，值為 2147483648，而 2147483648 < 0 為假，因此 dcomp 為 0。
對於 64 位元，-214748364 為 long，值為 -214748364，而 -2147483648 < 0 為真，因此 dcomp 為 1。
```c
int main(void)
{
int dtmin = -2147483648;
int dcomp2 = (dtmin < 0);
int htmin = 0x80000000;
int hcomp2 = (htmin < 0);
printf("%d\n%d", dcomp2, hcomp2);
}
```
以下程式碼，可以看到在 C90 底下，32 位元和 64 位元的結果相同。
-2147483648 這個值被賦值給 dtmin，實際上是將 -2147483648 的二的補數賦值給 dtmin，也就是一串二進位數值，並將該二進位數值以 int 進行解釋，而對於 htmin 也是如此，而 -2147483648 與 0x80000000 的二進位數值經過 int 的解釋皆為 −2147483648，因此這邊產生的結果不會因為平台而造成差異。
所以這邊可以發現到，會發生問題主要是因為在不同平台上，整數常數有不同的型別，因此造成了不同平台上的執行差異。
如果我們將 `TMin` 表示成 -2147483647 - 1，2147483647 可以被表示成 int，1 也能夠被表示成 int，這裡就避免了因為語言標準不同造成不同解釋的差異 (考慮 32 位元情況)。
```
int TMin = -2147483647 - 1
^ ^
int int
int TMin = -2147483648
^
unsigned
```
在無號數與有號數使用上常常因為隱式轉型造成不同的結果，考量到以下程式碼
### Ex1.
```c
float sum_elements(float a[], unsigned length)
{
int i;
float result = 0;
for(i = 0; i <= length - 1; i++)
result += a[i];
return result;
}
```
如果 length 為 0，則會發生記憶體錯誤，預期行為應該是直接回傳 0，但是這並沒有發生，原因為傳入的 length 為 unsigned，而 length -1 中 -1 會轉型成 unsigned，值會變為 4294967295，如果 length 為 0，則 length - 1 結果為 0 + 4294967295 = 4294967295，可以想像會存取到超出陣列邊界範圍的元素，因此發生了記憶體存取錯誤。
接著看到以下程式碼 [source](https://hackmd.io/@sysprog/c-bitwise)
```c
int n = 10;
for (int i = n - 1 ; i - sizeof(char) >= 0; i--)
printf("i: 0x%x\n",i);
```
這一段程式碼同樣存在有號數轉換到無號數的問題，`sizeof()` 運算子得到的值型別為 `unsigned`，當 `i - sizeof(char)` 產生負數時，如 -1，-1 型別為 unsigned，值為 4294967295，接著便會不斷的重複這個過程，進而產生無限迴圈。
可以看到上面的問題都是來源於有號數與無號數之間的運算所產生的隱式轉型問題，事實上除了 C 語言以外，很少語言支援無號數，其中一種解決方法為不使用無號數。
無號數使用的場合為當我們僅將數字當作二進位組合時，沒有數字意義，如 flag，記憶體地址等等。
## C 語言整數運算
在整數運算中，我們需要注意到溢位問題 (overflow)，以及表達式中操作數的順序問題，如 `x < y` 和 `x - y < 0` 會產生出不同的結果。
### 無號數加法
對於兩個正整數 $x$ 和 $y$，滿足 $0 <= x, y < 2^w$，如果我們要計算 $x + y$ 的值，則範圍會在 $0<=x+y<=2^{w+1}-2$，也就是要表示和我們需要 $w + 1$ 個位，以下舉例，考慮 $w = 8$，也就是 8 位元的情況下，$x = 255$, $y = 255$
$x = 255 = 1111, 1111$
$y = 255 = 1111, 1111$
$x + y = 1, 1111, 1110$
以上情況可以看到，在 $x$ 和 $y$ 為 8 位元無號數的最大值時，兩樹相加我們會需要 $w + 1$，也就是 9 個位進行表示。
延續上面的案例，假設我們將 $x + y$ 的結果存放到一個無號數 $z$ 中，也就是 `unsigned z`，則可發現到 $x + y$ 的結果太大以至於無法放入到 $z$ 中，我們可以檢視會發生怎樣的行為
```c
int main(void)
{
uint8_t a = 255u;
uint8_t b = 255u;
uint8_t c = a + b;
printf("c = %u", c);
}
```
output
```
254
```
我們發現到，正常 $a + b = 510$，二進位表示為 $1, 1111, 1110$，可以發現到超出的位被捨去了，也就只剩下了 $1111, 1110$，十進位為 254，因此，溢位其實就是 $c\ mod\ 2^8$。
在 C 語言中，不會將溢位做為錯誤並且發出警告，但是我們希望能夠有一些方法判斷是否有溢位的發生。
對於無號數加法 $x,y$，滿足 $0 <= x,y<=UMax_w$，定義 $+^u_w$ 為在 $w$ 位元下的無號數加法，定義 $s = x +^u_w y$，若且唯若 $s < x$ (和 $s < y$ 等價) 時，產生了溢位。
假設 $x = 9, y = 12$，$w = 4$，$s = 9 +^u_4 12 =5$，可以看到由於 $s < x$，也就是 $5 < 9$，因此發生了溢位。
證明:
這邊使用反證法，假設沒有發生溢位，則 $s >= x$，如果發生溢位，則 $s < x$，當 $s$ 發生溢位時，則 $s = x + y - 2^w$，令 $y < 2^w$，則 $y - 2^w <0$，則 $s = x + (y - 2^w) < x + (0)$，也就是 $s < x$。
溢位檢測可以使用上方的推導進行實作
```c
int uadd_ok(unsigned x, unsigned y)
{
unsigned sum = x + y;
return sum >= x;
}
```
### 補數的加法
上面介紹完無號數的加法，接著我們看到有號數的加法，也就是補數的加法，對於有號數，其加法可能會有兩種溢位的情況發生，一種是數字正太大，另外一種是數字負太大。
回憶先前看到的，對於 8 位元的有號數，值 x 的範圍在 $-128 <= x <= 127$ 之間，對於 w 位元有號數 x，值的範圍在 $-2^{w-1} <= x <= 2^{w-1} - 1$，有 w 位元的兩有號數 x 和 y，其相加的結果會在範圍 $-2^w <= x + y <= 2^w -2$ 之中。
這裡同樣會碰到先前的情況，也就是對於兩個 w 位元的數字相加，我們會需要 w + 1 位元進行表示，這邊定義 $+^t_w$ 為有號數在 w 位元底下的相加結果，也就是如果遇到溢出的情況，如同無號數加法中，將溢出的位元捨去。
對於 x 和 y，補數加法有以下三種情況
$\displaystyle x+^t_w=\begin{cases}
x+y-2^w,\ 2^{w-1} <= x + y\\
x+y,\ -2^{w-1}<=x+y<2^{w-1}\\
x+y+2^w,\ x+y<-2^{w-1}
\end{cases}$
假設 x 和 y 都是 8 位元有號數，則上面補數加法的所有情況，可以使用以下程式碼片段進行驗證
```c
int main(void)
{
printf("(-120) + (-15) = %" PRId8 "\n", (int8_t)((-120) + (-15)));
printf("(-120) + (-50) = %" PRId8 "\n", (int8_t)((-120) + (-50)));
printf("120 + 15 = %" PRId8 "\n", (int8_t)((120) + (15)));
printf("120 + 30 = %" PRId8 "\n", (int8_t)((120) + (30)));
}
```
output
```
(-120) + (-15) = 121
(-120) + (-50) = 86
120 + 15 = -121
120 + 30 = -106
```
- (-120) + (-15)，可以看到發生了負數溢位問題，負數的最大表示值為 -128，而這裡計算的結果為 -135，對於負數溢位，結果為 $x+y+2^w$，也就是 -135 + 256，結果為 121，符合預期。
- (-120) + (-50)，可以看到發生了負數溢位問題，負數的最大表示值為 -128，而這裡計算的結果為 -170，對於負數溢位，結果為 $x+y+2^w$，也就是 -170 + 256，結果為 86，符合預期。
- 120 + 15，可以看到發生了正數溢位問題，正數的最大表示值為 127，這裡結果為 135，對於正數溢位，結果為 $x+y-2^w$，也就是 135 - 256，結果為 -121，符合預期。
- 120 + 30，可以看到發生了正數溢位問題，正數的最大表示值為 127，這裡結果為 150，對於正數溢位，結果為 $x+y-2^w$，也就是 150 - 256，結果為 -106，符合預期。
我們希望能夠偵測出有號數的溢位情況，對於 w 位元的有號數，滿足 $TMin_w <= x,y <= TMax_w$ 的 x 和 y，令 $+^w_t$ 為在 w 位元底下的有號數相加符號，設 s 為 x 和 y 有號數相加的結果，也就是 $s = x\ +^w_t\ y$，若且唯若 $x >0$, $y >0$ 且 $s<=0$ 時，發生了正數的溢位，若且唯若 $x <0$, $y <0$ 且 $s>=0$ 時，發生了負數的溢位。
我們可以根據上面的推論，實作以下判斷有號數溢位
```c
int tadd_ok(int x, int y)
{
int sum = x + y;
int neg_over = x < 0 && y < 0 && sum >= 0;
int pos_over = x >= 0 && y >=0 && sum < 0;
return !neg_over && !pos_over;
}
```
以下針對補數減法的實作是有問題的
```c
int tadd_ok(int8_t x, int8_t y)
{
int8_t sum = x + y;
int neg_over = x < 0 && y < 0 && sum >= 0;
int pos_over = x >= 0 && y >=0 && sum < 0;
if(neg_over) printf("neg_over\n");
if(pos_over) printf("pos_over\n");
return !neg_over && !pos_over;
}
int tsub_ok(int8_t x, int8_t y)
{
return tadd_ok(x, -y);
}
```
我們可以試試傳入邊界值，也就是 `TMax` 或是 `TMin`，我們發現當 `y = TMin` 會有問題，`-(TMin)` 相當於 `128`，而 `128` 在 `8` 位元有號數已經溢位，因此其值為 `128 - 256 = -128`，當 `x` 為一負數時，相加結果會產生負溢位的結果，如果 `x` 為一正數，則不會發生溢位，但實際上結果應該相反，假設 `x = 1, y = -128`，`1 - 128 = -127`，沒有溢位發生，而 `x = -1, y = -128`，`-1 - 128 = -128`，則溢位發生，可以看到這個實作方式在 `y = TMin` 時候結果會相反。
### 無號數乘法
對於兩個正整數 $x$ 和 $y$，滿足 $0 <= x, y <= 2^w-1$，如果我們要計算 $x * y$ 的值，則範圍會在 $0<=x+y<=(2^{w+1}-1)^2$，將 $(2^{w+1}-1)^2$ 展開後，得到 $2^{2w}-2^{w+1}+1$，也就是要表示和我們需要 $2w$ 個位，但是在 C 語言中，我們使用 $w$ 為表示 $x$ 和 $y$ 相乘的結果，則會取最低的 $w$ 位做為結果。
定義兩個 w 位元的無號數乘法計算為 $*^u_w$，則
$x *^u_w y = (x * y)\mod 2^w$
<!-- $\mathrm{Formula}$ -->
### 補數乘法
對於兩個有號數 $x$ 和 $y$，滿足 $-2^{w-1} <= x, y <= 2^{w-1}-1$，如果我們要計算 $x * y$ 的值，則範圍會在 $(-2^{w-1})^2 <= x * y <= (2^{w-1}-1)^2$ 之間，如果要使用補數表示，我們會需要 $2w$ 位才能夠表示，但在 $w$ 位的有號數乘法中，會取 $w$ 位剩餘的捨棄，定義 $w$ 位的有號數乘法為 $*^t_w$。對於有號數乘法，會先將結果取 $w$ 位，接著以補數表示，如下面所展示
$x *^t_w y = \mathrm{U2T_w}((x * y) \mod 2^w)$
以下為無號數乘法和補數乘法的結果比較
對於 3 位的有號數或無號數乘法，結果皆為取 3 位，剩餘的位捨去，而有號數與無號數差別，在於最後產生的 3 位結果是如何進行解讀，如果是無號數，則以無號數方式解讀，反之則以有號數方式解讀。
上面可以看到對於補數乘法的溢位，我們使用了捨去多餘的位進行處理，下面是針對於補數乘法溢位的偵測
```c
int tmult_ok(int x, int y)
{
int p = x * y;
return !x || p / x == y;
}
```
對於上面的實現方法，我們可以嘗試證明，假設 $x$ 和 $y$ 皆為 $w$ 位的有號數，則 $x * y$ 的結果需要 $2w$ 位才能夠表示 (在上方有說明)，我們使用 $u$ 表示低 $w$ 位，$v$ 表示高 $w$ 位，我們可以將 $x * y$ 改寫成 $x * y = v*2^w + u$。
$u$ 表示低 $w$ 位，設 $p_{w-1}$ 為 $p$ 的最高有效位，則對於 $u$ 這個 $w$ 位的補數，可以改寫成 $u = p + p_{w-1}*2^w$，而 $x * y$ 可以表示為 $x * y = v*2^w + p + p_{w-1}*2^w$，將 $2^w$ 提出後得到 $x * y = 2^w(v + p_{w-1}) + p$，設 $\alpha = v + p_{w-1}$，當 $\alpha = 0$，則 $x * y = p$，沒有發生溢位，當 $\alpha \neq 0$，則 $x * y \neq p$，發生溢位 (從 $\alpha = v+p_{w-1}$ 中還知道 $\alpha >= 0$)。
根據除法原理，我們可以將 $p$ 表示成 $p = x * q + r$，也就是一個非零的 $x$ 和 $p$ 相除得到商為 $q$，餘數為 $r$，且 $|r| < |x|$
如果 $q = y$，則 $p = x * y + r$，而 $x * y = 2^w(\alpha) + p$，因此 $p = 2^w(\alpha) + p + r$，化簡後，$2^w(\alpha) + r = 0$。
等式成立的條件有兩個
1. $\alpha$ 和 $r$ 皆為 0
2. $2^w(\alpha) = -r$，我們在除法原理中得到 $|r| < |x|$，且根據我們最開始假設，$x$ 為 $w$ 位有號數，$x$ 最大值為 $2^w$，由 $|r| < |x|$ 得到 $|r| < 2^w$，可以知道等式 $2^w(\alpha) = -r$ 必不成立 ($\alpha >= 0$)，因此等式成立的條件只有 1.
如果 $\alpha = 0$，則 $p = x * y$，$p/x = y$，到這裡便證明完畢了。
我們可以將上面程式碼改成使用 `int64_t` 紀錄結果，可以簡化程式碼如下
```c
int tmult_ok(int x, int y)
{
int64_t res = (int64_t)x * y;
return res == (int) res;
}
```
可以注意到，`(int64_t)x * y`，這邊的強制轉型是為了實現 `int64_t * int64_t` 的結果，如果沒有加上，會變成 `int32_t * int32_t`，可能會發生溢位後，再將運算的結果存入到 `int64_t` 中。
下面為一個兩有號數進行乘法造成溢位的案例
#### Ex1
```c=
void* copy_elements(void *ele_src[], int ele_cnt, size_t ele_size)
{
void *result = malloc(ele_cnt * ele_size);
if(result == NULL)
return NULL;
void *next = result;
int i;
for(i = 0; i < ele_cnt; i++)
{
memcpy(next, ele_src[i], ele_size);
next += ele_size;
}
return result;
}
```
可以看到 `copy_elements` 這個函式為傳入一陣列，接著他會複製到 `result` 記憶體空間中，並且回傳其結果 (假設這是 32 位元的環境)。
有問題的地方在於第 3 行，分配了 `ele_cnt * ele_size` 大小的記憶體空間，如果 `ele_cnt` 為 $2^{20} + 1$，`ele_size` 為 $2^{12}$，則 $\mathrm{ele\_cnt} * \mathrm{ele\_size} = 2^{32} + 2^{12}$，這個數字以 `int` 進行表達，結果為 $4096$，`result` 指向的記憶體空間為 $4096\ \mathrm{bytes}$，接著 `for` 迴圈開始走訪，`ele_cnt` 為 $2^{20} + 1$，因此會超出 `result` 指向的記憶體空間，將其他記憶體空間的資料覆蓋。
上面的問題是 `ele_cnt * ele_size` 使用 `int` 表示時造成溢位，如果我們使用 `uint64_t`，如下
```c
uint64_t size = ele_cnt * (uint64_t) ele_size;
void *result = malloc(size);
```
似乎就不會有溢位問題，但是，`malloc` 的參數為 32 位元的無號數，也就是無法分配大於 $2^{32}$ 的記憶體空間，因此，如果分配的記憶體大於 $2^{32}$，我們需要捨棄
```c
uint64_t required_size = ele_cnt * (uint64_t) ele_size;
size_t request_size = (size_t) required_size;
if(required_size != request_size)
//Overflow must have occurred. Abort operation
return NULL;
...
```
### 關於常數，2 的冪次數乘法
對於乘法的運算，大約需要 3 ~ 6 個 clock cycle，而對於加法，減法，位移運算，可以使用更少，大約 1 個 clock cycle 完成。因此在編譯器優化中，常常會使用加減位移運算代替乘法運算，首先，先看到常數為 2 的冪次數的狀況
對於常數為 2 的冪次數乘法，可以使用左移運算進行表示，如果 $x$ 要乘上常數為 $2^k$，則等同於 $x \ll k$。對於溢位的情況也會是同樣的結果，以下範例
```c
int main(void)
{
int8_t x = 11;
int8_t y = 16;
int8_t res1 = 11 * 16;
int8_t res2 = 11 << 4;
printf("res1 = %d, res2 = %d", res1, res2);
}
```
output
```
res1 = -80, res2 = -80
```
位移之後，取低位 $w$ 位結果相同。
假設在程式碼中存在 $x * 14$，$14$ 可以表示成 $14 = 2^1 + 2^2 + 2^3$，因此編譯器會優化成 $(x \ll 3)+(x \ll 2)+(x \ll 1)$，或是更進一步，$(x \ll 4)-(x \ll 1)$。
如果將上面針對於常數的乘法操作一般化後，我們可以得到兩種形式
- 1. $(x \ll n)+(x \ll (n-1))+...+(x \ll m)$
- 2. $(x \ll (n + 1))-(x \ll m)$
如果 $n$ 為最高有效位，也就是 $n = w-1$，則 $(x \ll (w)) - (x \ll m)$，$(x \ll (w))$ 結果為 0，因此可以簡化成 $-(x \ll m)$
上面看到常數的乘法有兩種形式，分別為 1. 和 2.，以下將說明何種形式較佳
假設加法和減法的 clock cycle 相同，則
- 當 $n = m,\ m > 0$，對於 1. 只需要移位一次，2. 則需要移位兩次和一次減法
- 當 $n = m + 1,\ m > 0$，無論 1. 還是 2.，都需要兩次移位，一次加法或減法
- 當 $n > m + 1,\ m > 0$，2. 需要兩次位移，一次減法，而 1. 需要 $n - m + 1$ 個移位和 $n - m$ 次加法
- 當 $m = 0$，1. 和 2. 都至少需要一次位移
### 關於常數，2 的冪次數除法
對於除法操作，會需要大約 30 個 clock cycle，而如果常數為 2 的冪次數，則可以使用右移運算子完成該操作。
對於整數的除法，在 C 語言中為向下取整數，如 $3.1$ 變成 $\lfloor 3.1 \rfloor = 3$，$\lfloor -3.1 \rfloor = -4$，回憶先前針對於移位運算的說明，對於無號數的右移操作，為邏輯位移操作，因此只需要捨去右邊 $k$ 位，左邊補上 $k$ 個 0 便完成。
對於有號數，先前提及有號數的位移操作為算術位移操作，算術右移 $k$ 位，則左邊需要補上 $k$ 個最高有效位的數字，這裡可以看到對於有號數使用算術位移的原因其中之一是確保負數經過右移操作之後仍然為負數。
對於正數來說，最高有效位為 0，因此算術位移的右移和邏輯右移有一樣的效果。
對於負數來說，最高有效位為 1，經過算術右移 $k$ 位需要在左方補上 $k$ 個 1，這個操作可以確保負數經過右移之後仍然為負數。
```c
int main(void)
{
uint16_t a = 12340;
int16_t b = 12340;
int16_t c = -12340;
printf("a >> 4 = %d\n", a >> 4);
printf("b >> 4 = %d\n", b >> 4);
printf("c >> 4 = %d\n", c >> 4);
}
```
output
```
a >> 4 = 771
b >> 4 = 771
c >> 4 = -772
```
可以看到對於負數的位移操作，由於為向下取整，因此會出現進位的現象，而為了避免這個現象發生，下面先說明整個向下取整的過程
令 $x$ 為一 $w$ 位補數，表示成 $[x_{w-1},x_{w-2}...,x_0]$，設 $x'$ 為 $w-k$ 位，表示成 $[x_{w-1},...,x_{w-1},x_{w-2}...,x_k]$，設 $x''$ 為 $k$ 位無號數，表示成 $[x_{k-1},x_{k-2}...,x_0]$。
我們可以將 $x$ 表示成 $x = 2^k*x'+x''$，而 $0 \leq x'' < 2^k$，如果我們右移了 $k$ 位，得到的值為 $2^k*x'$，也就是相當於捨去 $x''$，右移後的值也可以表示成 $x'=\lfloor x/2^k \rfloor$。
接著我們看到負數進位的現象
```
-12340 | 1100 1111 1100 1100 | >> 0
-6170 | 1110 0111 1110 0110 | >> 1
-772 | 1111 1100 1111 1100 | >> 4 (-12340 / 2^4 = -771.25)
```
關於 $-12340 \gg 4$，我們知道右移的操作捨去的是無號數的部分，對應到的部分為 `1100`，如果是有號小數，其值為 `-0.5 + 0.25 = -0.25`。而對於負數進位，我們可以在進行移位操作之前，加上一個偏置 (biasing) 進行修正。
如果我們希望結果為 `-771`，最後 4 位二進位為 `1101`，而 `-772` 最後 4 位二進位為 `1100`，我們要進行的操作為讓最後 4 位的最高有效位進行進位，接著再進行右移操作，便可以讓 `1100` 變成 `1101`。
拓展到 $k$ 位的情況，便是我們觀察捨去的 $k$ 位，如果最高有效位為 1，則進行進位，否則捨去，`-12340` 二進位最後 4 位為 `1100`，如果我們將其變成 `1 xxxx`，接著向右移位 4 位，便可以得到最後右移完成後，最後 4 位為 `1101`。
假設最後 4 位為 `0000`，我們加上 $2^{4} - 1$，則會得到 `1111`，如果最後 4 位為 `0001`，加上了 $2^{4} -1$，則會得到 `1 0000`，成功完成進位，因此，只要將最後 $k$ 位加上 $2^{k} - 1$ 後，便可以得到最後 $k$ 位進位到 $k + 1$的結果，而如果最後 4 位皆為 0，會因為右移捨去而不受影響，舉例，`-12340 >> 2`，可以看到 `-12340` 二進位末兩位為 `00`，我們加上 $2^2-1$，得到 `11`，並不會進位，接著進行右移兩位，`11` 便會被捨棄。
因此，對於無條件捨去的負數右移，需要寫成如下
```c
(x + (1 << k) - 1) >> k
```
如果要對正數以及負數完成無條件捨去的右移，則可以寫成下面表示式
```c
(x < 0 ? x + (1 << k) - 1 : x) >> k
```
### EX1.
完成 div16 函數，只能使用位移操作完成，不可使用加減乘除，條件句。對於一整數 $x$，div16 需要回傳 $x/16$，$x$ 為 32 位有號數。
這裡困難點在於，我們不能使用上面推導的結論
`(x < 0 ? x + (1 << k) - 1 : x) >> k`
div16 相當於 $x >> 4$，$k = 4$，如果 $x < 0$，則需要加上 $(1 << 4) - 1 = 15$，這裡我們需要先判斷正負，我們知道對於 32 位整數，符號位於最高有效位，因此，`x >> 31` 即可取出正負號，如果為 0 表示正，1 表示負，0 的情況偏移為 0，1 的情況偏移為 15，我們可以設偏移為 `bias`，表示成以下
`int bias = (x >> 31) & 0xF`
如果 `(x >> 31) == 0`，則 `bias = 0`
如果 `(x >> 31) == 1`，則 `bias = 15`
```c
int32_t div16(int32_t x)
{
int32_t bias = (x >> 31) & 0xF;// 1111
return (x + bias) >> 4;
}
```
### EX2.
下面程式碼
```c
#define M
#define N
int arith(int x, int y)
{
int result = 0;
result = x * M + y / N;
return result;
}
```
經過編譯器優化後，我們將產生的機器語言經過反組譯後翻譯成以下 C 語言程式碼
```c
int opt_arith(int x, int y)
{
int t = x;
x <<= 5;
x -= t;
if(y < 0) y += 7;
y >>= 3;
return x + y;
}
```
試著求出 M 和 N
我們看到，`x = x << 5 - x`，可以得到 `x * 32 - x`，相當於 `x * 31`，因此 M 為 31。
如果 y 為負，則會加上 7，可以知道這個是加上偏置的操作，偏置的值為 $1 \ll k - 1 = 7$，得到 $k$ 為 3，得到 y 要進行的操作為 `y >> 3`，相當於 `y / 8`，因此 N 為 8。
## 整數運算結論
由於我們只能使用固定數量的位去表示一個數，對於整數的運算，實際上是一種模 (module) 運算，通過模運算將結果存放到能夠表示結果的變數中。
我們還看到補數的使用，可以表示正數也可以表示負數，而從位移運算中，我們知道了對於有號數的右移操作，為什麼會使用算術位移作為操作。對於正數或是負數的加減乘除操作，實際上二進位都是相同的表示，不同的是我們對於這一些二進位的解析方式。
對於有號數與無號數的使用，如 C 語言中的 `unsigned` 和 `size_t`，如果和有號數進行了運算，需要注意是否會發生意料之外的行為。
Sign in with Wallet
Connect another wallet