高效程序的奧秘.PDF

本書也許會(huì)激起某些讀者的懷舊情感，特別是那些經(jīng)歷過或曾向往在早期的Z80等計(jì)算機(jī)上用匯編語言或Basic語言編程的人們；那些竭盡全力、苦思冥想，僅僅是為了能夠?qū)懗龈��?jiǎn)短、更高效程序的人們；那些以編寫一行高效Basic程序而自我陶醉的人們。
本書適用于那些想要編寫及欣賞巧妙、高效代碼的讀者，特別適合于希望把計(jì)算機(jī)軟件和硬件有機(jī)地結(jié)合在一起的讀者。本書值得每一位認(rèn)真的計(jì)算機(jī)硬件設(shè)計(jì)者，每一位希望編寫高效、優(yōu)雅的嵌入式程序、編譯器及優(yōu)化編譯器的設(shè)計(jì)者，以及每一位希望提高程序設(shè)計(jì)技藝的讀者仔細(xì)斟酌和品味。

為了減少印刷錯(cuò)誤和疏忽，我們實(shí)際運(yùn)行了很多算法。因此，盡管每一種計(jì)算機(jī)語言都有不盡人意的一面，但我們還是使用程序設(shè)計(jì)語言給出了這些算法。由于C語言的高知名度，我們把它作為高級(jí)語言使用，它既允許整數(shù)操作，也允許位串操作，并且我們有產(chǎn)生高質(zhì)量目標(biāo)代碼的C編譯器。
偶爾我們也使用機(jī)器語言。它使用三地址格式，主要是為了可讀性。我們使用的匯編語言是RISC虛擬計(jì)算機(jī)的匯編語言。


本書是我多年來所收集的程序設(shè)計(jì)小技巧的集成，它們大部分只能應(yīng)用于以2的補(bǔ)碼的形式表示整數(shù)的計(jì)算機(jī)上。盡管當(dāng)這些技巧與寄存器的長(zhǎng)度相關(guān)時(shí)，我們假設(shè)機(jī)器是32位的，但是我們很容易將這些技巧運(yùn)用到其他寄存器長(zhǎng)度的計(jì)算機(jī)上。

我們盡量使用無分支代碼。因?yàn)樵谠S多機(jī)器上，分支會(huì)減慢指令提取，抑制指令的并行執(zhí)行。分支的另一個(gè)問題是它們可能會(huì)抑制編譯器的優(yōu)化，例如指令調(diào)度、指令公用以及寄存器分配。也就是說，編譯器可能會(huì)更有效地優(yōu)化由若干大的基本塊組成的程序，而對(duì)于由許多小基本塊組成的程序進(jìn)行優(yōu)化的效果則可能不顯著。

本書不涉及大型的編程技巧，例如高級(jí)排序技術(shù)和編譯器優(yōu)化技術(shù)等；相反，它所討論的是諸如計(jì)算一個(gè)字中值為1的位的數(shù)目這樣的與計(jì)算機(jī)的字或指令相關(guān)的小技巧，這樣的技巧通常是算術(shù)指令和邏輯指令的混合物。

本書自始至終都假設(shè)整數(shù)溢出中斷被屏蔽，所以不會(huì)發(fā)生溢出中斷。C語言、Fortran語言、Java語言運(yùn)行在這樣的環(huán)境下，但是Pascal語言和ADA語言的用戶則要小心。
本書的描述是非形式化的。只有當(dāng)算法不是顯然的時(shí)才給出證明(有些也不證明)。我們使用計(jì)算機(jī)算術(shù)、“地板”函數(shù)、算術(shù)和邏輯操作的混合等來描述這些小技巧。在這些領(lǐng)域，證明通常相當(dāng)困難并且難以表述。

代碼序列中也常出現(xiàn)小的立即值、與零的比較(而不是與其他數(shù)相比較)以及指令級(jí)的并行。盡管通過(從內(nèi)存)查表可以使大部分代碼更簡(jiǎn)潔，但本書不常提及查表法。這是因?yàn)橄鄬?duì)于算術(shù)指令，其裝入的代價(jià)越來越大，而且查表法通常不是很有趣(盡管它們通常很實(shí)用)。當(dāng)然也有例外的情況。

IBM資深程序員、藍(lán)基因千萬億浮點(diǎn)計(jì)算機(jī)項(xiàng)目參與者Henry S．Warren，Jr.給所有程序員帶來一本他們到處尋覓、實(shí)實(shí)在在、具有現(xiàn)實(shí)意義的程序設(shè)計(jì)技巧指南。本書是一本有特色的算法參考書，它不像現(xiàn)今多數(shù)算法書那樣討論大型的程序設(shè)計(jì)技術(shù)和系統(tǒng)的程序設(shè)計(jì)方法，而是向讀者展示了計(jì)算機(jī)代碼與指令，以及指令間的令人驚嘆的內(nèi)在關(guān)聯(lián)，并通過這樣的內(nèi)在關(guān)聯(lián)向讀者揭示計(jì)算機(jī)運(yùn)行的某些奧秘，揭示通過這樣的關(guān)聯(lián)更有效地實(shí)現(xiàn)基本操作的精湛技巧，以及這些技巧在優(yōu)化編譯器、圖形學(xué)、密碼學(xué)乃至數(shù)學(xué)中的應(yīng)用。

第1章 介紹
1．1 記法
1．2 指令集和運(yùn)行時(shí)間模型
第2章 基礎(chǔ)
2．1 操作最右側(cè)位
2．2 結(jié)合邏輯操作的加運(yùn)算
2．3 邏輯和算術(shù)表達(dá)式中的不等式
2．4 絕對(duì)值函數(shù)
2．5 符號(hào)擴(kuò)展
2．6 用無符號(hào)右移位實(shí)現(xiàn)帶符號(hào)右移位
2．7 符號(hào)函數(shù)
2．8 三值比較函數(shù)
2．9 符號(hào)傳遞
2．10 對(duì)"0意味著2"字段的解碼
2．11 比較謂詞
2．12 溢出檢測(cè)
2．13 加、減、乘的特征碼結(jié)果
2．14 循環(huán)移位
2．15 雙字長(zhǎng)加、減法
2．16 雙字長(zhǎng)移位

.2．17 多字節(jié)加、減、絕對(duì)值
2．18 doz、max、min函數(shù)
2．19 交換寄存器
2．20 兩個(gè)或更多值之間的交換
第3章 2的冪邊界
3．1 上舍入、下舍入到已知的2的冪的倍數(shù)
3．2 上舍入、下舍入到下一個(gè)2的冪
3．3 檢測(cè)2的冪的邊界跨越
第4章 算術(shù)邊界
4．1 整數(shù)的邊界檢測(cè)
4．2 通過加和減傳播邊界
4．3 邏輯操作的邊界傳播
第5章 位計(jì)數(shù)
5．1 1位計(jì)數(shù)
5．2 奇偶性
5．3 前導(dǎo)0計(jì)數(shù)
5．4 后綴0計(jì)數(shù)
第6章 字搜索
6．1 尋找第一個(gè)0字節(jié)
6．2 尋找第一個(gè)給定長(zhǎng)度的1位串
第7章 位和字節(jié)的重排列
7．1 位和字節(jié)的反轉(zhuǎn)
7．2 混洗位
7．3 轉(zhuǎn)置位矩陣
7．4 壓縮或廣義提取
7．5 一般置換，分羊操作
7．6 重排列和索引變換
第8章 乘法
8．1 多字乘法
8．2 64位積的高階位部分
8．3 無符號(hào)積高階位與帶符號(hào)積高階位間的轉(zhuǎn)換
8．4 常量乘法
第9章 整數(shù)除法
9．1 預(yù)備知識(shí)
9．2 多字除法
9．3 從帶符號(hào)除法到無符號(hào)短除法
9．4 無符號(hào)長(zhǎng)除法
第10章 整數(shù)常量除法
10．1 除以一個(gè)2的已知冪的帶符號(hào)除法
10．2 除以一個(gè)2的已知冪的除法的帶符號(hào)余數(shù)
10．3 非2的冪的帶符號(hào)除法和余數(shù)
10．4 除數(shù)≥2的帶符號(hào)除法
10．5 除數(shù)≤-2的帶符號(hào)除法
10．6 并入編譯器
10．7 其他主題
10．8 無符號(hào)除法
10．9 除數(shù)≥1的無符號(hào)除法
10．10 并入編譯器(無符號(hào))
10．11 其他論題(無符號(hào))
10．12 模除法和地板除法的適用性問題
10．13 類似的方法
10．14 魔術(shù)數(shù)示例
10．15 除以常數(shù)的精確除法
10．16 除以常數(shù)的除法的零余數(shù)檢測(cè)
第11章 初等函數(shù)
11．1 整數(shù)平方根
11．2 整數(shù)的立方根
11．3 整數(shù)求冪
11．4 整數(shù)對(duì)數(shù)
第12章 數(shù)制中的特殊底
12．1 以-2為底
12．2 以-1+i為底
12．3 其他底
12．4 最有效的底是什么
第13章 Gray碼
13．1 Gray碼
13．2 遞增Gray碼整數(shù)
13．3 負(fù)二進(jìn)制Gray碼
13．4 簡(jiǎn)史及應(yīng)用
第14章 Hilbert曲線
14．1 生成Hilbert曲線的遞歸算法
14．2 從Hilbert曲線的路長(zhǎng)求坐標(biāo)
14．3 Hilbert曲線上坐標(biāo)到路長(zhǎng)的轉(zhuǎn)換
14．4 遞增Hilbert曲線上點(diǎn)的坐標(biāo)
14．5 非遞歸生成算法
14．6 其他空間填充曲線
14．7 應(yīng)用
第15章 浮點(diǎn)
15．1 IEEE格式
15．2 利用整數(shù)操作進(jìn)行浮點(diǎn)數(shù)比較
15．3 前導(dǎo)數(shù)字分布
15．4 各種各樣的值的列表
第16章 素?cái)?shù)公式
16．1 介紹
16．2 Willans公式
16．3 Wormell公式
16．4 求其他比較麻煩的函數(shù)的公式
附錄A 四位計(jì)算機(jī)的算術(shù)表
附錄B 牛頓方法
參考文獻(xiàn)
索引