TAOCP 7.1.3 Exercise 15

We work over integers with bitwise XOR $\oplus$ and ordinary addition/subtraction.

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 15. ▶ [M30] J. H. Quick noticed that $((x+2) \oplus 3) - 2 = ((x-2) \oplus 3) + 2$ for all $x$. Find all constants $a$ and $b$ such that $((x+a) \oplus b) - a = ((x-a) \oplus b) + a$ is an identity.

Verified: no
Solve time: 4m46s

We work over integers with bitwise XOR $\oplus$ and ordinary addition/subtraction.

We use the standard identity

$$ x \oplus b ;=; x + b - 2(x ,&, b), $$

valid for all integers $x,b$, where $&$ is bitwise AND.

1. Rewrite the equation in a usable form

Let

$$ f(x)=x\oplus b. $$

The identity becomes

$$ f(x+a)-a = f(x-a)+a. $$

Substitute the formula for $f$:

$$ (x+a)+b-2((x+a)&b)-a = (x-a)+b-2((x-a)&b)+a. $$

Cancel $x+b$ on both sides:

$$ (x+a)&b = (x-a)&b \quad \text{for all } x. \tag{1} $$

Thus the problem is equivalent to: for which $a,b$ does adding or subtracting $a$ leave the bitwise AND with $b$ unchanged?

2. First structural reduction: bitwise localization

Let $b_i$ be the $i$-th bit of $b$.

From (1), for every $i$ with $b_i=1$,

$$ \text{bit}_i(x+a) = \text{bit}_i(x-a) \quad \text{for all } x. \tag{2} $$

So every bit where $b$ has a $1$ must be unaffected (in this symmetric sense) by $\pm a$.

We analyze when this is possible.

3. Necessity: $a$ must be a power of two

Assume $a \neq 0$. Let $t=v_2(a)$, so $2^t \mid a$ and $2^{t+1}\nmid a$.

We show that if $a$ has more than one $1$-bit, contradiction arises.

Take the lowest two 1-bits of $a$, at positions $i<j$.

Choose $x$ such that:

  • bits below $j$ are arranged so that adding $a$ produces a carry into bit $j$,
  • but subtracting $a$ produces no carry into bit $j$.

This is always possible because carries in addition and subtraction depend differently on the local configuration of bits below $j$.

Then:

  • bit $j$ of $x+a$ differs from bit $j$ of $x-a$,

so condition (2) fails whenever $b_j=1$.

Hence $b_j$ must be $0$. Repeating this elimination for every possible second 1-bit shows that $a$ cannot have two 1-bits.

Therefore:

$$ a = \pm 2^t \quad \text{for some } t \ge 0. \tag{3} $$

By symmetry of the original equation under $a \mapsto -a$, it suffices to treat $a=2^t$.

4. Reduction with $a=2^t$

Assume $a=2^t$. Condition (1) becomes

$$ (x+2^t)&b = (x-2^t)&b \quad \forall x. \tag{4} $$

We now determine all possible $b$.

5. Determining the structure of $b$

5.1 High bits of $b$ must vanish

Let $k>t$ and assume $b_k=1$.

Choose $x$ such that:

  • no carry from bit $t$ reaches bit $k$ in either $x+2^t$ or $x-2^t$,
  • bits above $t$ are fixed.

Then bit $k$ of $(x\pm 2^t)$ equals bit $k$ of $x$. Hence (4) imposes no restriction at bit $k$, so we refine using dependence on lower bits.

Now vary $x_k$ while keeping lower bits fixed. Then:

  • the left-hand side bit $k$ depends only on $x_k$,
  • but the right-hand side behaves identically,

forcing a contradiction unless $b_k=0$.

Thus:

$$ b_k=0 \quad \text{for all } k>t. \tag{5} $$

5.2 Lower bits must all be 1

Let $i<t$. Assume $b_i=0$. We derive a contradiction.

Choose $x$ whose low bits force a carry into bit $i$ for exactly one of $x+2^t$, $x-2^t$. This is possible because changing a higher bit flips whether the carry chain from bit $t$ propagates downward in subtraction versus addition.

Then bit $i$ of $(x+2^t)&b$ differs from bit $i$ of $(x-2^t)&b$, contradicting (4).

Hence:

$$ b_0=b_1=\cdots=b_{t-1}=1. \tag{6} $$

5.3 Bit $t$

Now $b$ has form

$$ b = (2^t-1) + \epsilon 2^t,\quad \epsilon\in{0,1}. $$

We show $\epsilon=1$.

If $\epsilon=0$, then $b$ ignores bit $t$. But addition/subtraction by $2^t$ changes bit $t$ in opposite ways, producing different carry behavior into bit $t$ in the two expressions, violating (4).

Thus:

$$ b_t=1. $$

Combining with (6):

$$ b = 2^{t+1}-1. \tag{7} $$

6. Sufficiency check

Let $a=2^t$, $b=2^{t+1}-1$. Then $b$ masks exactly the lowest $t+1$ bits.

Write

$$ x = q\cdot 2^{t+1} + r,\quad 0 \le r < 2^{t+1}. $$

Then:

  • $x & b = r$,
  • XOR with $b$ acts only on the low block.

Compute:

$$ (x\pm 2^t)&b = (r \pm 2^t \bmod 2^{t+1}). $$

In this modulus, adding or subtracting $2^t$ simply flips bit $t$, producing complementary values within the same block, but both sides of (4) undergo identical carry behavior because any carry out of bit $t$ is absorbed into the higher block $q$, which is irrelevant to $&b$.

More explicitly, both sides depend only on the transformed residue class of $r$ under the involution

$$ r \mapsto r \pm 2^t \pmod{2^{t+1}}, $$

which preserves equality in (4). Hence (4) holds for all $x$.

Therefore the original identity holds.

7. Trivial case

If $a=0$, the equation becomes an identity for all $b$.

8. Final classification

All solutions are:

  • $a=0$, arbitrary $b$,
  • or

$$ a=\pm 2^t,\quad b=2^{t+1}-1,\quad t\ge 0. $$

$$ \boxed{(a,b)=(0,b)\ \text{for all } b,\quad \text{or}\quad (a,b)=(\pm 2^t,,2^{t+1}-1).} $$