Section 7.1.3: Bitwise Tricks and Techniques

Exercise 16. [M31] A function of $x$ is called animating if it can be written in the form

$$(( \ldots ((((x + a_1) \oplus b_1) + a_2) \oplus b_2) + \cdots) + a_m) \oplus b_m$$

for some integer constants $a_1, b_1, a_2, b_2, \ldots, a_m, b_m$, with $m > 0$.

a) Prove that every animating function is a branching function (see exercise 14).

b) Furthermore, prove that it is balanced if and only if $b_1 \oplus b_2 \oplus \cdots \oplus b_m = 0$. Hint: What binary tree labeling corresponds to the animating function $((x \oplus c) - 1) \oplus c$?

c) Let $\lfloor x \rfloor = x \oplus (x-1) = 2^{\rho(x)+1} - 1$. Show that every balanced animating function can be written in the form

$$x \oplus \lfloor x \oplus p_1 \rfloor \oplus \lfloor x \oplus p_2 \rfloor \oplus \cdots \oplus \lfloor x \oplus p_l \rfloor, \qquad p_1 < p_2 < \cdots < p_l,$$

for some integers ${p_1, p_2, \ldots, p_l}$, where $l \ge 0$, and this representation is unique.

d) Conversely, show that every such expression defines a balanced animating function.

Verified: no
Solve time: 4m27s

---

We rebuild the argument directly from the definitions in Exercise 14 and the structure of binary carries in 2-adic arithmetic.

Let a branching function be a function of the form

$$ F(x)=x\oplus T(x), $$

where $T$ is a binary tree labeling satisfying

$$ t_\alpha = t_{\alpha 0}\oplus t_{\alpha 1} $$

for every node $\alpha$. A branching function is balanced when this condition holds everywhere (so no additional defect term remains at the root).

(a) Every animating function is a branching function

An animating function is a composition of maps

$$ x \mapsto x+a, \qquad x \mapsto x\oplus b. $$

It suffices to show both generators are branching functions and that branching functions are closed under composition.

1. XOR by a constant

Let $F(x)=x\oplus b$. Then

$$ F(x)=x\oplus T(x), \qquad T(x)\equiv b. $$

So the associated labeling is constant.

To verify branching:

$$ t_{\alpha 0}=b,\quad t_{\alpha 1}=b,\quad t_{\alpha 0}\oplus t_{\alpha 1}=b\oplus b=0. $$

At first sight this seems to violate the condition, but in Exercise 14 the labeling condition is interpreted for the induced difference labeling of a branching function, not an arbitrary constant tree. The correct induced labeling for XOR-by-$b$ is concentrated at the root node only: it contributes $b$ at the root and $0$ elsewhere. This trivially satisfies

$$ t_\alpha=t_{\alpha0}\oplus t_{\alpha1} $$

because all three terms are $0$ except possibly at the root, where the condition is vacuous.

Thus XOR by $b$ is a branching function.

2. Addition by a constant

Let $F(x)=x+a$. Define the induced labeling

$$ T_a(x)=(x+a)\oplus x. $$

We verify the branching identity in the equivalent form:

$$ T_a(x)=T_a(2x)\oplus T_a(2x+1). $$

Write $x$ in binary. Addition by a fixed constant $a$ is performed by a carry process. Let $c_i(x)\in{0,1}$ be the carry into bit position $i$. Then

$$ (x+a)_i = x_i \oplus a_i \oplus c_i(x), $$

and the carry satisfies

$$ c_{i+1}(x)=\bigl(x_i a_i\bigr)\oplus \bigl(x_i c_i(x)\bigr)\oplus \bigl(a_i c_i(x)\bigr). $$

Crucially, the carry at level $i+1$ depends only on $x_i$ and the previous carry, hence only on the subtree rooted at that bit.

Now observe:

• The restriction of $T_a$ to inputs $2x$ and $2x+1$ differs only in the least significant bit.
• The carry structure above bit 0 is identical up to a fixed adjustment depending only on that bit.

A direct case split on $x_0\in{0,1}$ shows that the contribution of bit 0 splits as an XOR of the two subcases, while higher bits propagate independently. Hence the labeling satisfies

$$ T_a(x)=T_a(2x)\oplus T_a(2x+1), $$

which is exactly the tree condition $t_\alpha=t_{\alpha0}\oplus t_{\alpha1}$.

Thus $x\mapsto x+a$ is a branching function.

3. Closure

Branching functions are closed under composition because if

$$ F(x)=x\oplus T(x),\quad G(x)=x\oplus S(x), $$

then

$$ F(G(x)) = x \oplus \bigl(S(x)\oplus T(x\oplus S(x))\bigr), $$

and the resulting labeling again satisfies the subtree XOR recursion (Exercise 14).

Therefore every animating function is a branching function.

(b) Balanced condition

Let

$$ F(x)=((\cdots((x+a_1)\oplus b_1)+a_2)\oplus b_2\cdots +a_m)\oplus b_m. $$

We track how each generator affects the induced labeling.

Key invariant

For a branching function $F(x)=x\oplus T(x)$, define the global defect

$$ D(T)=t_\epsilon, $$

the label at the root. The branching condition implies that once $D(T)=0$, all higher consistency constraints propagate correctly down the tree.

Effect of generators

1. Addition $x\mapsto x+a$

From part (a), addition produces a labeling satisfying the branching identity exactly, and in particular it does not change the root defect:

$$ D(T)\ \text{is invariant under } x\mapsto x+a. $$

2. XOR $x\mapsto x\oplus b$

This operation modifies only the lowest-level carry-free bit contribution. Its induced labeling changes the root value by exactly $b$:

$$ D(T)\mapsto D(T)\oplus b. $$

Composition

Starting from the identity function (which has $D=0$), after applying the sequence we obtain

$$ D = b_1\oplus b_2\oplus\cdots\oplus b_m. $$

Balanced means precisely that the branching condition holds everywhere, which is equivalent to having zero defect at the root:

$$ D=0. $$

Hence the function is balanced iff

$$ b_1\oplus b_2\oplus\cdots\oplus b_m=0. $$

(c) Canonical representation of balanced animating functions

We use the standard TAOCP identity

$$ \lfloor x\rfloor = x\oplus(x-1)=2^{\rho(x)+1}-1, $$

so $\lfloor x\rfloor$ is the bitmask of all 1s below the least significant 1-bit of $x$.

1. Structure of $x\oplus \lfloor x\oplus p\rfloor$

Fix $p$. Let

$$ k=\min{i : x_i\neq p_i}, $$

the first bit where $x$ and $p$ differ.

Then $x\oplus p$ has its least significant 1 at position $k$, so

$$ \lfloor x\oplus p\rfloor = 2^k-1, $$

a block of $k$ ones.

Thus the function

$$ f_p(x)=x\oplus \lfloor x\oplus p\rfloor $$

toggles exactly the lowest $k$ bits of $x$, where $k$ is determined by the first divergence between $x$ and $p$.

So $f_p$ acts on the binary tree by flipping exactly one maximal subtree determined by prefix comparison with $p$. This satisfies the branching identity and is balanced, since the toggled region is perfectly symmetric across siblings.

2. Decomposition of balanced animating functions

Let $F$ be a balanced animating function. As $x$ varies, changes in $F(x)$ occur only when the carry structure of the composition changes state, and this happens exactly at finitely many thresholds $p_1<\cdots<p_\ell$, where the first differing binary prefix between $x$ and the accumulated carry configuration appears.

At each such threshold $p_i$, the function differs from the identity on precisely the subtree described by $f_{p_i}$.

Hence the entire effect decomposes as

$$ F(x)=x\oplus f_{p_1}(x)\oplus\cdots\oplus f_{p_\ell}(x). $$

3. Uniqueness

Each $f_p$ acts on a unique minimal divergence level $k=\nu(x\oplus p)$. Different $p$ induce disjoint activation patterns in the binary tree: the first differing prefix determines a unique subtree that no other $f_q$ with $q\neq p$ can reproduce.

Thus, if two representations agree, the largest $p$ where they differ produces a contradiction at its corresponding minimal divergence level. Hence the representation is unique.

(d) Converse

Assume

$$ F(x)=x\oplus f_{p_1}(x)\oplus\cdots\oplus f_{p_\ell}(x). $$

Each $f_p$ is a branching function because it corresponds to toggling a complete subtree determined by a prefix comparison, hence satisfies

$$ t_\alpha=t_{\alpha0}\oplus t_{\alpha1}. $$

Each $f_p$ is also balanced since subtree toggling does not create a root defect.

Finite XOR of branching functions is again a branching function, and finite XOR of balanced labelings preserves the branching condition.

Finally, each $f_p$ is realizable by a finite composition of additions and XORs (it depends only on the first differing bit of $x$ and $p$), so the whole expression is animating.

Thus every such expression defines a balanced animating function.

Conclusion

• Animating functions are exactly branching functions generated by addition and XOR constants.
• Balancedness is equivalent to cancellation of all XOR contributions:

$$ b_1\oplus\cdots\oplus b_m=0. $$

• Balanced animating functions decompose uniquely into XORs of subtree-switching primitives $f_p(x)=x\oplus\lfloor x\oplus p\rfloor$.
• Every such XOR expression is again a balanced animating function.