计算机编程的艺术,第 4 卷,分册 2 拼写错误?
第 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.
这可以通过使用 (...)2 表示按位表示的约定来解决。 (1j+1)2 则仅包含 j+1 个,而不是指求幂。 您可以在 TAOCP 第 4 卷分册 1 第 8 页中更明确地解释此约定,例如:
[我已用 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:
[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.