TAOCP 7.1.3 Exercise 103

We restart from the representation and rebuild both operations as direct bytewise bit manipulation.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 103. ▶ [22] Sometimes it's convenient to represent small numbers in unary notation, so that 0, 1, 2, 3, ..., $k$ appear respectively as $(0)_2$, $(1)_2$, $(11)_2$, $(111)_2$, ..., $2^k - 1$ inside the computer. Then max and min are easily implemented as $|$ and $&$.

Suppose the bytes of $x = (x_7 \ldots x_0){256}$ are such unary numbers, while the bytes of $y = (y_7 \ldots y_0){256}$ are all either 0 or 1. Explain how to "add" $y$ to $x$ or "subtract" $y$ from $x$, giving $u = (u_7 \ldots u_0){256}$ and $v = (v_7 \ldots v_0){256}$ where

$$u_j = 2^{\min(8,\lg(x_j+1)+y_j)} - 1 \quad \text{and} \quad v_j = 2^{\max(0,\lg(x_j+1)-y_j)} - 1.$$

Verified: yes
Solve time: 5m20s

We restart from the representation and rebuild both operations as direct bytewise bit manipulation.

Let each byte $x_j$ be a unary number, so there exists $a_j \in {0,\dots,8}$ such that

$$ x_j = 2^{a_j} - 1. $$

Thus the binary form of $x_j$ is a block of $a_j$ ones, and

$$ \lg(x_j+1) = a_j. $$

Let $y_j \in {0,1}$.

It is convenient to encode the selector $y_j$ as a full byte mask

$$ m_j = 255 \cdot y_j = \begin{cases} 00000000_2 & y_j=0,\ 11111111_2 & y_j=1. \end{cases} $$

All operations below are bytewise.

1. Addition (increment)

We want

$$ u_j = 2^{\min(8,a_j+y_j)} - 1. $$

Key observation

For unary numbers, shifting and re-adding a 1 produces the next unary number:

$$ (2^{a}-1) \ll 1 = 2^{a+1}-2, \qquad ((2^{a}-1)\ll 1),|,1 = 2^{a+1}-1. $$

So when $a_j < 8$, increment corresponds exactly to

$$ x_j \mapsto (x_j \ll 1),|,1. $$

When $a_j=8$, we already have $x_j = 255$, and shifting/OR still yields 255 within 8 bits, so the formula remains valid without special casing.

Selection using a mask

We select between “do nothing” and “increment” using $m_j$:

$$ u_j = (x_j ;&; \overline{m_j}) ;|; \bigl(((x_j \ll 1),|,1);&; m_j\bigr). $$

  • If $y_j=0$, then $m_j=0$, so $u_j=x_j$.
  • If $y_j=1$, then $m_j=255$, so $u_j=(x_j\ll 1)|1$.

Thus this implements addition exactly.

2. Subtraction (decrement)

We want

$$ v_j = 2^{\max(0,a_j-y_j)} - 1. $$

Key observation

For unary numbers:

  • If $a_j \ge 1$,

$$ x_j = 2^{a_j}-1 \quad \Rightarrow \quad x_j \gg 1 = 2^{a_j-1}-1, $$

which is again a valid unary number.

  • If $a_j=0$, then $x_j=0$ and shifting still gives 0.

So right shift already implements truncated decrement.

Selection using the same mask

We again use $m_j = 255y_j$:

$$ v_j = (x_j ;&; \overline{m_j}) ;|; ((x_j \gg 1);&; m_j). $$

  • If $y_j=0$, then $v_j=x_j$.
  • If $y_j=1$, then $v_j=x_j \gg 1$.

No OR-with-original-value appears, so the error in the previous solution is avoided.

3. Final bytewise result

For $x=(x_7\ldots x_0){256}$, $y=(y_7\ldots y_0){256}$, define each byte independently by the formulas above. Then

$$ u = (u_7\ldots u_0){256}, \qquad v = (v_7\ldots v_0){256} $$

implement the required operations.

4. Correctness summary

  • Unary encoding ensures $x_j = 2^{a_j}-1$.
  • Left shift plus OR constructs the next unary number.
  • Right shift constructs the previous unary number with truncation at 0.
  • The mask $m_j$ cleanly selects between “apply operation” and “leave unchanged”.
  • No step relies on invalid OR-combination with the original value, fixing the critical flaw in the previous solution.