Искусство компьютерного программирования, том 4, опечатка 2 опечатка?

Question

Внизу страницы 5 есть фраза "меняет k на k ⊕ (1^j+1)₂". Разве 1 ​​в любой степени еще 1 даже в двоичном? Я думаю это опечатка. Я послал электронное письмо доктору Кнуту, чтобы сообщить об этом, но не ожидаю ответа в течение нескольких месяцев. А пока я пытаюсь понять, что это должно быть.

Answer 1

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

Если x - почти любое ненулевое 2-адическое целое число, мы можем записать его биты в виде

х = (g01^a10^b)₂

иными словами, x состоит из некоторой произвольной (но бесконечной) двоичной строки g, за которой следует 0, за которой следуют единицы + 1, за которыми следуют b нулей, для некоторых a >= 0 и b> = 0.

[Я заменил символ альфа на 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

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