+ * negative powers of 2.
+ *
+ * Here's the relevant theory. The important observation is that
+ * %$2^i = 2^{i+1} - 2^i$%, and hence
+ *
+ * * %$\sum_{a\le i<b} 2^i = 2^b - 2^a$%, and
+ *
+ * * %$2^c - 2^{b+1} + 2^b - 2^a = 2^c - 2^b - 2^a$%.
+ *
+ * The first of these gives us a way of combining a run of several one
+ * bits, and the second gives us a way of handling a single-bit
+ * interruption in such a run.
+ *
+ * We start with a number %$p = \sum_{0\le i<n} p_i 2^i$%, and scan
+ * right-to-left using a simple state-machine keeping (approximate) track
+ * of the two previous bits. The @Z@ states denote that we're in a string
+ * of zeros; @Z1@ means that we just saw a 1 bit after a sequence of zeros.
+ * Similarly, the @X@ states denote that we're in a string of ones; and
+ * @X0@ means that we just saw a zero bit after a sequence of ones. The
+ * state machine lets us delay decisions about what to do when we've seen a
+ * change to the status quo (a one after a run of zeros, or vice-versa)
+ * until we've seen the next bit, so we can tell whether this is an
+ * isolated bit or the start of a new sequence.
+ *
+ * More formally: we define two functions %$Z^b_i$% and %$X^b_i$% as
+ * follows.
+ *
+ * * %$Z^0_i(S, 0) = S$%
+ * * %$Z^0_i(S, n) = Z^0_{i+1}(S, n)$%
+ * * %$Z^0_i(S, n + 2^i) = Z^1_{i+1}(S, n)$%
+ * * %$Z^1_i(S, n) = Z^0_{i+1}(S \cup \{ 2^{i-1} \}, n)$%
+ * * %$Z^1_i(S, n + 2^i) = X^1_{i+1}(S \cup \{ -2^{i-1} \}, n)$%
+ * * %$X^0_i(S, n) = Z^0_{i+1}(S, \{ 2^{i-1} \})$%
+ * * %$X^0_i(S, n + 2^i) = X^1_{i+1}(S \cup \{ -2^{i-1} \}, n)$%
+ * * %$X^1_i(S, n) = X^0_{i+1}(S, n)$%
+ * * %$X^1_i(S, n + 2^i) = X^1_{i+1}(S, n)$%
+ *
+ * The reader may verify (by induction on %$n$%) that the following
+ * properties hold.
+ *
+ * * %$Z^0_0(\emptyset, n)$% is well-defined for all %$n \ge 0$%
+ * * %$\sum Z^b_i(S, n) = \sum S + n + b 2^{i-1}$%
+ * * %$\sum X^b_i(S, n) = \sum S + n + (b + 1) 2^{i-1}$%
+ *
+ * From these, of course, we can deduce %$\sum Z^0_0(\emptyset, n) = n$%.
+ *
+ * We apply the above recurrence to build a simple instruction sequence for
+ * adding an appropriate multiple of %$d$% to a given number. Suppose that
+ * %$2^{w(N-1)} \le 2^{n-1} \le p < 2^n \le 2^{wN}$%. The machine which
+ * interprets these instructions does so in the context of a
+ * single-precision multiplicand @z@ and a pointer @v@ to the
+ * %%\emph{most}%% significant word of an %$N + 1$%-word integer, and the
+ * instruction sequence should add %$z d$% to this integer.
+ *
+ * The available instructions are named @MPRI_{ADD,SUB}{,LSL}@; they add
+ * (or subtract) %$z$% (shifted left by some amount, in the @LSL@ variants)
+ * to some word earlier than @v@. The relevant quantities are encoded in
+ * the instruction's immediate operands.