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.
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.
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 = (23 - 1)
Hope that helps.