算法心得：高效算法的奧秘

本書直觀明了地講述了計算機算術的更深層次的、更隱秘的技術，匯集了各種編輯的小技巧，包括常購的任務的小算法，2的冪邊界和邊界檢測、位和位元組的重排列、整數除法和常量除法、針對整數的基涵義，空間填充曲線、素數公式等。

基本介紹

• 書名：算法心得：高效算法的奧秘（原書第2版）
• 作者：（美）HenryS. Warren, Jr. 
• 原版名稱：Hacker's Delight （Second Edition) 
• 譯者：愛飛翔
• ISBN：9787111453567 
• 定價：89.00
• 出版社：機械工業出版社
• 出版時間：2014年3月

基本信息

書名：算法心得：高效算法的奧秘

作者: （美）Henry S. Warren, Jr.

出版社: 機械工業出版社

原作名: Hacker's Delight, 2nd Edition

譯者: 愛飛翔

出版年: 2014-3

定價: 89.00

ISBN: 9787111453567

作者簡介

Henry S. Warren, Jr.

計算機科學家，在IBM供職50餘年，經歷了IBM704時代、PowerPC時代及其後種種更迭。曾參與多個軍事指揮與控制系統工程，並且參加了由Jack Schwarz領銜的“SET語言”項目。自1973年起，Hank就職於IBM研發部，努力探索編譯器和計算機架構。當前正研究一種旨在每秒執行百億億次運算的超級計算機。Hank擁有紐約大學柯朗數學科學研究所計算機科學博士學位。

譯者簡介

愛飛翔

資深軟體開發工程師，擅長Web開發、移動開發和遊戲開發，有10餘年開發經驗，曾主導和參與了多個手機遊戲和手機軟體項目的開發，經驗十分豐富。他是手機軟體開發引擎AgileMobileEngine的創始人兼項目經理，同時也是CatEngine手機遊戲開發引擎的聯合創始人兼代碼維護員。他對極限編程、設計模式、重構、測試驅動開發、敏捷軟體開發等也有較深入的研究。業餘愛好文學和歷史，有一定的文學造詣。翻譯並出版了多本計算機著作。

目錄

譯者序

序（第1版序）

前言

第1章概述

1.1記法

1.2指令集與執行時間模型

1.3習題

第2章基礎知識

2.1操作最右邊的位元

2.1.1德摩根定律的推論

2.1.2從右至左的可計算性測試

2.1.3位操作的新式用法

2.2結合邏輯操作的加減運算

2.3邏輯與算術表達式中的不等式

2.4絕對值函式

2.5兩數平均值

2.6符號擴展

2.7用無符號右移模擬帶符號右移操作

2.8符號函式

2.9三值比較函式

2.10符號傳遞函式

2.11將值為0的位段解碼為2的n次方

2.12比較謂詞

2.12.1利用進位標誌求比較謂詞

2.12.2計算機如何設定比較謂詞

2.13溢出檢測

2.13.1帶符號的加減法

2.13.2計算機執行帶符號數的加減法時如何設定溢出標誌

2.13.3無符號數的加減法

2.13.4乘法

2.13.5除法

2.14加法、減法與乘法的特徵碼

2.15循環移位

2.16雙字長加減法

2.17雙字長移位

2.18多位元組加減法與求絕對值

2.19doz、max、min函式

2.20互換暫存器中的值

2.20.1交換暫存器中相應的位段

2.20.2交換同一暫存器內的兩個位段

2.20.3有條件的交換

2.21在兩個或兩個以上的值之間切換

2.22布爾函式分解公式

2.23實現16種二元布爾操作

2.24習題

第3章2的冪邊界

3.1將數值上調/下調為2的已知次冪的倍數

3.2調整到上一個/下一個2的冪

3.2.1向下捨入

3.2.2向上捨入

3.3判斷取值範圍是否跨越了2的冪邊界

3.4習題

第4章算術邊界

4.1檢測整數邊界

4.2通過加減法傳播邊界

4.3通過邏輯操作傳播邊界

4.4習題

第5章位計數

5.1統計值為“1”的位元數

5.1.1兩個字組種群計數的和與差

5.1.2比較兩個字組的種群計數

5.1.3統計數組中值為“1”的位元數

5.1.4套用

5.2奇偶性

5.2.1計算字組的奇偶性

5.2.2將表示奇偶性的位元添加到7位量中

5.2.3套用

5.3前導0計數

5.3.1浮點數算法

5.3.2比較兩個字組前導0的個數

5.3.3與對數函式的關係

5.3.4套用

5.4後綴0計數

5.5習題

第6章在字組中搜尋位串

6.1尋找首個值為0的位元組

6.1.10值位元組位置函式的

一些簡單推廣

6.1.2搜尋給定範圍內的值

6.2尋找首個給定長度的全1位串

6.3尋找最長全1位串

6.4尋找最短全1位串

6.5習題

第7章重排位元與位元組

7.1反轉位元與位元組

7.1.1位元反轉算法的推廣

7.1.2奇特的位元反轉算法

7.1.3遞增反轉後的整數

7.2亂序排列位元

7.3轉置位矩陣

7.4壓縮算法(廣義提取算法)

7.4.1用“插入”、“提取”指令實現壓縮操作

7.4.2向左壓縮

7.5展開算法(廣義插入算法)

7.6壓縮與展開操作的硬體算法

7.6.1壓縮

7.6.2展開

7.7通用置換算法及分羊操作

7.8重排與下標變換

7.9LRU算法

7.10習題

第8章乘法

8.1多字乘法

8.264位積的高權重部分

8.3無符號與帶符號的高權重積互化

8.4與常數相乘

8.5習題

第9章整數除法

9.1預備知識

9.2多字除法

9.3用帶符號除法計算無符號短除法

9.3.1用帶符號長除法計算無符號短除法

9.3.2用帶符號短除法計算無符號短除法

9.4無符號長除法

9.4.1用硬體實現移位並相減算法

9.4.2用短除法實現無符號長除法

9.5用長除法實現雙字除法

9.5.1無符號雙字除法

9.5.2帶符號雙字除法

9.6習題

第10章除數為常量的整數除法

10.1除數為2的已知次冪的帶符號除法

10.2求與2的已知次冪相除的帶符號餘數

10.3在除數不是2的冪時求帶符號除法及餘數

10.3.1除以3

10.3.2除以5

10.3.3除以7

10.4除數大於等於2的帶符號除法

10.4.1算法

10.4.2算法可行性證明

10.4.3證明乘積正確

10.5除數小於等於-2的帶符號除法

10.6將除法算法集成至編譯器中

10.7其他主題

10.7.1唯一性

10.7.2可生成最佳程式代碼的除數

10.8無符號除法

10.8.1除數為3的無符號除法

10.8.2除數為7的無符號除法

10.9除數大於等於1的無符號除法

10.9.1無符號版算法

10.9.2算法可行性證明

10.9.3證明無符號版算法的乘積正確

10.10將無符號除法算法集成至編譯器中

10.11與無符號除法相關的其他話題

10.11.1可生成最佳無符號除法代碼的除數

10.11.2帶符號乘法與無符號乘法互化

10.11.3更簡單的無符號除法生成算法

10.12餘數非負式除法與向下取整式除法的適用性

10.13類似算法

10.14神奇數字示例

10.15用Python語言編寫的簡單代碼

10.16除數為常量的精確除法

10.16.1用歐幾里得算法計算乘法逆元素

10.16.2用牛頓法計算乘法逆元素

10.16.3乘法逆元素示例

10.17檢測除以常數後是否餘0

10.17.1無符號除法

10.17.2除數大於等於2的帶符號除法

10.18不使用Multiply High指令的除法算法

10.18.1無符號除法

10.18.2帶符號除法

10.19合計各數位求餘數

10.19.1求無符號除法的餘數

10.19.2求帶符號除法的餘數

10.20用乘法及右移位求餘數

10.20.1求無符號除法的餘數

10.20.2求帶符號除法的餘數

10.21將普通除法化為精確除法

10.22計時測試

10.23用電路計算除數為3的除法

10.24習題

第11章初等函式

11.1整數平方根

11.1.1用牛頓法開平方

11.1.2二分查找

11.1.3硬體算法

11.2整數立方根

11.3求整數冪

11.3.1用n的二進制分解式計算xn

11.3.2用Fortran語言計算2n

11.4整數對數

11.4.1以2為底的整數對數

11.4.2以10為底的整數對數

11.5習題

第12章以特殊值為底的數制

12.1以-2為底的數制

12.2以-1+i為底的數制

12.3以其他數為底的數制

12.4最高效的底是什麼

12.5習題

第13章格雷碼

13.1簡介

13.2遞增格雷碼整數

13.3負二進制格雷碼

13.4格雷碼簡史及套用

13.5習題

第14章循環冗餘校驗

14.1簡介

14.2理論

14.3實現

14.3.1硬體實現

14.3.2軟體實現

14.4習題

第15章糾錯碼

15.1簡介

15.2漢明碼

15.2.1SECDED碼

15.2.2校驗位個數的最小值

15.2.3小結

15.3適用於32位信息的軟體SECDED算法

15.4廣義錯誤修正

15.4.1漢明距離

15.4.2編碼論的主要問題

15.4.3n維球面

15.5習題

第16章希爾伯特曲線

16.1生成希爾伯特曲線的遞歸算法

16.2根據希爾伯特曲線上從起點到某點的途經距離求其坐標

16.3根據希爾伯特曲線上的坐標求從起點到某點的途經距離

16.4遞增希爾伯特曲線上點的坐標

16.5非遞歸的曲線生成算法

16.6其他空間填充曲線

16.7套用

16.8習題

第17章浮點數

17.1IEEE格式

17.2整數與浮點數互化

17.3使用整數操作比較浮點數大小

17.4估算平方根倒數

17.5前導數位的分布

17.6雜項數值表

17.7習題

第18章素數公式

18.1簡介

18.2Willans公式

18.2.1Willans第二公式

18.2.2Willans第三公式

18.2.3Willans第四公式

18.3Wormell公式

18.4用公式來描述其他難解的函式

18.5習題

參考答案

附錄A4位計算機算術運算表

附錄B牛頓法

附錄C各種離散函式圖像

參考文獻