###

Question:

At the bottom of page 5 is the phrase "changes *k* to *k* âŠ• (1^{j+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.

###

Solution:1

This can be resolved by using the convention that (...)_{2} represents a bitwise representation. (1^{j+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 = (g01

^{a}10^{b})_{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 âŠ•(1^{j+1})_{2} is equated with k âŠ• (2^{j+1} - 1) implying that (1^{j+1})_{2} = (2^{j+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:

(1^{4})_{2} = (1111)_{2} = (2^{4} - 1)

Hope that helps.

###

Solution:2

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.

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

EmoticonEmoticon