TAOCP 7.1.3 Exercise 100

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 100. [25] Suppose $x = (x_{15} \ldots x_1 x_0){16}$ and $y = (y{15} \ldots y_1 y_0){16}$ are binary-coded decimal numbers, where $0 \le x_j$, $y_j < 10$ for each $j$. Explain how to compute their sum $u = (u{15} \ldots u_1 u_0){16}$ and difference $v = (v{15} \ldots v_1 v_0)_{16}$, where $0 \le u_j$, $v_j < 10$ and

$$(u_{15} \ldots u_1 u_0){10} = ((x{15} \ldots x_1 x_0){10} + (y{15} \ldots y_1 y_0){10}) \bmod 10^{16},$$ $$(v{15} \ldots v_1 v_0){10} = ((x{15} \ldots x_1 x_0){10} - (y{15} \ldots y_1 y_0)_{10}) \bmod 10^{16},$$

without bothering to do any radix conversion.

Verified: yes
Solve time: 4m44s

Let $x = (x_{15}\ldots x_0){16}$ and $y = (y{15}\ldots y_0)_{16}$, where each $x_j, y_j \in {0,\ldots,9}$. Let

$$ X = \sum_{j=0}^{15} x_j 10^j,\qquad Y = \sum_{j=0}^{15} y_j 10^j. $$

We work entirely in the 16-nibble word model (base $16$ storage), but interpret correctness in decimal modulo $10^{16}$.

1. Addition

Step 1: raw binary (hex-word) addition

Compute the ordinary integer sum of the 16-nibble words:

$$ s = x + y. $$

Write its base-16 expansion

$$ s = (s_{15}\ldots s_0)_{16}, $$

where now each $s_j \in {0,\ldots,15}$, since this is a genuine base-16 representation after all carries have been resolved.

Each $s_j$ satisfies

$$ s_j \equiv x_j + y_j + \text{carry from lower position} \pmod{16}. $$

Step 2: BCD correction constant

Define a correction word $c$ digitwise by

$$ c_j = \begin{cases} 6, & s_j \ge 10,\ 0, & s_j < 10. \end{cases} $$

Let

$$ c = (c_{15}\ldots c_0)_{16}, \qquad u = s + c. $$

We now prove that $u$ is a valid BCD word and represents $X+Y \bmod 10^{16}$.

Step 3: local correctness lemma

Fix a digit position $j$. Let $s_j$ be the current hex digit.

Case 1: $s_j \le 9$

Then $c_j = 0$, so no change is made at position $j$. The digit remains a valid BCD digit.

Case 2: $10 \le s_j \le 15$

Write

$$ s_j = u_j + 10,\qquad u_j \in {0,\ldots,5}. $$

Then $c_j = 6$, so at position $j$ we add

$$ s_j + 6 = u_j + 16. $$

In base 16 arithmetic this produces:

digit $u_j$ at position $j$,
a carry of $1$ into position $j+1$.

Hence the corrected digit becomes a valid BCD digit $u_j \in {0,\ldots,9}$, and the only effect on higher positions is a standard carry of $1$.

This is the key mechanism: adding $6$ converts an invalid digit $10$–$15$ into a valid decimal digit while converting the excess $+10$ into a carry of $+1$ in base 16.

Step 4: no interference between digits

The correction at position $j$ produces at most one carry into $j+1$. That carry is absorbed into the existing base-16 addition at position $j+1$. Since each position is treated uniformly and carries are always bounded by $1$, the process is identical to ordinary base-16 addition with an extra fixed per-digit perturbation.

Thus the transformation

$$ s \mapsto s + c $$

is a standard carry-propagating addition in base 16, so it preserves a well-defined integer value modulo $16^{16}$, hence also modulo $10^{16}$ once we identify digits as decimal digits.

Step 5: correctness of the decimal value

We show that $u$ represents $X+Y \bmod 10^{16}$.

Each digit position behaves as follows:

if no correction occurs, the digit is unchanged and valid in decimal;
if correction occurs, the identity

$$ s_j + 6 = (s_j - 10) + 16 $$

converts a base-10 overflow into a base-16 carry.

Therefore, after propagation, the resulting digits satisfy exactly the recurrence of decimal addition, since each overflow of $10$ is replaced by a carry of $1$, matching decimal arithmetic.

Hence

$$ (u_{15}\ldots u_0)_{10} = (X+Y) \bmod 10^{16}. $$

2. Subtraction

We construct $v = X - Y \bmod 10^{16}$ using 10’s complement.

Step 1: 10’s complement of $y$

Define digitwise complement:

$$ \bar{y}_j = 9 - y_j. $$

Then

$$ \bar{Y} = \sum_{j=0}^{15} \bar{y}_j 10^j = 10^{16} - 1 - Y. $$

Add 1:

$$ y^* = \bar{y} + 1, $$

$$ y^* = 10^{16} - Y. $$

This is a valid BCD word.

Step 2: reduce subtraction to addition

Compute

$$ t = x + y^*. $$

Apply the same BCD correction procedure as in the addition case to obtain a valid BCD word $v$.

Then

$$ t = X + (10^{16} - Y) = X - Y \pmod{10^{16}}. $$

Since the correction step preserves the represented value modulo $10^{16}$, we obtain

$$ (v_{15}\ldots v_0)_{10} = (X - Y) \bmod 10^{16}. $$

Conclusion

The algorithm is:

Add the two 16-nibble base-16 words.
Add $6$ to each nibble that is $\ge 10$, propagating carries in base 16.
The result is a valid BCD representation of the decimal sum modulo $10^{16}$.
Subtraction is performed by forming the 10’s complement in BCD and applying the same addition procedure.

This yields correct BCD addition and subtraction without any radix conversion.