編程實現從 1 加到 100 和從 100 加到 1 兩個程序，哪個更快？為什麼？
該問題系中國科學技術大學軟體學院考研面試問題。
據悉某考生回答一樣快，被教授懟了，教授問「有沒有複習機器碼？」。
各位大佬可以參考回答。
在x86/ARM之類的主流架構上和RISC-V這種較新的架構上，如果不做任何優化，直接硬算，100加到1指令數會少一些。在單發射順序執行的處理器上，100加到1會更快。
比如說RISC-V彙編，從1加到100：li a0, 0
li a1, 100
li a2, 0
L0:
addi a0, a0, 1
add a2, a2, a0
beq a0, a1, L0
li a0, 0
li a1, 100
L1:
add a0, a0, a1
addi a1, a1, -1
beqz a1, L1
4/23 7:10PM補充一下：
循環體中的三條指令在亂序執行的處理器中完全也可以重新排序後同時執行。對於從100加到1的程序而言，循環體內a0 a1之間是不存在顯式的數據依賴的，因此兩條加法指令是可以同時運行的。對於beqz指令而言，即使是簡單的前跳後不跳分支預測器在這個場景下也能猜對99次，設計較為激進的處理器甚至可以同時運行這三條指令。
而對於從1加到100的程序而言，其實在流水線dispatch這一步把指令順序做一個重排，和從100加到1的循環體就完全一樣了。場景也應該是完全一樣的。
綜上所述，硬算100加到1對於嵌入式應用或者較老的處理器來講，應該是比硬算1加到100快的。對於比較現代的處理器來講，應該是不會有顯著差別，甚至執行時間是完全相同的。
答案是一樣快，因為
int sum1() {
int sum = 0;
for (int i = 1; i &<= 100; ++i) {
sum += i;
}
return sum;
}
int sum2() {
int sum = 0;
for (int i = 100; i &>= 1; --i) {
sum += i;
}
return sum;
}
使用g++ -O2編譯後得到
sum1():
mov eax, 5050
ret
sum2():
mov eax, 5050
ret
這是個沒有上下文的問題，也沒說用什麼語言，運行在什麼平台上。那我就 assume 語言是 C++，目標平台為 x86-64，編譯器為 gcc 8.3。
首先單純的 1 加到 100 是沒有意義的，因為開 -O3 的情況下編譯器直接 emit：
mov eax, 5050
ret
所以問題變成，從 1 加到 n 快還是從 n 加到 1 快。
首先是 1 加到 n：
test edi, edi
jle .L4
add edi, 1
mov edx, 1
xor eax, eax
.L3:
add eax, edx
add edx, 1
cmp edx, edi
jne .L3
ret
.L4:
xor eax, eax
ret
然後是 n 加到 1：
xor eax, eax
test edi, edi
jle .L10
.L9:
add eax, edi
sub edi, 1
jne .L9
ret
.L10:
ret
顯然後者指令更少，尤其是循環體內比前者少了一個 cmp 指令。其實這個問題在實際應用場景下意義不大，因為對於 n 很大的情況，直接用等差數列求和公式明顯比任何用循環的方式都快。即便是必須要用循環的場景，也可以通過循環展開（參考：Duffs device）來優化。
而且編譯器比你想像地要強大，開了 -O3 之後的 gcc 甚至會對循環次數大於一定閾值的代碼直接開啟 SIMD 指令優化，理論上比一遍一遍簡單地循環還要快。
不過話說回來，我不太懂教授反問的「有沒有複習機器碼？」是什麼意思，這跟機器碼有什麼關係嗎？
補充：
剛才試了一下，clang -O3 優化的時候直接就是高斯求和公式：
test edi, edi
jle .LBB0_1
lea eax, [rdi - 1]
lea ecx, [rdi - 2]
imul rcx, rax
imul eax, eax
shr rcx
add eax, edi
sub eax, ecx
ret
.LBB0_1:
xor eax, eax
ret
這是一個非常有趣的問題——而且也一直以來都很有爭論。
認為「100加到1比1加到100」快的人，往往是基於這樣一個事實：
jnz指令要明顯快於cmp之後再jne
但是，這裡有一個問題：編譯器是否真的會把循環中的「不等於零」用nz指令來替換？
這裡以C語言為實驗對象。
好的，我現在在wsl上運行了gcc (Ubuntu 7.4.0-1ubuntu1~18.04) 7.4.0
然後，用下面這段程序作為例子。
int sum;
int i;
int main(){
sum=0;
for(i=100;i!=0;i--)
sum+=i;
return 0;
}
一個很簡單的C程序。
我們用gcc來進行一下彙編。
gcc -O0 -S 1.c
好的，我猜不會有多少人願意看……那就摘一下重點吧。
比較的地方的彙編如下：
movl i(%rip), %eax
testl %eax, %eax
jne .L3
而對於「從1加到100」而言，這一段則是
movl i(%rip), %eax
cmpl $100, %eax
jle .L3
並沒有本質的區別。
為了保險起見，我們把循環中的
for(i=100;i!=0;i--)
改成
for(i=101;--i;)
於是，對比輸出的彙編結果，除了循環體內的減法操作跑到了比較的地方之外，並沒有更多的差別。
那麼，如果打開/O1呢…會不會把nz這種東西優化進來
movl $5050, sum(%rip)
當我沒說…
於是現在，我們使用msvc試一試。(19.16.27030.1)
cl /Od /FAs /c /Fonul 1.c
和剛才類似地，對於一路減下去的做法，彙編里依然多了個cmp指令
cmp DWORD PTR i, 0
je SHORT $LN3@main
而，如果是一路加上來，比較也並不會複雜很多
cmp DWORD PTR i, 100 ; 00000064H
jg SHORT $LN3@main
至於那種非要把--i放到循環條件里的…enmmm…您別說，還真的少了一行彙編…
我找了半天才看出來差在哪…
別人是先jmp到循環條件那裡檢查一下…不知道為啥，到了這裡就是一個大循環…
不過…要執行上千行彙編的事…您給我說這一行jmp…不太好吧…
好的，看到有人說到了「上古時代」的編譯器會有這種特性。
於是在DOSBOX中運行Turbo C 1.0進行實驗。
TCC -S 1.c
一如既往，同樣的行數，同樣的快樂。
cmp word ptr dgroup:_i,0
jne @4
cmp word ptr dgroup:_i,100
jle @4
然而，在最後一種「奇葩」方法的測試中，我們終於如願以償收穫了驚喜。
dec word ptr dgroup:_i
jne @4
在循環體內，確實就像想像的那樣，少了一個cmp指令。
不過先不要急著下結論。我們繼續我們的實驗。
這次我們用剛剛下載的icc來測試(Version 19.0.3.203 Build 20190206)
test eax, eax ;5.15
je .B1.4 ; Prob 50% ;5.15
cmp eax, 100 ;5.13
jg .B1.4 ; Prob 50% ;5.13
而--i的做法這次…
我看了好半天…有點沒看明白為什麼會出現這種智障操作…
mov DWORD PTR [rbp], eax ;5.14
mov eax, DWORD PTR [rbp] ;5.14
mov DWORD PTR [i], eax ;5.14
mov eax, DWORD PTR [rbp] ;5.14
不過從結果上來看…它每次循環比另外兩種寫法要多執行兩條語句…
以後我想做一下其它語言和編譯器的測試
不過就目前的結果來看…
這名學生完全可以問面試官具體的架構環境編譯器參數…
嗯，如果面試官認為沒開優化的編譯器都可以…那麼…
「老師，您預習編譯原理了嗎？」
如果完全從彙編的角度看，從 100 加到 1 要比從 1 加到 100 要快一點。
因為彙編有單獨令 cx 和 0 比較進行跳轉的指令 jz 和 jnz。從 100 加到 1，加數每次自減 1，最後加數會變成 0。假設加數用的是 cx 寄存器，在比較的時候用 jnz l 一條指令跳轉就夠了。
如果從 1 加到 100，那麼在比較加數寄存器的時候，先要寫一句 cmp cx, 100，然後再 jnb l，無形中多了一條指令。
如果是高級語言的話，那要看最終編譯器彙編成的代碼是什麼樣子的才能得出結論。
推薦閱讀：
