---
title: 數值系統篇
tags: C 語言筆記
---
## 數值系統篇
### 有號數字 表示法
* 符號與值 (sign & magnitude)
* 用一個位元 (bit) 來表示 正(+)、負(-)
* 正數表達範圍: 『 + 0 ~ + 2^n-1^ – 1 』 ，負數表達範圍: 『 – 0 ~ – 2^n-1^ – 1 』
* 缺點:
* 電路複雜: 必須要單獨的硬體線路來確定正負號符號位元
* 加法和減法需要各自的硬體電路才能實作：加法運算會產生「進位」(carry)，減法運算需要「借位」(borrow)
* ==0== 的表示不唯一，增加數位電路的複雜性和設計難度，需要進行兩次確認才可以確定是 0
* 表示範圍
* 1 的補數 (==Ones’== Complement)
* 欲計算負值，把 『 1 』 就變 『 0 』，『 0 』就變 『 1 』
* 正數表達範圍: 『 + 0 ~ + 2^n-1^ – 1 』 ，負數表達範圍: 『 – 0 ~ – 2^n-1^ – 1 』
* 表示範圍
* 相較於 sign & magnitude ，優點在於把減法需要的 「借位」(borrow) 給替換掉了，舉例來說
* ```25 - 17``` 明顯需要借位，但如果看做 ``` 25 + (99 - 17) + (1 - 100) ``` 就可以用兩個減法替代原先的一個減法，避免了煩瑣的借位操作，而在十進位的觀點，我們可稱 99 - 17 相較於 -17 為「9 的補數」(nine’s complement)。
* 缺點
* 但是在 1 的補數做加法還是需要考慮到進位，端回進位 (end around carry)，也就是將任何溢出的最高有效位元，加回最低有效位元
* 和「符號與值」編碼方式一樣，0 的表示不唯一
* 應用: 網路通訊協定的檢驗和 (Checksum) 計算
* 2 的補數 (Two’s Complement)
* 2 的補數之『負數』，其實就是 1 的補數 + 1
* 例如:
『 3 』的表示為: 0011
『 -3 』的 1 的補數 表示為: 1100
則『 -3 』的 2 的補數 即為: 1101
* 正數表達範圍: 『 0 ~ + 2^n-1^ – 1 』 ，負數表達範圍: 『 – 1 ~ – 2^n-1^ 』，有一個沒有對應正值的負數 – 2^n-1^
* 表示範圍
* 優點:
* 減法可以用加一個『負數』來完成，ex: 3 – 2 運算，可以透過 3 + (-2) 來完成
* 加法不需要做 端回進位 (end around carry)
* 在二補數系統中的 abs 實作
* 先觀察 Bitwise XOR (^)，如果和一個全是 1 的數做 XOR，則可以得到反轉(0 -> 1、1 -> 0)的效果，所以 ```~x``` 可以用 ```(x ^ 0xFFFFFFFF)``` 表示
* 觀察位移 (shift) 操作:
* Arithmetic shift (算數位移)
* Right shift 時，空出的 bit 填 MSB
* Left shift 時，空出的 bit 填 0
* Logical shift (邏輯位移)
* Right 與 Left shift 時，空出的 bit 皆填 0
* 32 位元整數實作絕對值:
* 若輸入值 x 是正整數則 ```x >> 31``` 得到 0x00000000 => ==0==
* 若輸入值 x 是負整數則 ```x >> 31``` 得到 0xFFFFFFFF => ==-1==
* 方法一: 從 2 的補數的取負數的公式往回推找其正值
```c=
#include <stdint.h>
int32_t abs(int32_t x) {
int32_t mask = (x >> 31);
return (x + mask) ^ mask;
}
```
* 方法二: 再對 x 取一次負值，相當於 -(x)
```c=
int32_t abs(int32_t x) {
int32_t mask = (x >> 31);
return (x ^ mask) - mask;
}
```
* 不需要分支的設計
* 回傳最小值:
```c=
int32_t min(int32_t a, int32_t b) {
int32_t diff = (a - b);
return b + (diff & (diff >> 31));
}
```
* 一樣可以分成兩個情況來看:
* a >= b: (diff >> 31) = ==0==，則 (diff & (diff >> 31) 就可以得到 ==0==， 回傳 b
* a < b: (diff >> 31) = ==-1==， 則 (diff & (diff >> 31) = ==diff== = ==a - b==，回傳 a
### 運用 bit-wise operator
* 將字元大小之間的轉換: 免除使用分支，利用大小寫字母在 ASCII 裡面距離 32 個間隔
* 轉小寫
```c=
('a' | ' ') // 得到 'a'
('A' | ' ') // 得到 'a'
```
* 轉大寫
```c=
('a' & '_') // 得到 'A'
('A' & '_') // 得到 'A'
```
* 大小寫互換
```c=
('a' ^ ' ') // 得到 'A'
('A' ^ ' ') // 得到 'a'
```
* XOR swap: 交換兩個記憶體空間內的數值，可完全不用額外的記憶體來實作，不用額外宣告 temp
```c=
void xorSwap(int *x, int *y) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
```
* 避免 overflow
* ``` (x + y) / 2 ``` 這樣的運算可能會造成 overflow (x 和 y 都接近 int 的上限時)
* 所以可改寫為 ``` (x & y) + ((x ^ y) >> 1) ```
* 這邊的理解可以分成三段，從每個 bits 相加的情況可以分成
* ```0 + 0```: 除以二之後還是0，所以甚麼事都不用做
* ```1 + 0``` 或 ```0 + 1```: 兩個組合除以二之後，等同於==兩個 bits 做 XOR 後再向右位移一格==，之所以要選擇用 XOR 的原因是考慮到 ```0+0``` 跟 ```1+1``` 的情況，```0+0``` 和 ```0+1 or 1+0``` 做 ``` (x ^ y) >> 1 ``` 等同於甚麼都沒做
* ```1 + 1```: ```(1+1)/2``` 等於 ```(1+1) >> 1```，也就是做 ``` (x & y) ``` 就可以了，而其他兩個情況做 ``` (x & y) ``` 都等於 0，不影響
* [參考](https://blog.csdn.net/leo115/article/details/7993110?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1-7993110-blog-8682889.pc_relevant_multi_platform_whitelistv2&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1-7993110-blog-8682889.pc_relevant_multi_platform_whitelistv2&utm_relevant_index=1)
* C 語言程式的 DETECT 巨集
* 用途是在偵測是否為 0 或者說是否為 NULL char ’\0’
```c=
// 32位元
#define DETECT(X) \
(((X) - 0x01010101) & ~(X) & 0x80808080)
// 64位元
#define DETECT(X) \
(((X) - 0x0101010101010101) & ~(X) & 0x8080808080808080)
```
* 考慮一般的 strlen 函式，雖然是對的但是一個一個字元比對太沒效率，現在的 cpu 都是一次處理 32bits 或 64bits 的資料:
```c=
unsigned int strlen(const char *s) {
char *p = s;
while (*p != ’\0’) p++;
return (p - s);
}
```
* 為了方便理解可以先看成 ``` if ((x - 0x01) & (~x) & 0x80) ```
* ```0x80``` 等於 ```1000 0000```
* if 條件式用來判斷 x 是否為 NULL，關鍵在於最後的 ``` & 0x80 ```。也就是說 前兩項(```(x - 0x01) 、 (~x)```)的 most-significant bit(也就是最左邊第一個 bit) 做完 ```&``` 要等於 ==1==，if 才會成立
* ```(x - 0x01)``` 只有在 x 等於 0 的時候 most-significant bit 才會等於 1
* ```(~x)``` 只有在 x < 0x80 時 most-significant bit 才會等於 1
* 所以可以總結出 x = 0 時這個 if 才會成立
* [參考](https://blog.csdn.net/dss875914213/article/details/123217931)
* 代回 ``` (((X) - 0x01010101) & ~(X) & 0x80808080) ``` 思考，只要 X 其中一個 byte 等於 0，這個 if 就會成立。比如說 x = 1001 1100 0000 0000，最後的結果就會是 0000 0000 1000 0000
* Count Leading Zero
* 計算 log~2~N 時可以用，把數字 N 逐步往左移，直到 ```N & 0x80000000``` 成立為止
```c=
int clz(int N) {
int BITS = 31;
for (int i = 0; i < 32; --BITS, i++) {
if (N & 0x80000000) break;
N <<= 1;
}
return BITS;
}
```
* 查表法(利用 De Bruijn sequence)
* 32 bits 版本
```c=
const int tab32[32] = {
0, 9, 1, 10, 13, 21, 2, 29,
11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7,
19, 27, 23, 6, 26, 5, 4, 31
};
int log2_32 (uint32_t value)
{
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
return tab32[(uint32_t)(value*0x07C4ACDD) >> 27];
}
```
* tab32 可以看做一個 De Bruijn sequence
* B(k, n) 是一種 sequence，由 k 種不同符號組成，且其所有長度為 n 之連續子序列 恰為 k 種符號組成長度為 n 的所有排列
* 舉例來說 ```00010111``` 即為一 B(2, 3) 序列，因其連續子序列（尾端循環至開頭: 000, 001, 010, 101, 011, 111, 110, 100 恰為所有由 {0, 1} 組成且長度 3 的序列
* 所以 tab32 是 B(2, 5) 的其中一種排列
* ```(uint32_t)(value*0x07C4ACDD) >> 27``` 為 hash function
* value 就是把 最高位的 1 之後的 bits 都轉成 1，ex: 0100 -> 0111
* 0x07C4ACDD 為 tab32 轉成 De Bruijn sequence 後的結果
* 27 = 32 - 5 (32 個 bits - n)，64位元 就是 64 - 6，用來讓得到的數介於 [0, 31] 區間
* [參考1](https://halfrost.com/go_s2_de_bruijn/)、[參考2](https://blog.csdn.net/aixgw8112/article/details/101274095)、[參考3](https://en.wikipedia.org/wiki/De_Bruijn_sequence)、[參考4](https://hackmd.io/@9U2ovSU_QH2j8MuHZG6yRg/rkJXW_wjW?type=view)
* gcc 提供 [built-in Function](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)，可用來實作 log2:
```c=
#define LOG2(X) ((unsigned) \
(8 * sizeof (int) - \
__builtin_clz(X) - 1))
```
* 實作 CLZ
* iteration version:
```c=
int clz(uint32_t x) {
int n = 32, c = 16;
do {
uint32_t y = x >> c;
if (y) {
n -= c;
x = y;
}
c >>= 1;
} while (c);
return (n - x); //x 最後一定是 1，改成 n - 1 也可
}
```
* 範例
當 x = 0f001234
* loop 1:
y = 0f00 (0f00|1234) ; n = 16 (因為確定 x 的 clz 不在這個區間 (y != 0)，所以可以扣掉右移的 16 bits) ; x = 0f00 (然後從左半個 x 開始找) ; c = 8
* loop 2:
y = 0f (0f|00) ; n = 8 ; x = 0f ; c = 4
* loop 3:
y = 0 (0|f) ; n 不變 ; x 不變 ; c = 2
* loop 4:
y = 000011 (000011|11) ; n = 6 ; x = 000011 ; c = 1
* loop 5:
y = 00001 (00001|1) ; n = 5 ; x = 00001 ; c = 0
* 回傳 5 - 1 = 4
* binary search technique
```c=
int clz(uint32_t x) {
if (x == 0) return 32;
int n = 0;
if (x <= 0x0000FFFF) { n += 16; x <<= 16; }
if (x <= 0x00FFFFFF) { n += 8; x <<= 8; }
if (x <= 0x0FFFFFFF) { n += 4; x <<= 4; }
if (x <= 0x3FFFFFFF) { n += 2; x <<= 2; }
if (x <= 0x7FFFFFFF) { n += 1; x <<= 1; }
return n;
}
```
* 範例:
* 以其中一個為例，``` if (x <= 0x0000FFFF) { n += 16; x <<= 16; } ``` ，if 如果成立代表 CLZ 一定在 32 bits 的 右邊 16 bits 之中，所以 ```n += 16```，右移 16 bits 是要配合下一個 if 判斷```if (x <= 0x00FFFFFF) ```
* byte-shift version
```c=
int clz(uint32_t x) {
if (x == 0) return 32;
int n = 1;
if ((x >> 16) == 0) { n += 16; x <<= 16; }
if ((x >> 24) == 0) { n += 8; x <<= 8; }
if ((x >> 28) == 0) { n += 4; x <<= 4; }
if ((x >> 30) == 0) { n += 2; x <<= 2; }
n = n - (x >> 31);
return n;
}
```
* 概念與 binary search technique 相似
* [浮點數運算](https://hackmd.io/@sysprog/c-numerics#Count-Leading-Zero)
Sign in with Wallet
Connect another wallet