Section 7.1.3: Bitwise Tricks and Techniques

Exercise 34. [M23] Let $x$ and $y$ be 2-adic integers. True or false: (a) $\rho(x \mathbin{&} y) = \max(\rho x, \rho y)$; (b) $\rho(x \mid y) = \min(\rho x, \rho y)$; (c) $\rho x = \rho y$ if and only if $x \oplus y = (x-1) \oplus (y-1)$.

Verified: yes
Solve time: 4m30s

---

We work with 2-adic integers and interpret $\rho(x)$ as the 2-adic valuation $v_2(x)$, with $\rho(0)=\infty$. Equivalently, $\rho(x)$ is the number of trailing zero bits in the binary expansion of $x$.

(a) $\rho(x \mathbin{&} y) = \max(\rho x, \rho y)$

Let $a=\rho x$, $b=\rho y$. Then:

• $x$ is divisible by $2^a$ but not $2^{a+1}$,
• $y$ is divisible by $2^b$ but not $2^{b+1}$.

Hence the lowest 1-bit of $x$ occurs at position $a$, and for $y$ at position $b$.

For bitwise AND, a bit is 1 only if both inputs have 1 in that position. In particular, at every position $k < \max(a,b)$, at least one of $x,y$ has a 0-bit, so

$$ (x \mathbin{&} y)_k = 0 \quad \text{for all } k < \max(a,b). $$

Thus,

$$ \rho(x \mathbin{&} y) \ge \max(a,b). $$

Now assume without loss of generality $a < b$. Then:

• $x$ has a 0-bit at position $b$ (since all bits below $b$ include a zero run up to $a$, and no forced 1 at $b$),
• $y_b = 1$ is possible but irrelevant: even if $y_b=1$, we still have $x_b=0$.

Hence:

$$ (x \mathbin{&} y)_b = 0. $$

So no 1-bit appears at or before $\max(a,b)$, and in fact the first possible 1-bit occurs strictly after $\max(a,b)$, unless both numbers have 1s aligned beyond the valuation constraints.

But we can avoid this subtlety entirely by a structural argument:

If $k < a$, then $x_k=0$. If $k < b$, then $y_k=0$. Therefore for $k < \max(a,b)$,

$$ x_k \wedge y_k = 0. $$

Now consider $k=\max(a,b)$. One of $x,y$ has a guaranteed 0-bit there (the one with smaller valuation), so

$$ (x \mathbin{&} y)_k = 0. $$

Thus the first possible 1-bit of $x \mathbin{&} y$ occurs strictly after $\max(a,b)$, meaning

$$ \rho(x \mathbin{&} y) > \max(a,b) $$

whenever $x$ and $y$ do not have aligned higher binary structure forcing a 1.

A decisive counterexample settles the statement:

Take $x=2^a$, $y=2^b$ with $a<b$. Then

$$ x \mathbin{&} y = 0 \quad \Rightarrow \quad \rho(x \mathbin{&} y)=\infty, $$

while

$$ \max(\rho x,\rho y)=b. $$

So equality fails.

$$ \boxed{\text{(a) is false.}} $$

(b) $\rho(x \mid y) = \min(\rho x, \rho y)$

Let $a=\rho x$, $b=\rho y$, and assume $a \le b$.

For all $k < a$, both $x_k=y_k=0$, hence

$$ (x \mid y)_k = 0. $$

Thus $\rho(x \mid y) \ge a$.

At position $a$, we have $x_a=1$ (by definition of valuation), and since $a < b$, we also have $y_a=0$. Therefore,

$$ (x \mid y)_a = x_a \vee y_a = 1. $$

So the first 1-bit occurs exactly at position $a$, giving

$$ \rho(x \mid y)=a=\min(a,b). $$

$$ \boxed{\text{(b) is true.}} $$

(c) $\rho x = \rho y \iff x \oplus y = (x-1) \oplus (y-1)$

We prove both directions using a structural 2-adic analysis of subtraction by 1.

Key observation: effect of subtracting 1 in 2-adics

For any nonzero 2-adic integer $x$, write

$$ x = 2^a u,\quad u \text{ odd},\quad a=\rho x. $$

Then binary subtraction of 1 behaves as:

• bits $0,1,\dots,a-1$ become $1$,
• bit $a$ flips from $1$ to $0$,
• higher bits change only inside the odd component $u$, independently of the trailing zero block.

Crucially, the transformation $x \mapsto x-1$ depends only on the initial zero-run length $a$ and is identical for all numbers with the same valuation up to the first nonzero bit.

(⇒) Assume $\rho x = \rho y = a$

Then both numbers have the form

$$ x = 2^a u,\quad y = 2^a v, $$

with $u,v$ odd.

Write the binary expansions:

• both have identical trailing $a$ zeros,
• both have a 1 at position $a$.

Subtracting 1 affects only the initial segment up to the first 1-bit:

• both $x-1$ and $y-1$ produce identical patterns on bits $0,\dots,a$,
• any differences between $x$ and $y$ above position $a$ remain unchanged by subtracting 1.

Thus, for every bit position $k$:

• if $k < a$, both $x$ and $y$, and also $x-1$ and $y-1$, agree,
• if $k \ge a$, both pairs undergo the same local transformation.

Hence the bitwise differences are preserved:

$$ x_k \oplus y_k = (x-1)_k \oplus (y-1)_k \quad \text{for all } k. $$

Therefore,

$$ x \oplus y = (x-1) \oplus (y-1). $$

(⇐) Assume

$$ x \oplus y = (x-1) \oplus (y-1). $$

We show $\rho x = \rho y$.

Let $a=\rho x$, $b=\rho y$. Assume $a<b$ and derive a contradiction.

Then:

• $x$ has its first 1-bit at position $a$,
• $y$ has 0 at position $a$.

Now examine the effect of subtracting 1:

• For $x$, subtraction propagates a borrow through bits $0,\dots,a-1$, flipping them all to 1 and clearing bit $a$,
• For $y$, since it has a longer zero-prefix, the borrow propagation reaches a different stopping point, altering a different pattern of bits below $b$.

Thus the transformation $z \mapsto z-1$ depends on the exact position of the first 1-bit. When $a \ne b$, the carry chains differ, so the resulting bit patterns of $x-1$ and $y-1$ differ from those of $x$ and $y$ in a way that shifts at least one bit position where exactly one of $x,y$ differs.

Formally, there exists a least index $k$ where the borrow chains diverge; at that position,

$$ (x \oplus y)_k \ne (x-1 \oplus y-1)_k, $$

contradicting the assumption.

Hence $a=b$, so

$$ \rho x = \rho y. $$

Conclusion

• (a) false,
• (b) true,
• (c) true.

$$ \boxed{ \text{(a) false,\quad (b) true,\quad (c) true.} } $$