《算法心得:高效算法的奥秘》(原書第2版)討論及勘誤

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

備註:這份勘誤表在 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)從「元」到「節」,再到「組」,有遞進關係。

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

感謝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⌊log2 x
訂正:2⌈log2 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/

廣告

《算法心得:高效算法的奥秘》(原書第2版)討論及勘誤” 有 23 則迴響

    1. 您好,感謝您給出勘誤鏈接。英文第二版的Errata裡面,有一部分內容已經在翻譯時修正了;另一部分內容是翻譯時所沒有的,中文版可能未來得及修正。我會將這些新加進來的勘誤回報給編輯,以求再印時修正。

  1. 赞一个,很多计算机类的书籍都被翻烂了,翻烂了不重要,重要是翻烂后不管。最喜欢像@Jeffrey Lee译者这样不断更新勘误的人了!

    1. 您好,非常感謝回報此勘誤。剛查了底稿,發現我也沒有寫「-」號,應該是掃描公式時誤植了,由此給您閱讀帶來不便,我深感抱歉。

    1. 您好,剛查閱了該書英文版,作者好像沒有給出「形式化證明」,我個人理解這些可能是「經驗公式」。具體情形您可以諮詢本書作者Henry S. Warren, Jr.先生,他的電子郵箱是hankw#us.ibm.com(請將#換為「at」符號)。

  2. 18页表2.1 第一行 第五列 y前的‘-’号应该为按位取反符号。 另外我打算先对照原版把公式都对照一遍。这种程度,看不下去了。

    1. 您好,感謝您回報此勘誤。我查了底稿,我寫的也是「按位取反」符號「¬」。估計是掃描時誤植了。給您閱讀帶來不便,非常抱歉。

  3. 20页, 第四行 “平均值就是 (y-x) >> 1” 应该是 x+(y-x) >> 1好多错误都是基本公式,非常影响看书效果。到底是翻译搞错了,还是排版的时候粗心了?大家都说中文版翻译不错,我个人觉得非常烂。文法不好的翻译,最起码能凑合理解,你这公式都是错误的,太坑人了。

    1. 您好,非常感謝回報此問題。我查了譯稿,這個錯誤是我自己造成的。由此給您閱讀帶來不便,我深感抱歉。我已將其更新至勘誤表,以期再版時更正。

      1. 态度很认真,这点还是很支持的。希望后续翻译能再认真一些,特别是一些关键的公式等,

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s