TAOCP 7.1.3 Exercise 212
Let $a = (a_{63}\dots a_1 a_0)_2,\qquad b = (b_{63}\dots b_1 b_0)_2,$ and interpret them as polynomials over $\mathbb{F}_2$, $a(x)=\sum_{i=0}^{63} a_i x^i,\qquad b(x)=\sum_{j=0}^{63} b_j x^j.$ The pro...
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 212. [M32] [M32] Suppose a = (a63 . . . a1a0)2 represents the polynomial a(x) = (a63 . . . a1a0)x = a63x63 + · · · + a1x + a0. Discuss using MXOR to compute the product c(x) = a(x)b(x), modulo x64 and mod 2.
Verified: yes
Solve time: 1m16s
Setup
Let
$a = (a_{63}\dots a_1 a_0)2,\qquad b = (b{63}\dots b_1 b_0)_2,$
and interpret them as polynomials over $\mathbb{F}_2$,
$a(x)=\sum_{i=0}^{63} a_i x^i,\qquad b(x)=\sum_{j=0}^{63} b_j x^j.$
The product in $\mathbb{F}_2[x]$ reduced modulo $x^{64}$ is
$c(x)=a(x)b(x)\bmod x^{64}=\sum_{k=0}^{63} c_k x^k,$
where
$c_k=\sum_{\substack{i+j=k\0\le i,j\le 63}} a_i b_j \pmod 2.$
The goal is to describe how this computation can be carried out using MXOR-type bitwise operations, meaning word-level exclusive-or accumulation combined with shifts and masking.
Solution
Each coefficient $c_k$ is a parity of pairwise products $a_i b_j$ with $i+j=k$. Over $\mathbb{F}_2$, addition is XOR and multiplication is AND of bits, so each term $a_i b_j$ contributes either $0$ or $1$.
Fix an index $i$. If $a_i=0$, no contribution arises from this $i$. If $a_i=1$, the contribution to the product is the polynomial $x^i b(x)$ truncated at degree $63$, corresponding to the word
$(b \ll i)\ &\ ((1 \ll 64)-1).$
Hence the full product is the XOR-sum of shifted copies of $b$:
$c = \bigoplus_{i=0}^{63} \left(a_i \cdot (b \ll i)\right),$
where multiplication by $a_i$ means either the zero word or the shifted word.
This identity follows directly from distributivity in $\mathbb{F}_2[x]$ and the definition of bitwise XOR as addition in $\mathbb{F}_2$.
To compute this using MXOR-style operations, one scans the bits of $a$. For each $i$ with $a_i=1$, one forms a shifted version of $b$ and accumulates it into an output register using MXOR, which performs wordwise exclusive-or. Each update has the form
$c \leftarrow c \oplus (b \ll i).$
The truncation modulo $x^{64}$ ensures that any bits shifted beyond position $63$ are discarded, since they correspond to terms $x^k$ with $k \ge 64$.
Equivalently, the same computation can be expressed symmetrically by scanning $b$ instead:
$c = \bigoplus_{j=0}^{63} \left(b_j \cdot (a \ll j)\right).$
Both formulations implement the same convolution in $\mathbb{F}_2[x]/(x^{64})$.
The MXOR instruction is used precisely for the accumulation step, since each partial contribution is combined by bitwise exclusive-or with no carries.
Verification
For each pair $(i,j)$ with $0 \le i,j \le 63$, the term $a_i b_j$ appears in exactly one shifted copy $(b \ll i)$ at position $i+j$, and in no other shifted copy, since the shift index is uniquely determined by $i$. Thus every product term contributes exactly once to coefficient $c_{i+j}$.
At each bit position $k$, the resulting bit is the XOR of all contributions $a_i b_j$ with $i+j=k$, matching the definition of multiplication in $\mathbb{F}_2[x]$. No carry propagation occurs because addition is XOR, so bit positions are independent. The truncation modulo $x^{64}$ removes all contributions with $i+j \ge 64$, matching the stated reduction by $x^{64}$.
Each MXOR accumulation step preserves correctness because XOR is associative and commutative, so the order of combining shifted partial products does not affect the final word.
This completes the proof. ∎
Notes
The same structure extends to wider words of length $w$, producing multiplication in $\mathbb{F}_2[x]/(x^w)$. The computation is the classical “shift-and-XOR convolution,” and it is the bit-level analogue of ordinary integer multiplication with carries removed.