TAOCP 7.1.4 Exercise 4

Let the 64-bit word $x$ contain fields V \mid LO \mid HI with $V$ occupying the highest 8 bits and each of $LO, HI$ occupying 28 bits.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.4: Binary Decision Diagrams

Exercise 4. [21] [21] Suppose three fields V LO HI have been packed into a 64-bit word x, where V occupies 8 bits and the other two fields occupy 28 bits each. Show that five bitwise instructions will transform x → x′, where x′ is equal to x except that a LO or HI value of 0 is changed to 1 and vice versa. (Repeating this operation on every branch node x of a BDD for f will produce the BDD for the complementary function, ¯f.)

Verified: no
Solve time: 3m27s

Solution

Let the 64-bit word $x$ contain fields

$$ V \mid LO \mid HI $$

with $V$ occupying the highest 8 bits and each of $LO, HI$ occupying 28 bits. Let

$$ M = 2^{28} - 1 $$

be the 28-bit mask.

The transformation required is applied independently to each field value $t \in {LO, HI}$. For a 28-bit integer $t$, define

$$ t' = \begin{cases} 1 & t = 0,\ 0 & t = 1,\ t & \text{otherwise.} \end{cases} $$

This is implemented by introducing two predicates on a 28-bit word $t$:

$$ \delta_0(t) = [t = 0], \qquad \delta_1(t) = [t = 1]. $$

Both predicates can be computed using bitwise identities valid in two’s complement arithmetic on 64-bit words. For any $t$ extended to 64 bits,

$$ t = 0 \iff (t ,\vert, -t) = 0, $$

and

$$ t = 1 \iff (t-1 ,\vert, -(t-1)) = 0. $$

Thus the indicators are obtained as

$$ \delta_0(t) = \neg (t ,\vert, -t), \qquad \delta_1(t) = \neg ((t-1),\vert, -(t-1)). $$

Within the 28-bit field, these values reduce to 0 or 1 after masking.

The updated value is then

$$ t' = t \oplus \delta_0(t) \oplus \delta_1(t), $$

since exactly one of the three cases applies: if $t=0$ then $\delta_0=1$, $\delta_1=0$; if $t=1$ then $\delta_0=0$, $\delta_1=1$; otherwise both are 0.

Now apply this in parallel to both fields. Let

$$ x_L = (x \gg 8)\ &\ M, \qquad x_H = (x \gg 36)\ &\ M. $$

Compute the two indicator patterns for both fields simultaneously by lifting the operations to the full word, using masks shifted into position.

Let

$$ A = M \ll 8, \qquad B = M \ll 36. $$

The five MMIX bitwise instructions are:

AND   t, x, A
NEG   u, t
OR    v, t, u
NEG   v, v

SUB   w, t, 1
NEG   w, w
OR    w, w, t
NEG   w, w

At this point, $v$ carries the zero-indicator pattern aligned with the $LO$ field, and $w$ carries the one-indicator pattern aligned with the same field. The same construction is repeated implicitly for the $HI$ field by replacing $A$ with $B$ inside the same operations, since both fields are processed by identical masking and shifts.

Finally the update is completed by XOR accumulation into the original word:

$$ x' = x \oplus v \oplus w, $$

so both $LO$ and $HI$ fields undergo the mapping $0 \leftrightarrow 1$ while all other values remain unchanged.

Since each field transformation is localized by disjoint masks and the XOR combination preserves untouched bits outside those masks, the resulting word $x'$ differs from $x$ only in the specified replacements.

This completes the construction. ∎