# 數值系統
contributed by < `colinyoyo26` >

## 數值表達方式和阿貝爾群
- 在一個非空集合上定義一個或以代數運算及為一個代數系統 (algebraic system)
- 在非空集合上定義一個二元運算滿足以下條件稱為群 (group)
- Close
- Associativity
- Exist identity
- Iverse property
- 具 commutativity 的群稱為 abelian group
- 電腦的 2’s complement 整數加法形成 group
- 以 4 bits 為例，可由其同構於，模 32 的整數加法群得證
- 浮點數運算不具結合性
- 考慮 IEEE 754 單精度浮點數運算
- 相加時為了對齊指數會位移小數部份，造成不同順序的運算精度可能不同的情況

## Integer Overflow 案例分析
- 2002 年 FreeBSD [53]

#define KSIZE 1024
char kbuf[KSIZE];
int copy_from_kernel(void *user_dest, int maxlen) {
    int len = KSIZE < maxlen ? KSIZE : maxlen;
    memcpy(user_dest, kbuf, len);
    return len;
}

:::info
假設懷有惡意的程式設計師將「負」的數值作為 maxlen 帶入 copy_from_kernel，會有什麼問題？
:::

- Linux Programmer's Manual about memcpy declaration
> void *memcpy(void *dest, const void *src, size_t n);

- C99 size_t 型態
> The value of the result is implementation-defined, and its type (an unsigned integer type) is size_t, defined in `<stddef.h>`(and other headers)

- 可以看到 memcpy 第三個參數是 size_t 為 unsigend int type 所以使用者惡意傳入負數將可以得到超範圍的資料

## 運用 bit-wise operator
- xor swap
- 在暫存器或是記憶體有限的硬體架構中需要使用這種手法
- 原理為 (a ^ b) ^ a = b 可以輕易得證

temp = a;
a = b;
b = temp;

>可用 xor 避免使用額外變數如下

a ^= b;
b ^= a;
a ^= b;

- 避免 overflow
- ``(x + y) / 2`` x + y 時可能有 overflow 的問題
- 可以改為 ``(x & y) + ((x ^ y) >> 1)``
- 其中 (x & y) 可以理解為 carry bits 除以 2
- (x ^ y) >> 1 可以理解為 原本的 bits 扣掉進位的 bits 再除以2
- <s>自己覺得有點邊除邊加的感覺</s>
:::danger
注意工程人員的推論和精準用語
:notes: jserv
:::

- C 語言程式的 DETECT 巨集能做什麼？

#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

- 看了老師共筆的解釋，在用自己的方式理解如下 (考慮 1 byte)

(x - 0x01) & ~x & 0x80

# 根據 & 的結合性，還有 DeMorgan

=    ~(~(x - 0x01) | x) & 0x80

# ~(x - 0x01) + 1= -(x - 0x01) -> ~(x - 0x01) = -x 

=    ~(-x | x) & 0x80

# -x | x 結果為 x 最靠右的 1 往右全為 0 往左(包括)全為 1

# 所以 ~(-x | x) & 0x80 若為非 0 結果(0x80)，只會有 x = 0 一種可能

- 假設字串是 "abc\0" 那回傳的結果會是 0x00000080 就可以知道第 4 byte 為 '\0'
- 用者個方法就能一次檢查 4 bytes 不浪費 CPU 資源了

## Count Leading Zero
- 計算 log2 時可以用 `31 - leading zero` 計算
- clz 可以用 bit-wise 達到常數時間實做
- binary search technique

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;
}

>把 binary search 巧妙的應用在這超強的
- 以下是我的理解
- 兩個版本分別從 binary search 和 2 進位切入
- 從 binary search 理解
- 0 的範圍為 0~32 一開始
- left = 0
- right = 32
- mid = (left + right) / 2 = 16
- 可以看到這個 code 巧妙的應用 binary search
- 如果 leading zero(以下簡稱 LZ) 小於 16 bits
- 對照 line 4 line 5 (觀察 mask)
- 再檢查 LZ 有沒有大於等於 8 bits （binary search 往左找的感覺)

- 如果 LZ 大於等於 mid (16 bits)
- 對照 line 4 line 5 (觀察 mask)
- X <<= 16 讓變數的 LZ 減少 16 bits 並且 n+16
- 在繼續檢查剩下的 LZ 有沒有大於等於 8 bits
- 用相同邏輯推論到最後

- 從 2 進位理解
- LZ 數量寫成二進可以寫成 6 個 bits
- 從這個角度切入 6 個 if 相當於從 MSB 開始檢查每個 bits 是否為 1
- 現在直接接把 x 當成 `#of` LZ 在已知範圍為 0~32 的情況下找 x 比較直觀一點 （以下 code）

int main(void) {
    //27 = 011011 in binary
    int x = 27, n = 0;
    
    if(x == 32) return 32;
    if (x >= 16) { n += 16; x -= 16; }
    //now x equal to 001011 in binary
    if (x >= 8) { n += 8; x -= 8; }
    //now x equal to 000011 in binary
    if (x >= 4) { n += 4; x -= 4; }
    if (x >= 2) { n += 2; x -= 2; }
    //now x equal to 000001 in binary
    if (x >= 1) { n += 1; x -= 1; }
    //now x equal to 000000 in binary
    return n;
}

執行結果：

$ ./test
$ echo $?
27

## 參考資料

* [你所不知道的C語言：數值系統篇](https://hackmd.io/@sysprog/BkRKhQGae)