2024q1 Homework1 (lab0)

contributed by < jouae >

開發環境

    $ lsb_release -a
    No LSB modules are available.
    Distributor ID:	Ubuntu
    Description:	Ubuntu 22.04.4 LTS
    Release:	22.04
    Codename:	jammy
    $ gcc --version
    gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
    Copyright (C) 2021 Free Software Foundation, Inc.
    This is free software; see the source for copying conditions.  There is NO
    warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

CPU (Central Processing Unit) 資訊
在 Linux 作業系統行程 (process) ，是以檔案系統 (file system) 的方式存在於 /proc (Linux 核心設計: 作業系統術語及概念：藉由星之卡比解讀 Linux 核心發展)，其中包含 CPU 的詳細資訊。使用 man proc 查看手冊說明：

/proc/cpuinfo
This is a collection of CPU and system architecture dependent items, for each supported architecture a different list. Two common entries are processor which gives CPU number and bogomips; a system constant that is calculated during kernel initialization. SMP machines have information for each CPU. The lscpu(1) command gathers its information from this file.

由於是檔案，可以 cat 連結檔案內容 cat /proc/cpuinfo 便得到相關 CPU 資料，但使用這個方式的話，會列舉所有處理器(processor)的資訊。使用 lscpu 可以得到 Virtualization features 如快取(caches)大小等額外資訊。

    $ lscpu
    Architecture:            x86_64
      CPU op-mode(s):        32-bit, 64-bit
      Address sizes:         48 bits physical, 48 bits virtual
      Byte Order:            Little Endian
    CPU(s):                  6
      On-line CPU(s) list:   0-5
    Vendor ID:               AuthenticAMD
      Model name:            AMD Ryzen 5 4500U with Radeon Graphics
        CPU family:          23
        Model:               96
        Thread(s) per core:  1
        Core(s) per socket:  6
        Socket(s):           1
        Stepping:            1
        Frequency boost:     enabled
        CPU max MHz:         2375.0000
        CPU min MHz:         1400.0000
        BogoMIPS:            4741.04
        Flags:               ...

關於 flags ： What do the flags in /proc/cpuinfo mean?

Linux 中的鏈結串列

linux/include/linux/list.h

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

C macro expansion in Linux Kernel code 解釋中給出

WRITE_ONCE() 你所不知道的 C 語言: linked list 和非連續記憶體
建議搭配 statment expression 與 Linux 核心原始程式碼巨集: max, min 理解實作原理

基本工具

`container_of`

Linux 核心原始程式碼巨集: container_of

不安全的函式

CERN Common vulnerabilities guide for C programmers 給出一些不安全的內建函式。

strcpy()

相較於 strncpy(char *s1, const char *s2, size_t n) ， strcpy(char *s1, const char *s2) 少了 size_t n 參數。

C99 7.21.2.3 The strcpy function：

The strcpy function copies the string pointed to by s2 (including the terminating null character) into the array pointed to by s1.

C99 7.21.2.4 The strncpy function：

The strncpy function copies not more than n characters (characters that follow a null character are not copied) from the array pointed to by s2 to the array pointed to by s1.

If the array pointed to by s2 is a string that is shorter than n characters, null characters are appended to the copy in the array pointed to by s1, until n characters in all have been written.

當 s2 的長度小於 n 時候，會將 null characters 寫入 s1 直到 n 個大小，例如：

    size_t n = 5;
    char *s2;
    s2 = "a";

    strncpy(s1, s2, n);
    for(int i = 0; i < n; i++)
        printf("%d ", s1[i]);

會輸出 ACII 碼，結果會為：

97 0 0 0 0

CERN 給出 strcpy 不安全的例子：

char str1[10];
char str2[]="abcdefghijklmn";
strcpy(str1,str2);

使用 valgrind 來檢查記憶體的狀況：

==42629== Memcheck, a memory error detector
...
==42629== Command: ./strcpy
==42629== 
==42629== Source and destination overlap in strcpy(0x1ffefffdaf, 0x1ffefffdb9)
==42629==    at 0x484EF00: strcpy (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==42629==    by 0x1091B5: main (in /home/yanjie/playground/strcpy)

valgrind User Manual 4.2.6. Overlapping source and destination blocks

問題：使用 GDB 要怎麼看 buffer overflow 的行為？記憶體 stack 要怎麼看？

佇列實作

`q_new`

allocate 翻譯為「配置」，以區格 dispatch (分發/分配) 的翻譯詞彙，二者在作業系統領域都是常見詞彙。

參考 YSRossi 和 chiangkd，配置記憶體空間的時候採用更簡潔的方式表示

// malloc(sizeof(struct list_head))
struct list_head *q = malloc(sizeof(*q));

chiangkd 引用 [C99 7.20.3 Memory management function]

If the space cannot be allocated, a null pointer is returned. If the size of the space requested is zero, the behavior is implementation-defined: either a null pointer is returned, or the behavior is as if the size were some nonzero value, except that the returned pointer shall not be used to access an object.

使用 malloc 有可能無法配置足夠的記憶體而返回空指標（ null pointer ），空指標在某些場合會導致未定義行為（ undefined behavior）。因此直接回傳 q 是不安全的，為了處理這種情況，在回傳前加入一個 if 判斷句，檢查是否成功配置了記憶體。

if(!q) // If the allocation is failed
   return NULL;

改進你的漢語表達。

q_free

由於釋放記憶體的過程會對原本的串列內容做改動，所以需要在遍歷整個串列並改動的同時紀錄原始串列的資訊，才能保證在改動記憶體過程時，指標不會指向未知的地址，這部分可以用 list.h 中定義的 list_for_each_entry_safe 來實踐。

這個巨集中相比 list_for_each_entry 多定義了一個 safe 指標，用於紀錄當前指標指向的下個節點的資訊。但這個巨集的使用僅限於移開（ remove ） 不包含修改串列本身。除了移開節點，任何對串列的修改，都可能會造成未定義行為。

安全的釋放記憶體：

移開節點
list_del()
釋放該節點記憶體
q_release_element()

q_insert_head, q_insert_tail

對於字串（ string ）於 C99 7.1.1 Defitions of Terms 定義為

A string is a contiguous sequence of characters terminated by and including the first null character. The term multibyte string is sometimes used instead to emphasize special processing given to multibyte characters contained in the string or to avoid confusion
with a wide string. A pointer to a string is a pointer to its initial (lowest addressed) character. The length of a string is the number of bytes preceding the null character and the value of a string is the sequence of the values of the contained characters, in order.

參考 chun61205, kdnvt 等的實作方式，當中有使用 strlen() 來取得字串的長度，但在你所不知道的 C 語言：指標——重新探討字串中引用 C99 7.21.1 String function conventions

Various methods are used for determining the lengths of the arrays, but in all cases
a char * or void * argument points to the initial (lowest addressed) character of the
array. If an array is accessed beyond the end of an object, the behavior is undefined.

null pointer *p 使用 strlen(p) 是未定義行為。由於無法預期使用者的行為，所以在此直接使用 strlen() 並非是最好的選擇。所以我想先判斷 s 是否為 null pointer 再執行 strlen()

if (!s)
    return false

使用上述的程式碼會有一個危險，空字元（ null-chararter ）也會回傳 false

C99 5.2.1 Characters Set

A byte with all bits set to 0, called the null character, shall exist in the basic execution character set; it is used to terminate a character string

C99 6.4.4 Character constants

The construction '\0' is commonly used to represent the null character.

所以我用邏輯運算子 ~~&&~~ || 修正上述判斷的過程

- if ((!s) && (s!="")) // If s is null pointer but not null-terminator
+ if (!s || !*s)
    return false

FB 2024 年系統軟體系列課程討論區 2024/02/28 中提問，邱冠維跟黃老師給予指點更正

q_swap

實作 swap 有兩個動作：

選擇要交換的位置
將要交換位置的節點與相鄰的節點兩者互換

void swap (int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = *temp;
}

for each node of list do
    swap(list[index], list[index+1])

但這是 bad taste 的作法，參考 2020leon，善用環狀鏈結串列的特性以及 API 巧妙的使用

以下是原作者將 swap 兩個動作實作的方式：
假設有一個指標的指標（indirect pointer） *i 指向要交換的 list_head 指標。以及實作交換的最小單位，有著兩個 list_head 結構體 a 和 b 節點的串列。

交換的動作
當 *i 指向 a 時，需要將 a->next=b 和 a->prev=b 改為 a->prev=b 和 a->next=b 。同時 b->prev=a 和 b->next=a，改為 b->next=a 和 b->prev=a 。
其實在 list.h 中有定義這操作，那就是 list_move ，由 list_del 和 list_add 組成。 list_del 先將 *i 指向的指標，移開原本屬於的串列：

list_add 最後再將 a 新增到 b 的之後：

list_del 的行為，是 remove 這個動作，其註解中也有解釋：

Remove a list node from the list

兩者的差異可見 Difference between "delete" and "remove"。

選取欲交換位置的過程
由於串列的長度會是奇數或是偶數，將分成兩個情況討論其終止條件
- 串列長度為偶數
  偶數長度串列，可以將整個串列視為成對節點構成的子串列鏈結在一起。所以討論最小可交換串列後，剩下的部分可以用歸納法的方式做結論。最小串列即兩個節點組成的串列，在上述交換動作時，指標 *i 做完交換動作指向 b，根據環狀鏈結串列的特性此時再將 *i 指向下一個位置即為 head ，至此便不用再做交換。每個子串列在內部進行交換後便會指向的相鄰的下個子串列做內部交換，根據歸納法最後可以得到每個已交換子串列組成的串列。因此當串列長度為偶數時，終止條件為 i 指向 head。
- 串列長度為奇數
  奇數長度串列，為成對節點構成的子串列鏈結一起後額外加一個沒有配對的節點組成。可以將整個串列視為前面偶數長度部分跟最後單一節點部分，偶數部分根據上偶數長度的討論，最後 i 指向最後的單一節點時， i->next 指向 head 時便停止交換。
根據上述兩個情況，終止條件為 i->next 為 head 或是 i 為 head 。以邏輯運算子表示的話：
```
i->next == head || i == head
```
其否命題
```
i->next != head && i != head
```
便是迴圈中的控制表達式（ controlling expression ）。

q_reverse

逐一走訪所有節點的同時，將節點從串列移開（ remove ）然後加入至串列的開始。

q_reverseK

這邊對有做一些 K 討論，qtest.c 中 do_reverseK 在判斷 K 的資料型態時，僅只使用 get_int() 判斷型態是否整數。

想到兩個解法：

修改 qtest.c 內容
修改測試程式的內容時，只要將以下控制表達是增加一個邏輯運算子，確認 K 是否小於
$0$ ：

- if(!get_int(argv[1], &k))
+ if(!get_int(argv[1], &k) || k <= 0)

並在 console_init 中修改 do_reverseK 中的增加以下說明：

K must be positive integer.

直接在 reverseK 中做判斷
這邊就要定義當 K 為負數含零時的行為，我這邊是採用甚麼都不做。如下：
```
if (!head || list_is_singular(head) || k <= 0)
    return;
```

我這邊採用後者的作法，由於目前不確認測資的實際行為如何，修改 qtest.c 可能會有無法預期的行為。

q_delete_dup

參考 yanjiew1 另外儲存重複出現的字串，最後再一次全部釋放。

想將最後釋放節點的方式改用成 q_free ：

-    list_for_each_entry_safe (current, safe, &dup_head, list)
-        q_release_element(current);
+    q_free(&dup_head)

過程中有出現一些錯誤提示，這邊使用 valgrind 查看

valgrind ./qtest -v 3

        cmd> new
        l = []
        cmd> it a 4
        l = [a a a a]
        cmd> dedup
        ERROR: Attempted to free unallocated block.  Address = 0x1ffefff910
        ERROR: Attempted to free unallocated or corrupted block.  Address = 0x1ffefff910
        ==17064== Invalid read of size 8
        ==17064==    at 0x10F44F: test_free (harness.c:183)
        ==17064==    by 0x10F75D: q_free (queue.c:44)
        ==17064==    by 0x10F9FA: q_delete_dup (queue.c:219)
        ==17064==    by 0x10C053: do_dedup (qtest.c:465)
        ==17064==    by 0x10DFD1: interpret_cmda (console.c:181)
        ==17064==    by 0x10E586: interpret_cmd (console.c:201)
        ==17064==    by 0x10F1F0: run_console (console.c:691)
        ==17064==    by 0x10D3C3: main (qtest.c:1258)
        ==17064==  Address 0x2003b80ac8 is not stack'd, malloc'd or (recently) free'd
        ==17064== 
        Segmentation fault occurred.  You dereferenced a NULL or invalid pointer

這邊告訴我該去查看 harness.c 的 test_free 實際是如何運作的。因為 q_free 中使用到 q_release_element ，而 q_release_element 中使用 test_free 來釋放配置的記憶體。

但照原作者的方式釋放記憶體，是沒有問題的。具體來說的動作是一樣的藉由 list_for_each_entry_safe 和 q_release_element ，差別在於有沒有函式呼叫。細節部份在你所不知道的 C 語言：函式呼叫篇跟你所不知道的 C 語言：指標篇中應該會有明確的解答。這部份的差異待釐清。

q_remove_head, q_remove_tail

先觀察函式參數的作用，從 queue.h 中註解給定參數的定義為：

@head: header of queue
@sp: string would be inserted
@bufsize: size of the string

查看 qtest.c 中 q_remove_tail 的位置在 351 至 353 行出現。此時指標 *sp 為 remove 這個變數：

re = pos == POS_TAIL
         ? q_remove_tail(current->q, removes, string_length + 1)
         : q_remove_head(current->q, removes, string_length + 1);

追蹤 remove 指標在 qtest 的作用後， *sp 的正確敘述應該是 string would be removed 才對。理由是直接執行 ./qtest 執行以下命令：

cmd> new
l = []
cmd> ih RAND 5
l = [arjqhbb caqgpt efwbhiiu fyzuwbhn dcewkbi]
cmd> rh 1
Removed arjqhbb from queue
ERROR: Removed value arjqhbb != expected value 1
l = [caqgpt efwbhiiu fyzuwbhn dcewkbi]

看到 Removed value arjqhbb != expected value 1 ，從 qtest.c 找出位於 395 至 399 行中的 if 條件句中。

if (ok && check && strcmp(removes, checks)) {
    report(1, "ERROR: Removed value %s != expected value %s", removes,
           checks);
    ok = false;
}

藉由前處理器重構

參考 Shiritai, paulpeng-popo 可以採用前置處理器的方式來簡化程式碼。

你所不知道的C語言：前置處理器應用篇中有提及使用 ## 運算子的例子。GNU onlinedoc 3.5 Concatenation 詳述：

The ‘##’ preprocessing operator performs token pasting. When a macro is expanded, the two tokens on either side of each ‘##’ operator are combined into a single token, which then replaces the ‘##’ and the two original tokens in the macro expansion.

將 ## 前後的兩邊的 tokens 合併成一個 token ，最後用這個 token 替換 ## 與 ## 前後兩邊的 tokens。

其中出現 ## 這個運算子， C99 6.10.3.1 Argument substitution 給出以下敘述：

After the arguments for the invocation of a function-like macro have been identified, argument substitution takes place. A parameter in the replacement list, unless preceded by a # or ## preprocessing token or followed by a ## preprocessing token (see below), is replaced by the corresponding argument after all macros contained therein have been expanded.

與 6.10.3.3 The ## operator：

If, in the replacement list of a function-like macro, a parameter is immediately preceded or followed by a ## preprocessing token, the parameter is replaced by the corresponding argument’s preprocessing token sequence

回頭看程式碼的部份：

#define q_remove(suffix, list_api)                                 \
    element_t *q_remove_##suffix(struct list_head *head, char *sp, \
                             size_t bufsize)

使用這種方式可以藉由 suffix 參數，來生成出不同的函式，例如： q_remove(head, list_first_entry) 便得到 q_remove_head() 的函式。所以藉由前置處理器對 q_remove_head() 、 q_remove_tail() 採用一致的界面 q_remove(suffix, list_api) 來宣告。

隨機

fill_rand_string 生成的隨機字串不均勻

PR #173: Improve string randomness

在 lab0-c 的 qtest.c 中有對於隨機字串插入佇列的功能，藉由 RAND 關鍵字啟用偽隨機字串生成器。使用方式如 ih RAND 5 ，執行 q_insert_head 對佇列開端插入隨機

5

個字串。

在 qtest 中隨機字串生成的函式為 fill_rand_string ，對全域變數 charset 由 26 個小寫英文字母的組成陣列，隨機挑選介於 MIN_RANDSTR_LEN 和 MAX_RANDSTR_LEN 個字元，最後組成字串。

static void fill_rand_string(char *buf, size_t buf_size)
{
    size_t len = 0;
    while (len < MIN_RANDSTR_LEN)
        len = rand() % buf_size;

    randombytes((uint8_t *) buf, len);
    for (size_t n = 0; n < len; n++)
        buf[n] = charset[buf[n] % (sizeof(charset) - 1)];
    buf[len] = '\0';
}

其中偽隨機數的生成藉由 randombytes 實踐。

而 wuyihung 發現在此採用 uint8_t 會有一個問題：

However, since the number of variations is 256, which is not exact division of 26

uint8_t 在 stdint.h(0p) — Linux manual page 中的敘述如下：

The typedef name intN_t designates a signed integer type with width N, no padding bits, and a two's-complement representation.

藉由此敘述得知非符號整數，以十進位表示法範圍為：

[0, 255]

。buf[n] % (sizeof(charset) - 1) 從數學角度解釋，此處是對於

x \equiv i (\mod 26)

選定索引的過程。

藉由除法原理可以得到

255 = 26 \times 9 + 21.

換句話說 0 到 25 數字的倍數在 0 至 255 中，除了 22, 23, 24, 25 倍數之外皆出現 10 次。

假設 randombytes 給定的隨機數是均勻且彼此獨立的，在此之下 0 到 21 數字倍數出現的頻率為 10， 22, 23, 24, 25 倍數為 9 。假設 0 到 25 對應到小寫英文 a 到 z ，其離散機率分佈表示為

P (X = i) = {\begin{cases} \frac{10}{256}, for i = 0, 1, \dots, 21, \\ \frac{9}{256}, for i = 22, 23, 24, 25. \end{cases}

得知隨機生成的字元頻率不均勻。

wuyihung 使用 Python 設計一個測試腳本驗證上述理論上的情況。

他藉由重複執行 ih RAND 30

150, 000 / 30

次後，將串列內所有的字串連接（ concatenate ）成一個字串，並使用 ent分析字串的 entropy 。發現理論跟實際有些許誤差（約

0.0009

）。

-    randombytes((uint8_t *) buf, len);
+    uint64_t *randstr_buf_64 = malloc(len * sizeof(uint64_t));
+    randombytes((uint8_t *) randstr_buf_64, len * sizeof(uint64_t));
    for (size_t n = 0; n < len; n++)
-        buf[n] = charset[buf[n] % (sizeof(charset) - 1)];
+        buf[n] = charset[randstr_buf_64[n] % (sizeof(charset) - 1)];

+    free(randstr_buf_64);

他改用 uint64_t 來改善隨機字串的生成過程。其想法很簡單，就是藉由把上述 8 bits 改成用 64 bits 表示，在上述分佈的分母由

2^{8}

改為

2^{64}

從除法原理得知：

2^{64} = 709490156681136600 \times 26 + 16

其離散機率分佈表示為

P (X = i) = {\begin{cases} \frac{709490156681136601}{2^{64}}, for i = 0, 1, \dots, 16, \\ \frac{709490156681136600}{2^{64}}, for i = 17, 18, \dots, 24, 25. \end{cases}

參照他的實驗方式，此處將使用 uint8_t 和 uint64_t 的結果用 Python 套件 matplotlib 將數據以長條圖（ bar plot ）呈現。

採用 uint8_t：
總共 1050988 個字元。從 a 到 z 的頻率：
[41080, 41161, 40861, 41197, 41150, 40723, 40969, 41191, 41006, 41099, 41278, 41312, 41146, 40890, 41113, 40846, 36915, 36894, 41141, 41231, 41035, 41269, 40993, 40905, 36696, 36887]

採用 uint64_t：
總共 1049822 個字元。從 a 到 z 的頻率：
[40629, 40651, 40560, 40750, 40237, 40244, 39793, 40428, 40261, 40372, 40540, 40571, 40310, 40795, 40222, 39952, 40452, 40058, 40700, 40048, 40713, 40398, 40332, 40431, 40047, 40328]

sizeof() 在 C99 6.5.3.4 The sizeof operator 描述中也是回傳 unsigned integer type

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).

由於 charset 占用的記憶體大小固定，以 26U 取代 sizeof(charset) - 1

採用 uint8_t 並且使用 26U 取代 sizeof(charset) - 1取模：

-        buf[n] = charset[buf[n] % (sizeof(charset) - 1)];
+        buf[n] = charset[buf[n] % 26U];

總共 1050391 個字元。從 a 到 z 的頻率：
[40987, 41617, 40995, 41252, 41100, 40988, 40903, 41212, 40949, 40610, 40903, 41089, 41100, 40931, 41208, 40949, 40958, 40686, 41270, 41415, 40921, 40946, 37085, 36880, 36761, 36676]

排序論文

Bottom-up Mergesort

閱讀筆記： Bottom-up Mergesort

合併排序法的三種比較情況可以概括成：

C (N) = N \log_{2} N + N P (\log_{2} N) + low order terms

其中

P (x)

為週期為

1

的週期函數， Panny 和 Prodinger 以 Flajolet 和 Golin 在 1993 年使用梅林轉換（ Mellin Transforms ）對 top-down 合併排序遞迴過程做漸進分析。

定點數與逼近

定點數

定點數(fixed-point)與數學中提到的固定點定理不同，為一種分數表示方法，例如，新台幣以整數

1

為基本單位，與新台幣不同，美元以一美分為基本單位，通常表示下會以

0.01

美元表示，其中，

\frac{1}{100} = 1 \times \frac{1}{100}

，定點數為

1

乘以一係數

1 / 100

。以此概念建構美元整數表示法，五美分則為

5

，二十五美分為

25

，一美元為

100

以此類推。

總的來說定點數就是一分數表示法，以整數型態儲存，計算實際值時會乘上一係數。

在 C99 擴展規範之一 ISO/IEC TR 18037:2008 — 針對嵌入式裝置的定點數規範，內容涵蓋定點數型態定義方式、命名名稱建議、定點數運算子規範等等。

在 4.2 Detailed changes to ISO/IEC 9899:1999 小節中，兩個 C99 擴展條文描述定點數形式

Clause 5.2.4.2.3 - Characteristics of fixed-point types
一定點數
$x$ 定義為：

$x = s \times n \times b^{f}$
其中，
$s$ 為正負號(-1 或 1)；

$p$ 為精度；

$n$ 為一非負整數且小於
$b^{p}$ ；

$b$ 為一基數，在二進位系統中通常為
$2$ ；

$f$ 為一係數，用於表示小數部分的位數。

舉例來說，以 16 位元的有號整數來表示一定點數

x

，其中 4 個位元用於表示分數部分，11 個位元用於表示整數部分，1 個位元用於表示正負號。

f = - 4

、

p = 11 + 4 = 15

、

0 \leq n < 2^{15}

。假如有一定點數為

549

其二進位表示為 0000 0010 0010 0101 則此定點數

x

實際數值為

x = 549 \times 2^{- 4} = 34.3125 = 2^{5} + 2^{1} + 2^{- 2} + 2^{- 1}

Clause 6.2.6.3 - Fixed-point types
- 對有號定點數，可以將位元分成三個部分：
  1. 正負號位元(sign bit)
  2. 數值位元(value bits)
  3. 填充位元(padding bits)
  對於數值位元又可以分成：
  1. 整數位元(integral bits)
  2. 分數位元(fractional bits)
  其中，假如數值位元為
  $N$ 個且整數位元為
  $L$ 個，則分數位元部分為
  $N - L$ 個。對於用於表示純分數的定點數，該整數位元為
  $L = 0$ 個，則每一數值位元用於表示在
  $2^{- 1}$ 到
  $2^{- N}$ 之間不同
  $2$ 的冪，所以該定點數的實際數值範圍為
  $- 1$ 至
  $1 - 2^{N}$ ；
  對於用於表示帶分數的定點數，則每一數值位元用於表示在
  $2^{L - 1}$ 到
  $2^{N - L}$ 之間不同
  $2$ 的冪，所以該定點數的實際數值範圍為
  $- 2^{L}$ 至
  $2^{L} - 2^{N - L}$ 。
- 對無號定點數，可以將位元分成兩個部分：
  1. 數值位元(value bits)
  2. 填充位元(padding bits)
  對於數值位元又可以分成：
  1. 整數位元(integral bits)
  2. 分數位元(fractional bits)
  其中，假如數值位元為
  $N$ 個且整數位元為
  $L$ 個，則分數位元部分為
  $N - L$ 個。對於用於表示純分數的定點數，該整數位元為
  $L = 0$ 個，則每一數值位元用於表示在
  $2^{- 1}$ 到
  $2^{- N}$ 之間不同
  $2$ 的冪，所以該定點數的實際數值範圍為
  $0$ 至
  $1 - 2^{- N}$ ；
  對於用於表示帶分數的定點數，則每一數值位元用於表示在
  $2^{L - 1}$ 到
  $2^{N - L}$ 之間不同
  $2$ 的冪，所以該定點數的實際數值範圍為
  $0$ 至
  $2^{L} - 2^{N - L}$ 。

常用的定點數表示法為 Q-format，以 Qm.f 表示，其中 m 為整數位元個數及 f 為分數位元個數。例如，以二補數系統中的有號 16 位元整數，定點數表示有 11 個整數位元、 4 個分數位元，及 1 個正負號位元，則 Q-format 表示為 Q11.4。

對數逼近

有了定點數表示法後，就可以明確寫出函數的定義域與對應域範圍。

\tilde{f} (x) \approx \log_{2} (x)

假設使用的定點數系統為 Qm.f，也就是使用 m 個整數位元、 f 個分數位元，及 1 個正負號位元。
其中

\tilde{f} (x)

為一逼近函數，

x

為有號整數，在定點數表示下定義域為

[0, 2^{m} - 2^{f}]

，對應域為

[- 2^{m}, 2^{m} - 2^{f}]

。

可能有些人會有疑問是，為何定義域包含

0

？為何對應域設定下界為

- 2^{m}

及上界為

2^{f}

？這是因為逼近函數邊界映射為

\tilde{f} (0) = - 2^{m}

和

\tilde{f} (2^{m} - 2^{f}) = 2^{m} - 2^{f}

。

以下算法參考 log2fix 實作方式，依據 A Fast Binary Logarithm Algorithm 中提及的算法實作，該算法與計算平方根中的十分逼近法相似，皆是計算一位元接一位元計算出近似值。

x

為輸入，由對數表示輸出

y

：

y = \tilde{f} (x) \approx \log_{2} (x)

則

x = 2^{y}

假設輸出

y

的位元向量表示式寫為

[b_{m + f + 1}, b_{m + f}, b_{m - 1 + f}, \dots, b_{f}, b_{f - 1}, \dots, b_{1}]

其中

b_{i}

的對應關係為

(- 1)^{b_{m + f + 1}} \times \sum_{i = 1}^{m + f} b_{m + f + 1 - i} \times 2^{m - i}

在此求解對數逼近的問題變成找出所有

$b_{i}$ ，其中
$i$ 從
$1$ 至
$m + f + 1$ 。

先討論正負號位元以外的情況。

將

y

以十進位表示可以寫成

\begin{aligned} y & = b_{m + f} \times 2^{m - 1} + b_{m - 1 + f} \times 2^{m - 2} + \dots + b_{f + 1} \times 2^{0} \\ + b_{f} \times 2^{- 1} + b_{f - 1} \times 2^{- 2} + \dots + b_{1} \times 2^{- f} \\ = \end{aligned}

為了以迭代方式計算，改寫成巢狀結構來表示則為

y = 2^{- 1} (b_{1} + b_{2} 2^{- 1} + \dots + b_{n} \times 2^{- (n - 1)})

將其代入

x = 2^{y}

則得到

x = 2^{2^{- 1} (b_{1} + b_{2} 2^{- 1} + \dots + b_{n} \times 2^{- (n - 1)})}

兩側平方後得到

\begin{aligned} x^{2} & = 2^{(b_{1} + b_{2} 2^{- 1} + \dots + b_{n} \times 2^{- (n - 1)})} \\ = 2^{b_{1}} \times 2^{(b_{2} 2^{- 1} + \dots + b_{n} \times 2^{- (n - 1)})} \end{aligned}

在此會有兩個情況

$b_{1} = 0$

$x^{2} = 2^{(b_{2} 2^{- 1} + \dots + b_{n} \times 2^{- (n - 1)})}$
$b_{1} = 1$

$x^{2} = 2 \times 2^{(b_{2} 2^{- 1} + \dots + b_{n} \times 2^{- (n - 1)})}$