1
$\begingroup$

The title was difficult to formulate (I am open to suggestions). Two things bug me about this:

  1. "is almost any" is imprecise, which goes against Volume 1's statement on definiteness.
  2. When he writes, "in other words", this means Prof. Knuth explained it to me in two ways and I still do not understand it.

What is going on here in Plain English?


If $x$ is almost any nonzero 2-adic integer, we can write its bits in the form $$x = (\alpha01^a10^b)_2 $$

in other words, $x$ consists of some arbitrary (but infinite) binary string of $\alpha$, followed by a $0$, which is followed by $a+1$ ones, and followed by $b$ zeros, for some $a \geq 0$ and $b \geq 0$. (The exceptions occur when $x = -2^b$; then $a = \infty $)

Consequently

$$ \bar{x} = (\bar\alpha10^a01^b)_2 $$

$$ x-1 = (\alpha01^a01^b)_2 $$

$$ -x = (\bar\alpha10^a10^b)_2 $$

and we can see that $\bar{x} +1 = -x = \overline{x-1}$, ...

With two operations we can therefore compute relatives of $x$ in several useful ways:

  • $x \mathbin{\&} (x-1) = (\alpha01^a00^b)_2$
  • $x\mathbin{\&} -x = (0^\infty00^a10^b)_2$
  • $x \mathbin{|} -x = (1^\infty11^a10^b)_2$
  • $x \oplus -x = (1^\infty11^a00^b)_2$
  • $x \mathbin{|} (x-1) = (\alpha 01^a11^b)_2$
  • $x \oplus (x-1) = (0^\infty00^a11^b)_2$
  • $\bar{x} \mathbin{\&} (x-1) = (0^\infty00^a01^b)_2$
  • ...
  • $((x|(x-1))+1) \mathbin{\&} x = (\alpha 00^a00^b)_2$
  1. Knuth, Donald. The Art of Computer Programming. Volume 4, Fascicle 1. p. 8.
$\endgroup$
  • 1
    $\begingroup$ I think this is really a question about pure mathematics that belongs on Mathematics. Although it's come from Knuth, there doesn't seem to be any direct computational content and I don't think most computer scientists know anything about $p$-adic integers. $\endgroup$ – David Richerby Nov 5 '18 at 10:54
  • $\begingroup$ @DavidRicherby, here the relation to p-adic numbers is only tangential. The question is basically about two's complement. $\endgroup$ – Karolis Juodelė Nov 5 '18 at 11:04
2
$\begingroup$

Addressing first the explicitly asked questions:

Two things bug me about this: 1. "is almost any" is imprecise,

The meaning of “almost any” here is given in the next sentence, in the same paragraph: the paragraph goes as “If $x$ is almost any nonzero 2-adic integer, [...]. (The exceptions occur when $x = -2^b$; [...].)” So “almost any” here means “any, except for the specific exceptions stated”.

which goes against Volume 1's statement on definiteness.

Aside: Although definiteness is always good and I'm sure the author agrees, note that the statement in Volume 1 is specifically in the context of the definition of an algorithm, not about writing in general. :-) Computers need everything to be spelled out for them; humans can be more robust.

  1. When he writes, "in other words", this means Prof. Knuth explained it to me in two ways and I still do not understand it.

Yes: in the sentence “[...] we can write its bits in the form $x = (\alpha01^a10^b)_2$; in other words, $x$ consists of some [...]”, the form of $x$ is described in two ways: (1) in notation, and (2) in words.


Longer explanation with context:

What is a 2-adic integer?

Although some people (IMO incorrectly) describe The Art of Computer Programming as a reference book, in fact it is written to teach, so one cannot look up a random page or section and expect to understand it in isolation.

In this case, the “$2$-adic integers” mentioned here are first briefly described on page 2 of Fascicle 1 (page 134 when part of Volume 4A), where it is said:

Negative integers are to be thought of in this connection as infinite-precision numbers in two’s complement notation, having infinitely many $1$s at the left; for example, $−5$ is $(\dots1111011)_2$. Such infinite-precision numbers are a special case of 2-adic integers, which are discussed in exercise 4.1–31, and in fact the operators $\&$, $|$, $\oplus$ make perfect sense when they are applied to arbitrary 2-adic numbers.

This may be enough context for what is in the question here, but to understand this more completely, it would be best to look up (as mentioned) Exercise 31 of section 4.1 (Positional Number Systems), which is on page 213 of Volume 2. The exercise covers three-fourths of a page and is very instructive, but let me just quote part of it:

A generalization of two’s complement arithmetic, called “2-adic numbers,” was introduced by K. Hensel […] A 2-adic number may be regarded as a binary number $$u = (\dots u_3u_2u_1u_0.u_{−1}\dots u_{-n})_2,$$ whose representation extends infinitely far to the left of the binary point, but only finitely many places to the right. Addition, subtraction, and multiplication of 2-adic numbers are done according to the ordinary procedures of arithmetic, which can in principle be extended indefinitely to the left. For example, TODO change image to math

Here 7 appears as the ordinary binary integer seven, while −7 is its two’s complement (extending infinitely to the left); it is easy to verify that the ordinary procedure for addition of binary numbers will give $−7+ 7 = (\dots00000)_2 = 0$, when the procedure is continued indefinitely. The values of $\frac{1}{7}$ and $\frac{-1}{7}$ are the unique 2-adic numbers that, when formally multiplied by 7, give 1 and −1, respectively. The values of $\frac{7}{4}$ and $\frac{1}{10}$ are examples of 2-adic numbers that are not 2-adic “integers,” since they have nonzero bits to the right of the binary point. The two values of $\sqrt{-7}$, which are negatives of each other, are the only 2-adic numbers that, when formally squared, yield the value $(\dots111111111111001)_2$.

I hope this makes clear what is a 2-adic integer. (If that was too much, just focus on the $−5 = (\dots1111011)_2$ and $-7 = (\dots111111111111001)_2$ and $7 = (\dots000000000000111)_2$ examples.)

The first sentence

Now, with this background, the quoted sentence (that the question is about) will hopefully be clearer. It occurs on page 8 in a section titled “Working with the rightmost bits”, so that should also help orient your attention.

If you consider any 2-adic integer $x$ other than the stated exceptions ($0$ and $-2^b$), then the sentence says that it can be written in the form $x = (\alpha\color{blue}{0}1^a\color{#c00}{1}0^b)_2$. What this means is that looking from the right, the bits of $x$ (you may want to look at the examples above) consist of some (possibly empty) sequence of $0$s (“$0^b$”), to the left of which there is a $1$ (so “$\color{#c00}{1}0^b$”), to the left of which there's some (possibly empty) sequence of $1$s (so “$1^a\color{#c00}{1}0^b$”), to the left of which there is a $0$ (so “$\color{blue}{0}1^a\color{#c00}{1}0^b$”), to the left of which there is some infinite string of arbitrary $0$s and $1$s that we don't care about (so “$\alpha\color{blue}{0}1^a\color{#c00}{1}0^b$”).

In other words, if you consider the sequence of bits of $x$:

  • $b$ is the number of $0$s that it ends with, i.e. the sequence of $0$s after the last $\color{#c00}{1}$ in the sequence. ($b \ge 0$)
  • $a$ is the number of $1$s immediately to the left of that last $\color{#c00}{1}$, i.e. between “the last $\color{blue}{0}$ before the last $\color{#c00}{1}$” and “the last $\color{#c00}{1}$”. ($a \ge 0$)
  • $\alpha$ is the arbitrary sequence that comes before this, i.e. before “the last $\color{blue}{0}$ before the last $\color{#c00}{1}$”.

Examples

  • When $x = 1392 = (\dots000101\color{blue}{0}11\color{#c00}{1}0000)_2$, then $x$ can be written as $(\alpha\color{blue}{0}1^a\color{#c00}{1}0^b)_2$ with $\alpha = \dots000101$ and $a = 2$ and $b = 4$.

  • When $x = −5 = (\dots1111\color{blue}{0}1\color{#c00}{1})_2$, then $x$ can be written as $(\alpha\color{blue}{0}1^a\color{#c00}{1}0^b)_2$ with $\alpha = \dots1111$ and $a = 1$ and $b = 0$.

  • When $x = -7 = (\dots1111111111110\color{blue}{0}\color{#c00}{1})_2$, then $x$ can be written as $(\alpha\color{blue}{0}1^a\color{#c00}{1}0^b)_2$ with $\alpha = \dots1111111111110$ and $a = 0$ and $b = 0$.

  • When $x = 7 = (\dots00000000000\color{blue}{0}11\color{#c00}{1})_2$, then $x$ can be written as $(\alpha\color{blue}{0}1^a\color{#c00}{1}0^b)_2$ with $\alpha = \dots00000000000$ and $a = 2$ and $b = 0$.

The rest

This just gives the bit patterns of various functions of $x$, like $x-1$, $-x$, $\bar{x}$ (the bitwise complement of $x$; recall definition from page 3 earlier), $x \oplus (x-1)$, etc.

All of these are straightforward; e.g. if $x = (\alpha\color{blue}{0}1^a\color{#c00}{1}0^b)_2$ then when you subtract $1$ from it, the final $\color{#c00}{1}0^b$ becomes $\color{#c00}{0}1^b$ and the rest remains the same, so the result is $x - 1 = (\alpha\color{blue}{0}1^a\color{#c00}{0}1^b)_2$. (For example, think about what happens when you subtract $1$ from $1392 = (\dots000101\color{blue}{0}11\color{#c00}{1}0000)_2$ to get $1391 = (\dots000101\color{blue}{0}11\color{#c00}{0}1111)_2$ — and so on.)

I assume your main difficulty was in understanding the $x = (\alpha\color{blue}{0}1^a\color{#c00}{1}0^b)_2$ notation, so you should be able to work out these functions now.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

The pattern $x = (\alpha01^a10^b)_2$ is very easy to match. For example, the number $1=0^\infty1$ matches the pattern with $\alpha=0^\infty, a=b=0$. Try matching some other numbers yourself. The only thing this pattern asks for, is for the string "$01$" to appear somewhere in the sequence of bits. The only numbers to fail this condition are $0=0^\infty$ and $-2^b=1^\infty0^b$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.