---
# System prepended metadata

title: 數值系統篇
tags: [C 語言筆記]

---

---
title: 數值系統篇
tags: C 語言筆記
---
## 數值系統篇
### 有號數字 表示法
* 符號與值 (sign & magnitude)
    * 用一個位元 (bit) 來表示 正(+)、負(-)
    * 正數表達範圍: 『 + 0  ~  + 2^n-1^ – 1 』 ，負數表達範圍: 『 – 0  ~  – 2^n-1^ – 1 』
    * 缺點:
        * 電路複雜: 必須要單獨的硬體線路來確定正負號符號位元
        * 加法和減法需要各自的硬體電路才能實作：加法運算會產生「進位」(carry)，減法運算需要「借位」(borrow)
        * ==0== 的表示不唯一，增加數位電路的複雜性和設計難度，需要進行兩次確認才可以確定是 0
    * 表示範圍
    ![](https://i.imgur.com/ZKiZsze.png)
* 1 的補數 (==Ones’== Complement)
    * 欲計算負值，把 『 1 』 就變 『 0 』，『 0 』就變 『 1 』
    * 正數表達範圍: 『 + 0  ~  + 2^n-1^ – 1 』 ，負數表達範圍: 『 – 0  ~  – 2^n-1^ – 1 』
    * 表示範圍![](https://i.imgur.com/Xnez157.png)
    * 相較於 sign & magnitude ，優點在於把減法需要的 「借位」(borrow) 給替換掉了，舉例來說
    * ```25 - 17``` 明顯需要借位，但如果看做 ``` 25 + (99 - 17) + (1 - 100) ``` 就可以用兩個減法替代原先的一個減法，避免了煩瑣的借位操作，而在十進位的觀點，我們可稱 99 - 17 相較於 -17 為「9 的補數」(nine’s complement)。
    * 缺點
        * 但是在 1 的補數做加法還是需要考慮到進位，端回進位 (end around carry)，也就是將任何溢出的最高有效位元，加回最低有效位元
        ![](https://i.imgur.com/d4Dz2Kj.png)
        * 和「符號與值」編碼方式一樣，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^
    * 表示範圍![](https://i.imgur.com/lHCVssw.png)
    * 優點:
        * 減法可以用加一個『負數』來完成，ex: 3 – 2 運算，可以透過 3 + (-2) 來完成
        * 加法不需要做 端回進位 (end around carry)
* 在二補數系統中的 abs 實作
    * 先觀察 Bitwise XOR (^)，如果和一個全是 1 的數做 XOR，則可以得到反轉(0 -> 1、1 -> 0)的效果，所以 ```~x``` 可以用 ```(x ^ 0xFFFFFFFF)``` 表示
    * 觀察位移 (shift) 操作:
        * Arithmetic shift (算數位移)![](https://i.imgur.com/g8gP7tQ.png)
            * Right shift 時，空出的 bit 填 MSB
            * Left shift 時，空出的 bit 填 0
        * Logical shift (邏輯位移)
        ![](https://i.imgur.com/ysOpvp3.png)
            * 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)
    