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.