就地(不用額外記憶體)把字串反向
前陣子，有位同事看了《約耳趣談軟體》(Joel On Software 中譯版)，就作者提到面試人員教戰守則中的第一道程式問題向我請教。那道題目是「就地(不用額外記憶體)把字串反向」。同事不熟 C 語言，不了解作者為何說不懂指標的人，解這題一定會錯。所以跑來問我。
這道問題難就難在「不用額外記憶體」的條件。再者，就算面試者用了指標，我仍然可以就 C 語言的意義挑毛病，指出光用指標無法滿足「不用額外記憶體」的條件。如果只是從 C 語言的角度思考，僅用指標寫不出滿足條件的字串反向程式。面試者還要能從組合語言的角度思考，才能向出題者解釋他的程式確實滿足條件。
因為我了解指標，所以我會直接寫出下列字串反向程式。(OK, 如果主考官想找一個 C 語言程式設計人員，看到下列程式碼，九成就會直接錄用)
// strrev.c
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
char *f, *t, c;
if (argc < 2) {
puts("input one string");
return 1;
}
f = t = argv[1];
while (*t)
t++;
--t;
while (t > f) {
c = *f;
*f++ = *t;
*t-- = c;
}
puts(argv[1]);
return 0;
}上列程式透過指標指向字串 argv[1]，利用指標搬移字元，所以不用建立額外的字串。
這段程式碼中，沒有出現任何一次 malloc()，看起來似乎滿足「不用額外記憶體」的條件了。但我還是可以挑毛病，「嘿，你定義了三個變數 f,t,c，這三個變數用了額外的記憶體」。
不要懷疑，從 C 語言的定義來說，那三個變數確實用了額外的記憶體。當你在函數內定義了區域變數時，就是在堆疊(stack)中配置記憶體儲存變數內容。編譯器會計算區域變數的總容量，在函數的進入點後，加入一段碼，令堆疊索引暫存器之定址增加等於區域變數總容量之值。如此一來，堆疊索引暫存器與堆疊基底暫存器之定址包住的記憶體區間，就是區域變數額外配置的記憶體。編譯器同樣會在函數的返回點前，加入一段碼，令堆置索引暫存器之定址減少相同之值。這表示釋出區域變數配置的記憶體。
所以光是懂指標，上列程式碼還無法讓我等挑惕者滿意。面試者必須要了解計算機架構(具組合語言的基礎)與 C 編譯器最佳化動作的意涵。才能更進一步地向出題者說明上列程式碼如何得以滿足「不用額外記憶體」的條件。如果你精通組合語言，你就可以用組合語言寫出完全不用額外記憶體的字串反向程式，連解釋都免了。
在平面記憶體定址機制中(float memory)，每一個指標的大小就等於一個暫存器大小。同時，每一個暫存器的大小，也必定大於或等於該計算機中一個無修飾字元的大小 (即 char 等於 byte)。在上列程式中，只使用了兩個指標變數與一個字元變數，以現代 CPU 內含的暫存器數量來看，足夠提供三個暫存器儲存這三個變數的內容。基本上，只要啟用了 C 編譯器的最佳化選項中的暫存器使用最佳化項目，C 編譯器就可以在處理字串反向的程式區段中，找出三個暫存器儲存那三個變數的內容，連堆疊都不必使用。
以 gcc 編譯器為例，只要啟用第一級最佳化 (-O) 就足夠得到我們想要的結果。我利用 gcc 的組譯功能，得到上列 C 程式碼在第一級最佳化後實際產生的組合語言程式碼。下列:
$ gcc -S -O strrev.c
$ cat strrev.s
.file "strrev.c"
.section .rodata.str1.1,"aMS",@progbits,1
.LC0:
.string "input one string"
.text
.globl main
.type main, @function
main:
.LFB34:
.cfi_startproc
subq $8, %rsp
.cfi_def_cfa_offset 16
cmpl $1, %edi
jg .L2
movl $.LC0, %edi
call puts
movl $1, %eax
jmp .L3
.L2:
addq $8, %rsi
movq (%rsi), %rdx
movq %rdx, %rax
cmpb $0, (%rdx)
je .L5
.L10:
addq $1, %rax
cmpb $0, (%rax)
jne .L10
.L5:
subq $1, %rax
cmpq %rax, %rdx
jae .L7
.L8:
movzbl (%rdx), %ecx
movzbl (%rax), %edi
movb %dil, (%rdx)
addq $1, %rdx
movb %cl, (%rax)
subq $1, %rax
cmpq %rax, %rdx
jb .L8
.L7:
movq (%rsi), %rdi
call puts
movl $0, %eax
.L3:
addq $8, %rsp
ret
.cfi_endproc
.LFE34:
.size main, .-main
.ident "GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3"
.section .note.GNU-stack,"",@progbits自標記 L5 起，C 編譯器就令暫存器 rax 為指標 t，令暫存器 rdx 為指標 f，令暫存器 rcx 的低位元組部份 cl 為變數 c。再使用暫存器 edi 的低位元組部份 dil 作為從兩指標間搬移字元的暫存器；也就是負責 *f = *t 此一記憶體間資料搬移動作的暫存器。
標記 L8 到 L7 之間的程式區段，就是 C 程式碼中，實際處理字串反向動作之 while ( t > f) {... } 的內容。這段程式碼只用了暫存器(4個)，沒有使用任何額外的記憶體。故滿足題目的條件。
乍看之下很簡單的一道問題，確實能看出面試者對指標與計算機架構的理解程度。就是要懂這些基礎知識，才能說明你的程式碼真的沒有使用額外的記憶體。
樂多舊回應