TAOCP 7.1.3 Exercise 63

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 63. [19] For what integers $w$, $x$, $y$, and $z$ does the zipper function satisfy (i) $x\updownarrow y = y\updownarrow x$? (ii) $(x\updownarrow y)\gg z = (x\gg \lceil z/2 \rceil)\updownarrow(y\gg \lfloor z/2 \rfloor)$? (iii) $(w\updownarrow x)&(y\updownarrow z) = (w&y)\updownarrow(x&z)$?

Verified: yes
Solve time: 1m09s

---

Solution

Let $x = (\ldots x_2 x_1 x_0)_2$ and $y = (\ldots y_2 y_1 y_0)_2$. The zipper function is defined by interleaving bits,

$x \updownarrow y = (\ldots x_2, y_2, x_1, y_1, x_0, y_0)_2.$

Thus the bit in position $2k$ of $x \updownarrow y$ equals $x_k$, and the bit in position $2k+1$ equals $y_k$.

(i)

The equality $x \updownarrow y = y \updownarrow x$ holds if and only if the binary expansions coincide bitwise at every position.

In $x \updownarrow y$, the bit at position $2k$ equals $x_k$, while in $y \updownarrow x$ the bit at position $2k$ equals $y_k$. Equality for all $k \ge 0$ requires $x_k = y_k$ for all $k \ge 0$, hence $x = y$.

Conversely, if $x = y$, then both interleavings produce the same sequence of bits, so $x \updownarrow y = y \updownarrow x$.

Thus $x \updownarrow y = y \updownarrow x$ if and only if $x = y$.

(ii)

Let $z \ge 0$. Write $x \updownarrow y$ in binary as an interleaved sequence. The operation $\gg z$ removes the lowest $z$ bits.

Each even position $2k$ in $x \updownarrow y$ contributes $x_k$, and each odd position $2k+1$ contributes $y_k$. After shifting right by $z$, the bit formerly at position $i+z$ moves to position $i$.

Consider separately the parity of $z$.

If $z = 2t$, then every pair $(x_k, y_k)$ is shifted down by $t$ full pairs, so

$(x \updownarrow y) \gg 2t = (x \gg t) \updownarrow (y \gg t).$

If $z = 2t+1$, then one extra shift removes one additional bit from the interleaving, so all even-position bits of the shifted result come from the original odd positions. The even-position sequence corresponds to $y \gg t$, and the odd-position sequence corresponds to $x \gg (t+1)$, hence

$(x \updownarrow y) \gg (2t+1) = (x \gg (t+1)) \updownarrow (y \gg t).$

Combining both cases yields

$(x \updownarrow y) \gg z = (x \gg \lceil z/2 \rceil) \updownarrow (y \gg \lfloor z/2 \rfloor).$

(iii)

Let $w,x,y,z$ be integers with binary expansions $w_k, x_k, y_k, z_k$. The $2k$-th bit of $w \updownarrow x$ equals $w_k$, and the $2k$-th bit of $y \updownarrow z$ equals $y_k$. Hence the $2k$-th bit of $(w \updownarrow x) ,&, (y \updownarrow z)$ equals $w_k \wedge y_k$.

Similarly, the $(2k+1)$-th bit of $(w \updownarrow x) ,&, (y \updownarrow z)$ equals $x_k \wedge z_k$.

Now form $(w ,&, y) \updownarrow (x ,&, z)$. Its $2k$-th bit equals $(w ,&, y)_k = w_k \wedge y_k$, and its $(2k+1)$-th bit equals $(x ,&, z)_k = x_k \wedge z_k$.

The bit in every position agrees in both expressions, so

$(w \updownarrow x),&,(y \updownarrow z) = (w ,&, y) \updownarrow (x ,&, z).$

This completes the proof. ∎