Section 7.1.3: Bitwise Tricks and Techniques

Exercise 64. [22] Find a "simple" expression for the zipper-of-sums $(x + x') \updownarrow (y + y')$, as a function of $z = x \updownarrow y$ and $z' = x' \updownarrow y'$.

Verified: yes
Solve time: 3m25s

---

The proposed solution fails because it tries to treat the interleaving as if it were compatible with ordinary addition. The correct analysis starts from the structure of the zipper operation itself and carefully tracks where carries are allowed to propagate.

1. Correct structural interpretation of the zipper

Write binary expansions

$$ x=\sum_{k\ge 0} x_k 2^k,\quad y=\sum_{k\ge 0} y_k 2^k, \quad x_k,y_k\in{0,1}. $$

The zipper-of-sums is

$$ x \updownarrow y = \sum_{k\ge 0} x_k 2^{2k} + y_k 2^{2k+1}. $$

Equivalently, if we define bit extraction from an integer $w$ by

$$ w_k = \left\lfloor \frac{w}{2^k} \right\rfloor \bmod 2, $$

then for $z=x\updownarrow y$,

$$ x_k = z_{2k}, \quad y_k = z_{2k+1}. $$

So $z$ contains $x$ in even positions and $y$ in odd positions, with no interaction between lanes.

2. What must be computed

We want

$$ (x+x') \updownarrow (y+y'). $$

This means:

• form the binary sum $x+x'$, producing a new bit sequence $u_k$,
• form the binary sum $y+y'$, producing a new bit sequence $v_k$,
• interleave them.

Thus the problem is entirely about how to express the bit sequences of $x+x'$ and $y+y'$ in terms of $z$ and $z'$.

3. Recovering the two lanes from $z$ and $z'$

Define the deinterleaving operations:

• Even-lane extraction:

$$ \operatorname{even}(w) = \sum_{k\ge 0} w_{2k} 2^k $$

• Odd-lane extraction:

$$ \operatorname{odd}(w) = \sum_{k\ge 0} w_{2k+1} 2^k $$

Then from the definition of zipper,

$$ \operatorname{even}(z)=x,\quad \operatorname{odd}(z)=y, $$

and similarly

$$ \operatorname{even}(z')=x',\quad \operatorname{odd}(z')=y'. $$

So we can reconstruct the original inputs exactly.

4. Correct computation of the sums

Now compute the two independent binary additions:

$$ u = x + x' = \operatorname{even}(z) + \operatorname{even}(z'), $$

$$ v = y + y' = \operatorname{odd}(z) + \operatorname{odd}(z'). $$

Here the additions are ordinary binary integer addition, including carries, but crucially they occur entirely inside each extracted sequence.

No carry can move between even and odd lanes because the lanes have been separated before addition.

5. Re-zipping the result

The final step is to interleave $u$ and $v$:

$$ (x+x') \updownarrow (y+y')

u \updownarrow v. $$

Substituting the expressions for $u$ and $v$, we obtain the final formula.

6. Final correct expression

$$ \boxed{ (x+x') \updownarrow (y+y')

\bigl(\operatorname{even}(z)+\operatorname{even}(z')\bigr) \updownarrow \bigl(\operatorname{odd}(z)+\operatorname{odd}(z')\bigr) } $$

Equivalently, in bit-masking form (with masks $E = 0101\ldots_2$, $O = 1010\ldots_2$):

$$ \boxed{ (x+x') \updownarrow (y+y')

\bigl((z ,&, E) \gg 0 + (z' ,&, E) \gg 0\bigr) \updownarrow \bigl((z ,&, O) \gg 1 + (z' ,&, O) \gg 1\bigr) } $$

followed by re-interleaving the resulting bit sequences.

7. Where the previous solution failed (directly addressed)

• The claim $(x+x')\updownarrow(y+y') = z+z'$ is false because addition of interleaved integers mixes bit positions via carries.
• The base-4 digit argument was invalid because $z_k$ are not independent digits under integer arithmetic.
• The correct structure is not a homomorphism with respect to $+$, but it is a homomorphism after splitting into even and odd projections.

Conclusion

The zipper-of-sums is not compatible with integer addition globally, but it is compatible with addition after projection onto even and odd bit positions. The correct expression must explicitly deinterleave, add within each lane, and reinterleave.