《算法心得：高效算法的奥秘》（原書第2版）討論及勘誤

2014-03-06讀書寫字Jeffrey Lee

請各位讀者將涉及本書內容的勘誤、意見及建議評論於此，以便集中瀏覽，謝謝！

備註：這份勘誤表在 Github 上面也存有一份，參見 https://github.com/jeffreybaoshenlee/hacker-delight-2-errata/issues/1

更新記錄：

2014年3月13日01:09添加說明
2014年3月13日23:27添加勘誤條目
2014年3月20日20:40添加說明
2014年3月29日23:12添加勘誤
2014年4月19日00:14添加勘誤
2014年4月21日18:26添加勘誤
2014年5月4日23:38添加勘誤
2014年5月5日00:13添加勘誤
2014年6月8日01:13略微修改勘誤表
2014年6月8日01:13根據「英文第二版第二刷」之勘誤表，訂正中文版裡的相關內容
2014年6月10日20:58更新勘誤表（一）裡面其中一條勘誤之回報者
2015年4月6日添加勘誤
2017年3月7日添加勘誤
2017年3月9日添加勘誤
2017年10月18日更新勘誤
2018年3月10日更新勘誤
2018年7月25日添加 Github 網址

對bit、byte、word三詞譯法的說明

bit、byte、word這三個詞彙譯法較多，實難統一。在不太涉及算法的文章裡，我和大家一樣，也習慣譯為：「位」、「字節」、「字」；但在涉及算法的正式出版物裡，為求謹慎，幾經思量，還是選了「位元」、「字節」、「字組」這套譯法，萬望大家理解。

各譯法之對比，請看byvoid同學 https://www.byvoid.com/blog/region-phrases-comparison-byte 一文。文中倒數第二段所說的這句話我比較贊同，抄錄在這裡供大家參考：
「從翻譯角度來說，我認爲三個概念中『位元』『字節』『字組』分別是對『bit』『byte』和『word』較好的翻譯，因爲首先這三個詞都是雙字詞，符合現代漢語的造詞習慣，其次還能避免相互之間或與其他概念的混淆，因此推崇這三者。」

除了上述兩個原因外，我再補充兩點：（1）三詞均為「偏正構詞法」，形式一致；（2）從「元」到「節」，再到「組」，有遞進關係。

原作者對英文第二版第二次印刷所做之勘誤：

http://www.hackersdelight.org/errata2_2.pdf

感謝brownianwalker同學提供鏈接。

勘誤表（一）

位置：第11頁，2.1節，公式 x & (x-1) 上方括號內的示例數據
原文：01011110 -> 01010000
訂正：01011000 -> 01010000
錯誤原因：原書無誤，譯文有誤
回報者：南唐古韵；Yubin Yang；N!

位置：第11頁，2.1節，第5段，第1行
原文：下面的公式可以將字組尾部的1都變成0，如果尾部沒有1，則x不變
訂正：下面的公式可以將字組最右側及其左方連續出現的1都變成0，若最右側位元是0，則x不變
錯誤原因：原有譯法說得不夠透徹，重新翻譯
回報者：hebin20130504

位置：第11頁，2.1節，第7段，第1行
原文：以下公式可以將字組尾部的0都變成1，如果尾部沒有0，則x不變
訂正：以下公式可以將字組最右側及其左方連續出現的0都變成1，若最右側位元是1，則x不變
錯誤原因：原有譯法說得不夠透徹，重新翻譯
回報者：愛飛翔

位置：第13頁，2.1.1小節，第10行，第2個「=」右側
原文：-¬x & ((x+1)-1)
訂正：¬x & ((x+1)-1)
錯誤原因：公式排印錯誤
回報者：hucm90

位置：第13頁，2.1.2小節
原文：有一種簡單的辦法可以判斷出某個函數是否能通過一系列加法、減法、按位和、按位與及按位取反實現出來
訂正：有一種簡單的辦法可以判斷出某個函數是否能通過一系列加法、減法、按位和、按位或及按位取反實現出來
錯誤原因：原書無誤，譯文有誤
回報者：ご花未眠

位置：第18頁，2.3節，表2.1，第1行，第5列
原文：x & -y
訂正：x & ¬y
錯誤原因：公式排印錯誤
回報者：hucm90

位置：第19頁，2.4節
原文：((x>>30)|1)*x
訂正：((x>>31)|1)*x
錯誤原因：原書有誤，譯文未改正。
測試代碼參見：https://ideone.com/YmBno5
回報者：陳昱

位置：第20頁，2.5節，第2段，第2行
原文：(y-x)>>1
訂正：x+((y-x)>>1)
錯誤原因：原書無誤，譯文有誤。
備註：此處的 >> 表示無符號右移，其上方應有字母 u 。
回報者：lee

位置：第29頁，2.13節
原文：

-16<=x+y+c<=1

訂正：

-16<=x+y+c<=-1

錯誤原因：原書無誤，譯文有誤。
回報者：wishlily

位置：第57頁，3.2節，clp2(x)函數的定義
原文：2^{⌊log₂ x⌋}
訂正：2^{⌈log₂ x⌉}
錯誤原因：印刷錯誤。
回報者：wishlily

勘誤表（二）

本書作者曾經公佈了針對「英文第二版第二刷」的勘誤，小愛據此將中文版裡的相關錯誤訂正並彙總如下。

位置：47頁，第5段，第4行，2.20.2小節
原文：6個週期
改文：5個週期
回報者：Lawrence Ryan

位置：59頁，第3段，第2行，3.3.2小節
原文：x>=2^31
改文：x>2^31
備註：^表示冪，印刷時無需印出該字符，而應該把它後面的指數以上標形式印出
回報者：Lawrence Ryan

位置：69頁，第4段，第3行，4.3節
原文：前兩個不等式
改文：前三個不等式
回報者：Lawrence Ryan

位置：80頁，第4段末尾，5.1.1小節
原文：（「（實際上，……）」的後面缺一句話）
改文：計算時，需要把圖5.2的第三行代碼改為x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);，而且最後一行的3F也必須改為7F。
回報者：Lawrence Ryan

位置：81頁，第2段，第2句，5.1.2小節
原文：另一個數就是種群計數較大的那個
改文：另一個數就是種群計數較大的那個（也有可能表明兩個數的種群計數相同）
回報者：Lawrence Ryan

位置：91頁，第4段之後的第1行代碼，5.3節
原文：static char table[256] = {0,1,2,2,3,3,3,3,4,4,...,8);
改文：static char table[256] = {0,1,2,2,3,3,3,3,4,4,...,8};
備註：最後的右花括號誤寫為右小括號
回報者：Lawrence Ryan

位置：92頁，第2段，第1行，5.3節
原文：5 + …
改文：6 + …
回報者：Lawrence Ryan

位置：92頁，第4段，第3行，5.3節
原文：需要11條指令
改文：需要12條指令
回報者：Lawrence Ryan

位置：96頁，bitsize函數公式的第6行，5.3.3小節
原文：-2^30 + 1
改文：-2^30 – 1
備註：^表示冪，印刷時無需印出該字符，而是應該把它後面的指數以上標形式印出
回報者：Lawrence Ryan

位置：103頁，倒數第2段，第4行，5.4.1小節
原文：log2(Λ)+1
改文：⌊log2(Λ)⌋+1
備註：log2中的2應該以小字的形式印在log右下方
回報者：Lawrence Ryan

位置：166頁，圖9.1倒數第5行代碼，9.2節
原文：i < n
改文：i < n-1
回報者：HSW

位置：166頁，圖9.1倒數第3行與倒數第4行代碼之間，9.2節
原文：（缺一行代碼）
改文：r[n-1] = un[n-1] >> s;
備註：該行代碼的縮進，與修改之前倒數第5行的for語句處在同一級別
回報者：HSW

位置：200頁，倒數第2段，第5行，10.8.2小節
原文：邏輯右移3位
改文：邏輯右移兩位
回報者：Paolo Bonzini

位置：210頁，圖10.4，函數體前兩行代碼，10.15節
原文：
nc = (nmax + 1//d)*d – 1
nbits = len(log(nmax,2)) +1
改文：
nc = ((nmax + 1)//d)*d – 1
nbits = len(bin(nmax)) – 2
回報者：Colin Bartlett

位置：354頁，第3段，第2行，參考答案2.2
原文：x是不是0
改文：n是不是0
回報者：Lawrence Ryan

位置：357頁，倒數第1段，第2行，參考答案2.11
原文：c(n)
改文：cn
備註：n應該是下標形式
回報者：Lawrence Ryan

位置：362頁，倒數第11行，參考答案3.2
原文：如果一個數是10的奇數倍，那麼它必然是2的奇數倍
改文：當且僅當一個數既是10的倍數，又是2的奇數倍時，它纔會是10的奇數倍
回報者：Lawrence Ryan

位置：362頁，倒數第7行，參考答案3.2
原文：if (r > 5 | (r == 5 && (y & 2) != 0)
改文：if (r > 5 || (r == 5 && (y & 2) != 0))
回報者：Lawrence Ryan

位置：362頁，倒數第2行，參考答案3.2
原文：if (r == 0 & (y & 2) != 0)
改文：if (r == 0 && (y & 2) != 0)
回報者：Lawrence Ryan

位置：363頁，倒數第9行，參考答案4.2
原文：nlz(c & d)
改文：nlz(b & d)
回報者：Lawrence Ryan

此表格亦不定期地更新到
http://book.douban.com/subject/25837031/discussion/57548491/
http://club.jd.com/bbsDetail/11417658_27502095-ab93-42b8-8898-5c9384d3ab73_1.html
http://club.jd.com/bbsDetail/11417658_3ce14771-935c-4d42-b5f7-d81aa2a93c65_1.html
http://club.jd.com/bbsDetail/11417658_b77b6c0e-04de-4b9e-af71-796ac9936e3d_1.html
等網頁之中。

豆瓣信息頁面：
http://book.douban.com/subject/25837031/
china-pub信息頁面：
http://product.china-pub.com/3769521
卓越亞馬遜信息頁面：
http://www.amazon.cn/mn/detailApp/ref=asc_df_B00IRNTOQI908106/?asin=B00IRNTOQI
當當網信息頁面：
http://product.dangdang.com/23434235.html
京東信息頁面：
http://item.jd.com/11417658.html

英文原版书相關信息：
名稱：《Hacker’s Delight》(2nd Edition)
作者：Henry S. Warren, Jr.
出版社：Addison-Wesley Professional

Amazon信息頁面：http://www.amazon.com/Hackers-Delight-Edition-Henry-Warren/dp/0321842685/ref=sr_1_1
豆瓣信息頁面：http://book.douban.com/subject/10756419/