Искусство программирования, том 4, Fascicle 2 typo?

Question

В нижней части страницы 5 является фраза "изменяет к к к ⊕ (1 ^{J +1}) ". Разве не 1 до какой-либо мощности еще 1 даже в двоичном формате? Я думаю, это должно быть опечатка. Я отправил электронное письмо к доктору Кнуту, чтобы сообщить об этом, но я не ожидаю услышать месяцы. Тем временем я пытаюсь понять, что это должно быть.

Answer 1

Это можно решить, используя соглашение, которое (...) представляет поразрядное представление. (1 ^{j + 1}) тогда состоит только из j + 1 единиц, вместо того, чтобы ссылаться на возведение в степень. Вы можете увидеть это соглашение объяснено более явно в TAOCP Том 4 пучках 1 на странице 8, например:

Если х почти любой ненулевой 2-адическая целое, то можно записать свои биты в форме

х = (G01 ^б)

другими словами, х состоит из некоторого произвольной (но бесконечной) бинарного Strin г г, с последующим 0, за которым следует по + 1 из них, и с последующим б нулей, для некоторого а> = 0 и Ь> = 0.

[я заменил символ альфа g для сохранения проблем с кодированием]

Возвращаясь к исходному запросу; к ⊕ (1 ^{J + 1}) приравнивается с к ⊕ (2 ^{J + 1} - 1) подразумевая, что (1 ^{J + 1}) = (2 ^{J + 1} - 1): это выполняется потому, что левая часть является целым числом, значащие биты которого j + 1 (смежные); правая часть - это возведение в степень. Например, при J = 3:

(1) = (1111) 2 = (2 - 1)

Надежда, что помогает.

Answer 2

список известных опечаток можно найти на странице опечаток:

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

Ваш сообщил опечатка нет. Если это действительно опечатка, вы можете получить денежное вознаграждение от самого Кнута.