---
# System prepended metadata

title: 數值系統

---

# 數值系統
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]
```cpp
#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 巨集能做什麼？
```clike=
#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
```cpp=
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）

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

執行結果：
```shell
$ ./test
$ echo $?
27
```

## 參考資料

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