knuth - 计算机编程艺术，第 4 卷，分册 2 错字？

Question

在第 5 页的底部是短语“将k更改为k ⊕ (1 ^{j +1} ) ₂ ”。即使在二进制中，1 的任何幂都不是 1 吗？我想这一定是笔误。我向 Knuth 博士发送了一封电子邮件报告此事，但我预计几个月后不会收到回复。与此同时，我试图弄清楚这应该是什么。

Answer 1

这可以通过使用 (...) ₂表示按位表示的约定来解决。(1 ^j+1 ) ₂则仅由 j+1 个组成，而不是指代幂。您可以在第 8 页的 TAOCP 第 4 卷分册 1 中看到更明确的解释，例如：

如果 x 几乎是任何非零 2 进整数，我们可以将其位写成以下形式

x = (g01 ^a 10 ^b ) ₂

换句话说，x 由一些任意（但无限）的二进制字符串 g 组成，后跟一个 0，然后是 a+1 个 1，然后是 b 个零，对于某些 a >= 0 和 b >= 0。

[我已将符号 alpha 替换为 g 以节省编码问题]

回到原来的查询；k ⊕(1 ^j+1 ) ₂与 k ⊕ (2 ^j+1 - 1) 等价，这意味着 (1 ^j+1 ) ₂ = (2 ^j+1 - 1)：因为左边是有效位为 j+1（连续）的整数；右边是指数。例如，当 j =3：

(1 ⁴ ) ₂ = (1111) ₂ = (2 ⁴ - 1)

希望有帮助。

Answer 2

可以在勘误页面上找到已知拼写错误的列表：

http://www-cs-faculty.stanford.edu/~knuth/taocp.html

您报告的错字不存在。如果确实是错字，您可能有资格从 Knuth 本人那里获得现金奖励。