Tutorial :The Art of Computer Programming, Vol 4, Fascicle 2 typo?


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.


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.


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


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

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Next Post »