计算机编程的艺术,第 4 卷,分册 2 拼写错误?

发布于 07-14 11:01 字数 191 浏览 16 评论 0原文

第 5 页的底部是短语“将 k 更改为 k ⊕ (1j+1)<子>2”。 即使是二进制,1 的任意次幂不是也都是 1 吗? 我想这一定是一个错字。 我向 Knuth 博士发送了一封电子邮件报告此事,但预计几个月后才能收到回复。 与此同时,我正在尝试弄清楚这应该是什么。

At the bottom of page 5 is the phrase "changes k to k ⊕ (1j+1)2". Isn't 1 to any power still 1 even in binary? I'm thinking this must be a typo. I sent an email to Dr. Knuth to report this, but I don't expect to hear back for months. In the meantime, I'm trying to figure out what this is supposed to be.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

肩上的翅膀2024-07-21 11:01:01

这可以通过使用 (...)2 表示按位表示的约定来解决。 (1j+1)2 则仅包含 j+1 个,而不是指求幂。 您可以在 TAOCP 第 4 卷分册 1 第 8 页中更明确地解释此约定,例如:

如果 x 几乎是任何非零 2-adic
整数,我们可以将其位写入
表格

x =
(g01a10b)2

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

[我已用 g 替换了符号 alpha 以解决编码问题]

回到您的原始查询;
k ⊕(1j+1)2 等于 k ​​⊕ (2j+1 - 1)
暗示 (1j+1)2 = (2j+1 - 1):这成立,因为左侧是有效位为 j+1(连续)位的整数; 右边是求幂。 例如,j =3:

(14)2 = (1111)2 = (24 - 1)

希望有帮助。

This can be resolved by using the convention that (...)2 represents a bitwise representation. (1j+1)2 then consists solely of j+1 ones, rather than referring to an exponentiation. You can see this convention explained more explicitly in TAOCP Volume 4 Fascicle 1 at page 8, for example:

If x is almost any nonzero 2-adic
integer, we can write its bits in the
form

x =
(g01a10b)2

in other words, x consists of some
arbitrary (but infinite) binary string
g, followed by a 0, which is followed
by a+1 ones and followed by b zeros,
for some a >= 0 and b >= 0.

[I have substituted the symbol alpha by g to save encoding problems]

Going back to your original query;
k ⊕(1j+1)2 is equated with k ⊕ (2j+1 - 1)
implying that (1j+1)2 = (2j+1 - 1): this holds because the left-hand side is the integer whose significant bits are j+1 (contiguous) ones; the right-hand side is an exponentiation. For example, with j =3:

(14)2 = (1111)2 = (24 - 1)

Hope that helps.

北方的巷2024-07-21 11:01:01

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

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

您报告的拼写错误不存在。 如果确实是拼写错误,您可能有资格获得高德纳本人的现金奖励。

A list of known typos can be found on the errata page:

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

Your reported typo is not there. If it really is a typo, you might be eligible for a cash reward from Knuth himself.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文