TAOCP 7.1.3 Exercise 217

Let a string consist of 64 characters $c_0,\ldots,c_{63}$, each character being an 8-bit vector $c_i = (c_{i,7},c_{i,6},\ldots,c_{i,0}), \qquad c_{i,k} \in \{0,1\}.$ Define eight 64-bit words $w_0,\ld...

taocpmathematicsalgorithmsvolume-4project

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 217. [40] [40] Explore the processing of long strings of text by packing them in a “trans- posed” or “sliced” manner: Represent 64 consecutive characters as a sequence of eight octabytes w0 . . . w7, where wk contains all 64 of their kth bits.

Verified: yes
Solve time: 1m26s

Setup

Let a string consist of 64 characters $c_0,\ldots,c_{63}$, each character being an 8-bit vector

$c_i = (c_{i,7},c_{i,6},\ldots,c_{i,0}), \qquad c_{i,k} \in {0,1}.$

Define eight 64-bit words $w_0,\ldots,w_7$ by transposition:

$w_k = (c_{63,k},c_{62,k},\ldots,c_{0,k}), \qquad 0 \le k \le 7.$

Thus bit $i$ of $w_k$ is the $k$th bit of character $c_i$. Equivalently, the $64 \times 8$ bit matrix $(c_{i,k})$ is stored by columns.

A string operation acts characterwise if it applies the same 8-bit Boolean function independently to each $c_i$.

The task is to describe how such transposed packing supports efficient processing and which operations reduce to word-level bitwise operations on the $w_k$.

Solution

Characterwise Boolean operations decompose along bit positions.

Let $\circ$ be any binary Boolean operation on bits, extended to characters by

$(c_i \circ d_i)k = c{i,k} \circ d_{i,k}.$

Then for each fixed $k$ and each position $i$, the $k$th bit of the result depends only on $c_{i,k}$ and $d_{i,k}$. Hence

$w_k' = (w_k) \circ (v_k),$

where $v_k$ is defined analogously for the second string. This holds because bit $i$ of $w_k'$, namely $(c_i \circ d_i)k$, equals $c{i,k} \circ d_{i,k}$, which is exactly bit $i$ of $w_k \circ v_k$.

Therefore bitwise AND, OR, and XOR on characters are implemented by eight independent word operations:

$w_k' = w_k ,&, v_k,\quad w_k' = w_k \mid v_k,\quad w_k' = w_k \oplus v_k.$

No cross-slice interaction occurs, since each operation in (1)–(3) acts pointwise on bits.

String position shifts correspond to permutations of bit positions inside each slice. If the string is shifted left by one character position, the new characters satisfy $c_i' = c_{i+1}$ for $0 \le i \le 62$, and $c_{63}'$ is undefined or zero-padded. Then for each $k$,

$w_k' = (c_{63,k}',\ldots,c_{0,k}') = (c_{64,k},\ldots,c_{1,k}),$

so each $w_k$ undergoes the same 64-bit shift operation. Thus a character shift is implemented by shifting all eight words identically.

Characterwise equality testing reduces to a bitwise mask computation. Define

$e_i = \bigwedge_{k=0}^7 \neg(c_{i,k} \oplus d_{i,k}).$

Then $e_i=1$ exactly when $c_i=d_i$. In slice form,

$\neg(c_{i,k} \oplus d_{i,k})$

corresponds to the bitwise complement of $w_k \oplus v_k$. Hence each slice can be formed independently, and equality per character is obtained by combining slices with bitwise AND across $k$:

$e = \bigwedge_{k=0}^7 \neg(w_k \oplus v_k).$

This produces a 64-bit word $e$ whose $i$th bit indicates equality of the $i$th characters.

The representation also supports uniform bit extraction across all characters. For a fixed bit position $k$, masking or testing that bit across all characters is a single operation on $w_k$. For example, extracting the parity bit of every character is exactly $w_0$ if $k=0$, or $w_1$ if $k=1$, and so on.

More complex per-character arithmetic, such as addition modulo $256$, is not slice-independent because carries propagate between bit positions. In slice form, addition of two characters produces carry bits between $w_k$ and $w_{k+1}$ at each position $i$. This forces a coupled recurrence across slices:

$s_k = w_k \oplus v_k \oplus c_k,$

$c_{k+1} = (w_k & v_k) \mid (w_k & c_k) \mid (v_k & c_k),$

with $c_0=0$, all operations taken bitwise over 64-bit words. Thus addition becomes a bit-sliced carry propagation across the eight planes.

The transposed representation is therefore optimal for operations whose characterwise definition is purely Boolean in each bit position, and it requires additional layered computation only when arithmetic carries couple adjacent slices.

Verification

Reconstruction of the original string from $(w_0,\ldots,w_7)$ is given by

$c_i = ( (w_7)_i, (w_6)_i,\ldots,(w_0)_i ).$

Each component $(w_k)i$ is well defined as bit $i$ of word $w_k$, so this reconstruction inverts the definition of $w_k$ and yields the original matrix $(c{i,k})$ uniquely.

For characterwise XOR, bit $k$ of the result at position $i$ equals $c_{i,k} \oplus d_{i,k}$. Bit $i$ of $w_k \oplus v_k$ equals $(w_k)i \oplus (v_k)i = c{i,k} \oplus d{i,k}$, so equality holds componentwise for every $i$ and $k$.

For equality detection, $e_i=1$ if and only if every bit satisfies $c_{i,k}=d_{i,k}$. This is equivalent to $c_{i,k} \oplus d_{i,k}=0$ for all $k$, which is equivalent to each bit of $\neg(w_k \oplus v_k)$ being $1$ at position $i$, hence the AND over $k$ yields a correct indicator.

This completes the proof. ∎

Notes

The representation is a classical bit-sliced organization: it converts 64 parallel 8-bit lanes into eight parallel 64-bit lanes. It is optimal for SIMD-like Boolean processing where the same operation is applied across all character positions.

The same construction generalizes to $2^t$-bit characters stored in $2^t$ slices, yielding uniform word-parallel evaluation of any Boolean circuit on characters, while arithmetic operations require cross-slice carry networks whose depth equals the bit-width.