2025-03-04 問答簡記
大語言模型對電腦程式開發的思維轉變
朋友嘗試用 Windsurf 搭配 Claude 3.7 Sonnet，僅憑兩項提示詞，就產生可與電腦對弈的中國象棋遊戲。第一項提示詞指定使用 HTML + JavaScript 撰寫網頁遊戲，第二項提示詞則依據給定圖片調整棋盤展現，結果立即獲得可運作的程式碼。在讚嘆新技術發展之餘，我們也該思索大語言模型對電腦程式開發帶來的衝擊。
依據實際測試結果，在 Claude 3.7 Sonnet 之前的大語言模型，儘管可產生中國象棋遊戲的程式碼，但連依循遊戲規則、正確移動棋子都有難度。而新一代的大語言模型則能產生初步可運作的程式碼。那麼，這世界是否還需要軟體工程師？
答案是肯定且否定的。
倘若一位軟體工程師僅能從書本、網站提供的範例、Stackoverflow 討論和 GitHub 專案中囫圇吞棗或模仿，那如此的技能在 Claude 3.7 Sonnet 等新型大語言模型面前，完全站不住腳。當我們嘗試與人工智慧產生的中國象棋對戰時，不難發現該遊戲的「智慧」極為有限。若要提升電腦下棋能力，仍需具備領域知識的專家，藉由 MCTS (Monte Carlo Tree Search) 等方法，針對中國象棋特性，提出在有限運算資源及決策時間內的解決方案，且該針對網頁的安全模型，也就是不能讓網頁瀏覽器引擎偵測到 JavaScript 因運算太久而未能回應來自使用者端的輸入事件 —— 這涉及的知識與經驗累積，目前大語言模型仍難以取代。
Mark Zuckerberg 預測從 2025 年開始，Meta 及其他許多公司將開始使用人工智慧取代中階工程師。Zuckerberg 特別提到中階工程師而非初階或資深工程師，這點非常關鍵。初階工程師需要大量資深人員的指引，且薪資較低、流動性高，公司本來就不會大量招募；中階工程師已能獨立完成小型專案，薪資也較高，取代他們比初階工程師更具成本效益，足以抵消初期導入的投資成本。同時，人工智慧尚未成熟到能完全獨立完成複雜專案，仍需資深工程師的指導。Salesforce 執行長宣稱使用人工智慧後，工程師生產力提升三成，因此 2025 年不打算招募任何軟體工程師。這不僅反映生產力的大幅提升，也暗示企業可能將原本用於人力招募的資金轉投人工智慧的訓練與應用。而 NVIDIA 執行長黃仁勳的洞見尤為深刻：「人工智慧不會取代你的工作，但會使用人工智慧的人會取代你的工作。」
人工智慧的「文藝復興」（我傾向使用這詞彙，反映技術的消長）已深刻改變軟體工程師的日常工作，不僅加速開發流程，也改變對技能的需求。過去工程師需要花大量時間開發及除錯，現在則轉變為引導及調整人工智慧輸出的成果。然而，這也帶來挑戰，特別是對於初階工程師來說，他們的學習機會與職涯發展受到威脅。此外，人工智慧工具的普及也讓工程師可能面臨更高的工作負荷，因為上級期望的產出也隨之提高。
過去，許多企業選擇裁減美國昂貴的工程師，將工作轉移至中國和印度等成本較低的國家。然而，現在人工智慧的成本效益可能已開始超越海外工程師，而且人工智慧可不間斷工作。這意味著海外工程師的就業機會可能會進一步受到壓縮。全球化後的下一波衝擊，是人工智慧化的浪潮。
於是，傳統意義上的中階軟體工程師可能很快消失。軟體工程師的技能及其收益分布將趨向二極化：一端是經驗豐富、具備強大特定領域知識的資深工程師，運用大語言模型再創高峰，成為 10x、50x，乃至 100x 工程師，甚至直接影響科技公司的戰略方向；另一端則是依賴人工智慧工具產生程式碼的從業人員，他們僅能輸入提示詞、選擇不同的人工智慧服務供應商，卻無法理解程式碼的運作原理，只能被動接受工具產出的結果。這種情境，與二十多年前人們依賴 Google 搜尋卻無法超越搜尋結果本身的知識框架如出一轍。
人工智慧大規模應用將取代重複性高的工作，如同工業革命時「會使用織布機的人」取代「會手工織布的人」，但也催生「校調與維修織布機的師傅」。如今，軟體工程領域正經歷相同變革。能夠駕馭、指導、修正人工智慧產出的工程師將脫穎而出，而僅依賴工具產生程式碼的工程師，將逐漸失去市場價值。未來，關鍵在於工程師能否成為「操控織布機的人」，而非被動等待人工智慧產出結果的人。
在人工智慧的協助下，基礎能力反而變得更加重要。工程師需要更扎實的數學、演算法與系統設計能力，以驗證人工智慧的輸出是否正確，避免盲從機器生成的結果。同時，工程師的角色正從單純的技術落實者，轉變為問題解決者與溝通協調者。這需要學習更多跨領域技能，例如產品管理、需求分析，以及用「人話」與非技術部門溝通的能力。初階和中階工程師應考慮轉向人工智慧領域，把握這波人工智慧紅利。人工智慧雖然強大，但仍需人決定「做什麼」、「怎麼做」以及「何時做」。管理層和資深工程師將參考人工智慧意見做決策，並藉此高效完成任務，從而改進整體的成本結構。
這實際上無需恐慌。任何領域邁入全球市場且高度分工時，必然會發生上述的變革，無論是成衣行業、文學出版或電腦程式設計，都在全球化與人工智慧化的雙重衝擊下劇烈改變其面貌。關鍵在於審視自己想在哪一端立足，並順勢而為。
未來不屬於那些否認變化的人，而是屬於那些擁抱並善用新工具提升自我價值的人。軟體開發的思維轉變不是終點，而是新起點 —— 在人機協作的時代中找到自己獨特的位置，從單純的程式碼撰寫者，轉變為人工智慧能力的引導者和放大器。
快訊
- 編譯器/程式語言執行環境相關的職缺
- Ladybird 是款從零開始打造的全新網頁瀏覽器，不使用任何現成的網頁瀏覽器引擎
- EA 在 GitHub 上釋出多款經典即時戰略遊戲《終極動員令》系列的原始程式碼
- Apple iPhone 16e 搭載 Apple 首款自家研發的 5G 數據機，即 Apple C1
學員貢獻的程式碼
- Fix parsing arguments: 修正
qtest處理ih命令時，遇到空白字元會有錯誤處理的問題。感謝 jouae - Avoid unnecessary spaces created by clang-format: 同步 Linux 核心的風格。感謝 gg21-aping
- Add missing parameter hints: 提示
qtest的source命令格式。感謝 Dennis40816 - Remove similar trailer keys from commit hook: 精簡 Git hook 對於結尾訊息的辨識，感謝 lumynou5
- Clarify list_add documentation: 改進文件。感謝 SimonLiu423
- Fix commit hook breakage: 正確處理 commit message。感謝 Dennis40816
- Fix incorrect comments / cont: 改進文件。感謝 yy214123
- Refine trace command descriptions: 改進自動測試任務的描述。感謝 Dennis40816
準備中:
- Allow generating commit message via ollama: 可自動產生 git commit message 的 Git hook (整合於 prepare-commit-msg hook)，只要電腦安裝 ollama 並取得 qwen2.5-coder 模型 (可換)，就能在執行 git commit 時，以大語言模型產生建議的 commit message，日後甚至可對潛藏於程式碼的「壞味道」(bad smell) 進行告警。
charliechiou
32 位元最大的無號整數最大值?
未經思考所得到的答案可能會是 \(2^{32}\)， 32 位元中每個位元可能為 0 或 1，可以表達 \(2^{32}\)個數（包含 0），因此最大可表達數字為 \(2^{32}-1\)，減去 1 拿來表示 0 。
| 可表達總數 | 可表達最大數 |
|---|---|
| \(2^{32}\) | \(2^{32}-1\) |
而 32 位元有號整數最大值為 \(2^{32-1}-1\) ，其中的 \(32-1\)是由於最高位要分配給符號使用，而後面的 \(-1\) 則和無號整數減 1 的原因相同。
檢視 Linux manual page 對於 intmax_t 及 uintmax_t 的敘述，
intmax_t is a signed integer type capable of representing any value of any basic signed integer type supported by the implementation. It is capable of storing values in the range [INTMAX_MIN, INTMAX_MAX]
uintmax_t is an unsigned integer type capable of representing any value of any basic unsigned integer type supported by the implementation. It is capable of storing values in the range [0, UINTMAX_MAX].
由於 linux 可能運行在不同平台，各自對於 int 大小的定義可能不同 (16-bits, 32-bits, 64-bits)，因此這邊的定義描述是透過 INTMAX_WIDTH 來做計算。
#define INTMAX_MAX /* 2**(INTMAX_WIDTH - 1) - 1 */
#define INTMAX_MIN /* - 2**(INTMAX_WIDTH - 1) */
#define UINTMAX_MAX /* 2**UINTMAX_WIDTH - 1 */
以 32 位元的平台為例，其有號整數的最大值 \(2^{32-1}-1\)，最小值 \(-2^{32-1}\)。
0x7F = 0b0111 1111 可用做 bit mask，來取得最高位 (MSB)，因此當見到類似的表示應該要有警覺性。以 FP32 為例，可藉由清除最高位來計算絕對值而不用到較消耗資源的 if statement。
static inline float fabsf(float x) {
uint32_t i = *(uint32_t *)&x; // Read the bits of the float into an integer
i &= 0x7FFFFFFF; // Clear the sign bit to get the absolute value
x = *(float *)&i; // Write the modified bits back into the float
return x;
}
為何最後要加上mpi_t[1]
/* mpi: Multi-Precision Integers */
typedef struct {
uint32_t *data;
size_t capacity;
} mpi_t[1];
將 mpi_t 定義為包含 1 個 struct 元素的陣列，在編譯時便可確保 mpi_t 始終會佔據一個 struct 的空間。而使用陣列的形式而非指標，即可不需要再額外分配記憶體。
int mpi_set_str(mpi_t rop, const char *str, int base)
{
assert(base == 10); /* only decimal integers */
size_t len = strlen(str);
mpi_set_u32(rop, 0U);
for (size_t i = 0; i < len; ++i) {
mpi_mul_u32(rop, rop, 10U);
assert(str[i] >= '0' && str[i] <= '9');
mpi_add_u32(rop, rop, (uint32_t) (str[i] - '0'));
}
return 0;
}
參考規格書中 6.4.5 段落，string 在 C 語言中視為一連串的 char 並在結尾指向NULL
A character string literal is a sequence of zero or more multibyte characters enclosed in
double-quotes, as in "xyz". A wide string literal is the same, except prefixed by the
letter L.
並且分配一個 static storage duration 的 array 儲存足夠空間的 char
The multibyte character sequence is then used to initialize an array of static storage duration and length just sufficient to contain the sequence.
再進一步查看規格書中 6.5.2.1 段落對於 array的敘述
A postfix expression followed by an expression in square brackets [] is a subscripted designation of an element of an array object. The definition of the subscript operator [] is that E1[E2] is identical to (*((E1)+(E2))).
可以知道其為一段連續的記憶體，因此我們使用 mpi_set_str的時候將輸入設為 string 可以方便讀取到需要的字元。
繼續查看 6.4.5 ，如果程式嘗試修改string literals的內容，將會造成未定義行為
It is unspecified whether these arrays are distinct provided their elements have the appropriate values. If the program attempts to modify such an array, the behavior is undefined.
因此若嘗試修改會造成 Segmentation fault ，這是由於 "hello" 存放在唯獨的區段但嘗試修改導致的錯誤。
char *s = "hello";
s[0] = 'H';
而規格書中 5.2.4.1 也提及 string literal 或 wide string literal 最多可包含 4095 個字元。
The implementation shall be able to translate and execute at least one program that
contains at least one instance of every one of the following limits:13)
- 4095 characters in a character string literal or wide string literal (after concatenation)
透過 mpi_set_str 來設定一個 mpi_t 的數值以 mpi_set_str(s, "1844", 10); 為例
size_t len = strlen(str); 先判斷輸入的字串有多少位元需要處理，再透過 mpi_set_u32 來將 rop 初始化為 0.U
後面的迴圈中一次讀取一個 char，讀取時先將先前儲存值乘十以表示左移一位，後將讀取到的值加至 rop 中，迴圈結束後便完成讀取，因此 mpi_set_str 先從高位開始讀取。以下以 1844為例
"1844"
len = 4
rop = 0
---<loop1>---
rop = 0
rop = 1
---<loop2>---
rop = 10
rop = 18
---<loop3>---
rop = 180
rop = 184
---<loop4>---
rop = 1840
rop = 1844
進一步檢視 mpi_set_u32 是如何使用 uint32 來設定 mpi 。
先透過 ceil_div 計算所需要的空間，由於使用 31 位元來保存因此這邊 capacity 計算結果會是 2 需要兩塊才能夠保存，並使用 mpi_enlarge 來分配足夠的空間給 rop。
在迴圈中透過遮罩只取後 31 位並存入 rop 中，接著右移 31 位元繼續下一段的儲存。最後再使用另一個迴圈將剩下空間設定為 0 。
void mpi_set_u32(mpi_t rop, uint32_t op)
{
size_t capacity = ceil_div(32, 31);
mpi_enlarge(rop, capacity);
for (size_t n = 0; n < capacity; ++n) {
rop->data[n] = op & INTMAX;
op >>= 31;
}
for (size_t n = capacity; n < rop->capacity; ++n)
rop->data[n] = 0;
}
以 op = 0xABCDEF12 為例
op = 0xABCDEF12 = 0b 1010 1011 1100 1101 1110 1111 0001 0010
INTMAX = 0x7FFFFFFF = 0b 0111 1111 1111 1111 1111 1111 1111 1111
---<loop1>---
op & INTMAX = 0b 0010 1011 1100 1101 1110 1111 0001 0010 = 0x2BCDEF12
rop->data[0] = 0x2BCDEF12
op >>= 31 = 0b 0000 0000 0000 0000 0000 0000 0000 0001 = 0x00000001
---<loop1>---
op & INTMAX = 0b 0000 0000 0000 0000 0000 0000 0000 0001 = 0x00000001
rop->data[1] = 0x00000001
因此 rop 中 data[0] = 0x2BCDEF12 而 data[1] = 0x00000001 。
rota1001
"12345" 轉成 uint32_t 的改良。
剛才與 weiso131 討論，他提出可以 3 個 3 個一組，然後 x 乘以 1000 可以變成 x 乘以 1024 再減掉 x 乘以 24。
我想，我可以每 4 個 4 個一組，化為 uint32_t 的形式一起相減，然後再用一些位元運算去計算，最差的情況就是用 bitmask。如果說 "1234" 的話，那它轉成 uint32_t 就是 0x34333231，而把它減掉 0x30303030 就會變成 0x04030201。那我可以把 10 和 100 都轉成 2 進位制的 0b1010 和 0b1100100，這些 10 的羃的乘法都能用左移和加法取代，也就是說現在問題被轉化成了如何用各種將位元一起移動或是將一個數字表示成兩個二進位制較少 1 的數字相減的問題，現在在思考這件事。譬如說，"123456789" 這個字串，如果說最後都要用 3 個 3 個一組的話，那麼會乘以 100 的有 1、4、7，會乘以 10 的有 2、5、8，那麼 100 要用 3 個左移和 2 個加法，但是如果我 4 個 4 個一組（在 uint32_t 範圍內），先把東西都乘 10，這個時候因為他們範圍在 0 到 9，所以乘 10 之後還是會在 unsigned char 的範圍內，而以 9 位十進位制數字而言，我只要兩次的乘 10 操作就能覆蓋住所有乘 10 或乘 100 的數字，乘 100 的部份再各自做一次乘以 10 的乘法。
後來決定用加上它乘以 9，去處理乘以 10，是這樣考量的，因為要將那些位元都乘 10 又不影響其他位元，所以用 += 的會更好，而且 \(9 = 1 + 2^3\) 可以少一個左移操作，以下是把需要乘 10 的都先乘 10 的程式碼：
uint32_t str_to_uint32(char *s)
{
unsigned int len = strlen(s);
assert(len == 9);
unsigned char s1[10];
*(uint32_t *) s1 = *(uint32_t *) s - 0x30303030;
*(uint32_t *) (s1 + 4) = *(uint32_t *) (s + 4) - 0x30303030;
*(unsigned char *) (s1 + 8) = *(unsigned char *) (s + 8) - 0x30;
uint32_t ret = 0;
uint32_t tmp = (*(uint32_t *) s1) & 0xff00ffff;
*(uint32_t *) s1 += tmp + (tmp << 3);
tmp = (*(uint32_t *) (s1 + 4)) & 0xffff00ff;
*(uint32_t *) (s1 + 4) += tmp + (tmp << 3);
for (int i = 0; i < len; i++) {
printf("%u ", s1[i]);
}
puts("");
// return ret;
}
後來發現 - 0x30303030 也可以變成 & 0x0f0f0f0f。
如果輸入 "123456789" 我們可以獲得：
10 20 3 40 50 6 70 80 9
然後再加上 3 個三個一組的運算：
uint32_t str_to_uint32(char *s)
{
...
ret += (s1[0] + (s1[0] << 2)) << 1;
ret += s1[1];
ret += s1[2];
ret = (ret << 10) - (ret << 4) - (ret << 3);
ret += (s1[3] + (s1[3] << 2)) << 1;
ret += s1[4];
ret += s1[5];
ret = (ret << 10) - (ret << 4) - (ret << 3);
ret += (s1[6] + (s1[6] << 2)) << 1;
ret += s1[7];
ret += s1[8];
return ret;
}
int main()
{
printf("%u\n", str_to_uint32("123456789"));
}
這樣可以得到輸出：
123456789
接下來我們用 CPU cycle 去測量速度：
直接搬 lab0 的來用
#include "cpucycles.h"
#define PERFTEST(func, ...) \
({ \
int64_t start, end; \
start = cpucycles(); \
func(__VA_ARGS__); \
end = cpucycles(); \
end - start; \
})
實驗函式是這樣，傳入兩個函數和實驗組數，讓它跑 1e7 次，然後交錯測試以降低環境因素影響。
void test(func_t func[2], int n)
{
uint64_t sum[2] = {0};
for(int i = 0; i < 2 * n; i++){
data[i] = PERFTEST(func[i & 1], "123456789");
sum[i & 1] += data[i];
}
FILE *file = fopen("data.txt", "w");
for(int i = 0; i < 2 * n; i++){
fprintf(file, "%lu\n", data[i]);
}
fclose(file);
printf("%lu %lu\n", sum[0], sum[1]);
}
第一個實驗是乘法用 * 10 的和左移 1 個和左移 3 個加起來，發現我用位元運算的時間甚至在平均上比它略慢：
去看編譯的結果發現編譯器和我做了一樣的事情，指令數字也一樣。
- mul 10
pwndbg> x/6i 0x555555555200 0x555555555200 <str_to_uint32_worst+28>: mov edx,DWORD PTR [rbp-0x8] 0x555555555203 <str_to_uint32_worst+31>: mov eax,edx 0x555555555205 <str_to_uint32_worst+33>: shl eax,0x2 0x555555555208 <str_to_uint32_worst+36>: add eax,edx 0x55555555520a <str_to_uint32_worst+38>: add eax,eax 0x55555555520c <str_to_uint32_worst+40>: mov DWORD PTR [rbp-0x8],eax - mul with left shift
pwndbg> x/6i 0x555555555258 0x555555555258 <str_to_uint32_better+28>: mov eax,DWORD PTR [rbp-0x8] 0x55555555525b <str_to_uint32_better+31>: lea edx,[rax+rax*1] 0x55555555525e <str_to_uint32_better+34>: mov eax,DWORD PTR [rbp-0x8] 0x555555555261 <str_to_uint32_better+37>: shl eax,0x3 0x555555555264 <str_to_uint32_better+40>: add eax,edx 0x555555555266 <str_to_uint32_better+42>: mov DWORD PTR [rbp-0x8],eax
接下來的比較是兩個都是用 *10 去做乘法，但是一個是每次字元都減 '0'，一個是直接減 0x30303030，可以發現，減 0x30303030 的效率更高。
接下來比較的是將多個位元一起左移的版本和一直 ret *= 10 的版本（兩邊的迴圈我都直接做展開），可以發現新版本的平均略快。
這裡補一個建 2 * 10 的表格查表的。
uint16_t table[2][10] = {{0, 10, 20, 30, 40, 50, 60, 70, 80, 90},
{0, 100, 200, 300, 400, 500, 600, 700, 800, 900}};
uint32_t str_to_uint32_table(char *s)
{
char s1[10];
*(uint32_t *) s1 = *(uint32_t *) s - 0x30303030;
*(uint32_t *) (s1 + 4) = *(uint32_t *) (s + 4) - 0x30303030;
*(uint32_t *) (s1 + 5) = *(uint32_t *) (s + 5) - 0x30303030;
uint32_t ret = 0;
ret += table[1][s1[0]] + table[0][s1[1]] + s1[2];
ret = (ret << 10) - (ret << 4) - (ret << 3);
ret += table[1][s1[3]] + table[0][s1[4]] + s1[5];
ret = (ret << 10) - (ret << 4) - (ret << 3);
ret += table[1][s1[6]] + table[0][s1[7]] + s1[8];
return ret;
}
然後以下是查表的與 ret *= 10 的比較：
就像預期的那樣，查表比較快。
上面限定在不使用 64 位元整數型別的情況下，接下來使用 64 位元無號整數進行改進。
uint32_t str_to_uint32_64(char *s)
{
unsigned char s1[10];
*(uint64_t *) s1 = *(uint64_t *) s - 0x3030303030303030ull;
*(unsigned char *) (s1 + 8) = *(unsigned char *) (s + 8) - 0x30;
uint32_t ret = 0;
uint64_t tmp = (*(uint64_t *)s1) & 0xffff00ffff00ffffull;
*(uint64_t *) s1 += tmp + (tmp << 3);
...
}
以下是它與多個位元左移但使用 32 位元的程式碼（前面標 new 的那個）的比較：
一次存取 64 位元顯然有明顯的效率改善，因為可以更多位元一起平移，一起減掉 0x30。
另外有注意到一些編譯出來的結果和我想的不同的地方，像是讀取一個字元到 eax 的時候它做了這樣：
movzx eax,BYTE PTR [rbp-0x12]
movzx eax,al
但後面的動作是多餘的。然後還有一些是從堆疊上取值來運算再放回去的，這也有一些多餘動作，像是這件事：
ret = (ret << 10) - (ret << 4) - (ret << 3);
編譯出來長這樣：
mov eax,DWORD PTR [rbp-0x24]
shl eax,0xa
mov edx,eax
mov eax,DWORD PTR [rbp-0x24]
shl eax,0x4
mov ecx,edx
sub ecx,eax
mov eax,DWORD PTR [rbp-0x24]
lea edx,[rax*8+0x0]
mov eax,ecx
sub eax,edx
mov DWORD PTR [rbp-0x24],eax
完全可以簡單的改成這樣：
mov eax,DWORD PTR [rbp-0x24]
shl eax,0xa
mov edx,DWORD PTR [rbp-0x24]
shl edx,0x4
sub eax,edx
mov edx,DWORD PTR [rbp-0x24]
shl edx,0x3
sub eax,edx
mov DWORD PTR [rbp-0x24],eax
甚至可以繼續改良：
mov eax,DWORD PTR [rbp-0x24]
mov edx,eax
shl eax,0xa
shl edx,0x4
sub eax,edx
shr edx,0x1
sub eax,edx
mov DWORD PTR [rbp-0x24],eax
看來這個方向還有改良空間，但基於平台相容性，我就沒有去寫內嵌組合語言了。
同樣是使用 64 位元的無號整數，又想到一個改進方式。原本是將需要乘 10 的和需要乘 100 的都先乘 10，之後再把要乘 100 的乘 10，全部加起來，但這樣的話在最後加總的時候需要去存取 9 個字元（s1[0] 到 s1[8]）。如果我先把百位數加到十位數，這個時候我每次處理一個三位數字時，我都只要做乘 10 、較少的加法還有兩次的字元存取。至於把百位數加到十位數的操作，因為一個數字是用 8 個位元存的，如果將它向左位移 8 格就等同於是將它加到低位的數字上（在十進位制是低位，但在小端序上是高位），然後這裡也一定不會超過 unsigned char 的範圍。所以利用 bitmask 0x00ff0000ff0000ffull 選取百位數，然後用 (x << 1) + (x << 3) 乘 10 之後向左移 8 格再加回去就可以了，而 ((x << 1) + (x << 3)) << 8 又可以化簡為 ((x + (x << 2)) << 9)，這樣只要兩個位元運算和一個加法。以下是改良後的程式碼：
uint32_t str_to_uint32_64_mod(char *s)
{
unsigned char s1[10];
*(uint64_t *) s1 = *(uint64_t *) s - 0x3030303030303030ull;
*(unsigned char *) (s1 + 8) = *(unsigned char *) (s + 8) - 0x30;
uint32_t ret = 0;
uint64_t tmp = (*(uint64_t *)s1) & 0x00ff0000ff0000ffull;
*(uint64_t *) s1 += ((tmp + (tmp << 2)) << 9);
ret += (s1[1] + (s1[1] << 2)) << 1;
ret += s1[2];
ret = (ret << 10) - (ret << 4) - (ret << 3);
ret += (s1[4] + (s1[4] << 2)) << 1;
ret += s1[5];
ret = (ret << 10) - (ret << 4) - (ret << 3);
ret += (s1[7] + (s1[7] << 2)) << 1;
ret += s1[8];
return ret;
}
可以發現，在下面加法和存取陣列的次數減少了，以下是它和同樣是用 64 位元無號整數，但將全部乘 10 的版本的比較：
他的效率在平均表現上又高了一些。
然後這裡寫了奇怪的寫法：
- *(unsigned char *) (s1 + 8) = *(unsigned char *) (s + 8) - 0x30;
+ s1[8] = s[8] - 0x30;
這裡還是去拾人牙慧了。
去看了 shecc 的 lib/c.c 裡面實現了一種基於快速除法的數字轉字串。
因為 \(12 \times (\sum_{i=0}^{\infty}\frac{1}{16^i}) \times \frac{1}{8}= 12 \times\frac{1}{15} \times \frac{1}{8} = \frac{1}{10}\)，所以將這個無窮級數在一個綜合考量下效益最好的位數截斷，在這裡就是 0b0.11001100110011001100110011001100 可以得到一個 \(q\) 的大略值 \(q'\)。
被除數是 \(n\)，\(r' = n - q' * 10\) 不大，所以可以用簡單的方法找整數除。
因為這個函式估計無窮級數到小數點後 32 位（二進位制）所以誤差有：
\[
n \times 12 \times \frac{1}{8} (\sum_{i=0}^{\infty}\frac{1}{16^i} - \frac{\frac{1}{16} - \frac{1}{16^9}}{1-\frac{1}{16}}) = \frac{n}{10 \times 16^8}
\]
如果將 32 位元無號整數的上界帶進去，\(\lfloor\frac{4294967295}{10\times 16^8}\rfloor \approx 0.0999\)
再加上 \(n\) 一直右移捨去的位數，在最差的情況下，0b0.1 + 0b0.11 + 0b0.11111 + 0b0.111111 + … ，約等於 \(15.200000000186265\)，所以兩者加起來會小於 \(16\)，會發現在這個區間中的 \(\lfloor\frac{r' + 6}{16}\rfloor\) 都等於 \(\lfloor\frac{r'}{10}\rfloor\)。
回來看了一下之後，發現我在估誤差值的時候犯了一些錯，\(0.0999\) 沒問題，但是另一個我估到的地方是這段程式碼的誤差：
q = (val >> 1) + (val >> 2);
q += (q >> 4);
q += (q >> 8);
q += (q >> 16);
而之後，將它轉換成商 \(q'\) 時要 q >>= 3，所以 \(q\) 的誤差是 \(15.02 \times 2^{-3}+0.0999=1.9774\)，而因為 \(q\) 的誤差是 \(1.9774\)，所以 \(r\) 的誤差是 \(1.9774 \times 10=19.774\)（注意到先前的計算是把無窮級數截斷的部份加上計算級數過程中捨去的部份相加，所以這裡的誤差指的是 \(r'\) 和 \(\frac{val}{10}\) 差了多少，而不是 \(r\) 和 \(r'\) 差多少，所以求出來的是 \(r'\) 的上界），而可以發現在 \(r'\) 小於等於 \(19\) 的情況下（因為 \(r'\) 一定是整數，最大誤差一定不會超過 \(19\)），\(\lfloor\frac{r' + 6}{16}\rfloor=\lfloor\frac{r'}{10}\rfloor\) 都成立。（這裡只是估一個明顯的上界，但顯然已能說明這個等式在會發生的情況下都適用）
這個誤差值之所以重要是因為 \(\lfloor\frac{r' + 6}{16}\rfloor=\lfloor\frac{r'}{10}\rfloor\) 只有在 \(r'\) 夠小的時候成立，譬如說如果 \(r'=20\) 的時候，前者等於 \(1\)，後者卻等於 \(2\)。
這裡其實也可以不做數學分析，使用實驗來分析，就是誤差最大的情況一定是 \(2^{32} - 1\)（shecc 中輸入是 int，但是實際上 unsigned int 也可以符合範圍），因為最多的 1 會在右移的時候被丟棄，然後直接看求出來的 r 是多少：
int main(){
unsigned int val = (1LL << 32) - 1;
unsigned int q = (val >> 1) + (val >> 2);
q += (q >> 4);
q += (q >> 8);
q += (q >> 16);
q >>= 3;
unsigned int r = val - (((q << 2) + q) << 1);
printf("%u\n", r);
}
輸出是 15，可以發現，它確實在範圍中。
至於 bignum 中的 apm_get_str 單純就只是看他不是 2 的羃就用除法和餘數去求。
salmoniscute
利用「逼近」的方式來取代乘法，並說明是其效益
首先說明 lib/c.c 中的 __str_base10 函式，他會將整數轉換為十進制的字串。核心的概念是透過使用位運算來近似整數除法。rota1001 同學在上一部份已經解釋的很清楚了，我簡單補充會更好理解。
4/5 的二進位表示為 0.1100110011001100110011001100110011001100110011001101，可以看到 1/10 的二進位表示 0.0001100110011001100110011001100110011001100110011001101 正是它右移 3 位的結果。也就是說，如果找出計算 val × 4/5 的方法，只需再右移 3 位就能得到 val / 10。
從 4/5 的二進位展開式開始分析：
\[
\frac{4}{5} = 2^{-1} + 2^{-2} + 2^{-5} + 2^{-6} + 2^{-9} + 2^{-10} + \dots
\]
觀察這個展開式，可以發現一個模式：
\[
\frac{4}{5} = (2^{-1} + 2^{-2}) \times \left(1 + 2^{-4} + 2^{-8} + 2^{-12} + \dots \right)
\]
其中：
\[(2^{-1} + 2^{-2}) = \frac{1}{2} + \frac{1}{4} = \frac{3}{4}\]
這正對應到程式碼中的第一步：
q = (val >> 1) + (val >> 2);
而 \(1 + 2^{-4} + 2^{-8} + 2^{-12} + \dots\) 是一個無限等比級數，公比為 \(2^{-4}\)
根據等比級數求和公式：
\[1 + 2^{-4} + 2^{-8} + 2^{-12} + \dots = \frac{1}{1 - 2^{-4}} = \frac{16}{15}\]
這對應到程式碼中的後續調整步驟，用有限項來逼近這個無限級數：
q += (q >> 4);
q += (q >> 8);
q += (q >> 16);
透過這些操作，我們近似計算出 val * 4/5，然後在最後一步右移 3 位得到 val / 10：
q >>= 3;
那反過來說，如果想將十進制的字串轉換為整數，通常需要透過乘法運算。在課堂討論中，我原本想到的是使用類似上述除法的逼近方法，但其實可以直接用位元運算與加法計算出 val * 10 的精確值。最直觀的方式如下：
(val << 1) + (val << 3)
不過，如果只是單純用迴圈每次乘以 10 進行計算，效率會較低。針對這個問題，rota1001 同學也在上一個部分提出了透過位元運算和數值分組，直接處理整個字串的方法。
回到問題本身，在將十進制字串轉換為整數的這個題目之下，我認為逼近的方法不適合用來替代乘法，因為：
- 精確度問題：此場景可直接使用位元運算，不需要任何近似。逼近法在這種情況下會產生不必要的精度損失。
- 效率考量：位元運算由硬體直接支援，執行速度非常快。相比之下，逼近法需要多次迭代，在這種可以精確計算的題目下使用逼近法反而是捨近求遠。
以下 by jserv :
通常有挑戰的部分，不是從字串轉為內部表示，因為你會撰寫相關的工具，而有挑戰的地方是「輸出」和「比對」，特別是運用現有的工具 (如 Python 的數學運算模組) 進行驗證和額外的運算。
對於逼近方法：
你應該重現實驗，注意到不同的微架構 (micro-architecture) 可能會有不同的表現。
devarajabc
為何以下程式碼無法編譯？
#include <stdio.h>
int main()
{
#if sizeof(long) == 4
printf("It's 32-bit\n");
#else
printf("It's 64-bit\n");
#endif
}
為什麼會這樣呢？ 在規格書 4.2.2 If 中提到：
The preprocessor does not know anything about types in the language. Therefore, sizeof operators are not recognized in ‘#if’, and neither are enum constants. They will be taken as identifiers which are not macros, and replaced by zero. In the case of sizeof, this is likely to cause the expression to be invalid.
因為在 preprocessor 的階段，機器還不知道此語言有什麼 "types"
什麼意思？這跟 sizeof 有什麼關係？
The sizeof operator shall not be applied to an expression that has function type or an incomplete type, to the parenthesized name of such a type, or to an expression that designates a bit-field member.
問題來啦，究竟是在 preprocessor 階段無法使用 sizeof ，還是因為在該階段 sizeof 的輸入在該階段無法使用呢？
讓我們回顧編譯的流程：
原來 C preprocessor 以獨立程式的形式存在，所以當我們用 gcc 或 cl (Microsoft 開發工具裡頭的 C 編譯器) 編譯給定的 C 程式時，會呼叫 cpp (伴隨在 gcc 專案的 C preprocessor) 一類的程式，先行展開巨集 (macro) 或施加條件編譯等操作，再來才會出動真正的 C 語言編譯器 (在 gcc 中叫做 cc1)
那要如何修改才能使用巨集來判斷變數的型態呢？
要使用 6.5.1.1 Generic selection
#define TYPE_NAME(x) _Generic((x), \
char: "char", \
signed char: "signed char", \
unsigned char: "unsigned char", \
short: "short", \
unsigned short: "unsigned short",\
int: "int", \
unsigned int: "unsigned int", \
long: "long", \
unsigned long: "unsigned long", \
long long: "long long", \
unsigned long long: "unsigned long long", \
float: "float", \
double: "double", \
long double: "long double", \
default: "unknown")
SimonLiu423
以下程式碼如何寫得更精簡
unsigned long mask = d << 8 | d;
mask |= mask << 16;
for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
mask |= mask << i;
不難發現其實迴圈外跟迴圈內在做的事情是一樣的，將 i 的初始範圍調整一下即可。
unsigned long mask = d;
for (unsigned int i = 8; i < LBLOCKSIZE * 8; i <<= 1)
mask |= mask << i;
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe