Section 7.1.3: Bitwise Tricks and Techniques

Exercise 6. [M22] Find all integers $x$ and $y$ such that (a) $x \gg y = y \gg x$; (b) $x \ll y = y \ll x$.

Verified: no
Solve time: 5m27s

---

We use Knuth’s definitions for all integers $x,y$:

$$ x \gg y = \left\lfloor \frac{x}{2^y} \right\rfloor,\qquad x \ll y = x\cdot 2^y, $$

where $2^y$ is a dyadic rational when $y<0$, and all floor effects occur only in $\gg$.

(a) $x \gg y = y \gg x$

We solve

$$ \left\lfloor \frac{x}{2^y} \right\rfloor = \left\lfloor \frac{y}{2^x} \right\rfloor. $$

Case 1: $x,y \ge 0$

Here $2^x,2^y\in \mathbb{Z}_{>0}$. If $x,y\ge 0$, then

$$ \frac{x}{2^y}\in \mathbb{Q}{\ge 0},\quad \frac{y}{2^x}\in \mathbb{Q}{\ge 0}. $$

If equality holds, symmetry forces either both sides $0$ or both positive.

If $x \gg y = y \gg x = t \ge 1$, then

$$ x \ge 2^y,\qquad y \ge 2^x, $$

which is impossible since $2^x$ grows strictly faster than $x$ for $x\ge 0$. Hence $t=0$.

So we require

$$ x < 2^y,\qquad y < 2^x. $$

If $x<y$, then $y \ge x+1$, so $2^x \le 2^{y-1}$, hence $y < 2^x \le 2^{y-1}$, impossible for $y\ge 1$. Similarly for $y<x$. Thus $x=y$.

So in the nonnegative case:

$$ x=y. $$

Case 2: $x,y<0$

Write $x=-a,; y=-b$ with $a,b\ge 1$. Then

$$ 2^x = 2^{-a} = \frac{1}{2^a},\qquad 2^y = \frac{1}{2^b}. $$

Compute:

$$ x \gg y = \left\lfloor \frac{-a}{2^{-b}} \right\rfloor = \left\lfloor -a\cdot 2^b \right\rfloor = -a2^b, $$

and similarly

$$ y \gg x = -b2^a. $$

Thus

$$ -a2^b = -b2^a \quad \Longleftrightarrow \quad a2^b = b2^a. $$

Rewriting:

$$ \frac{a}{2^a} = \frac{b}{2^b}. $$

For integers $a,b\ge 1$, check possibilities:

• $a=b$ always works.
• The only nontrivial solution is $a=1,b=2$ (and swap), since

$$ 1\cdot 2^2 = 4 = 2\cdot 2^1. $$

Hence

$$ (a,b)=(1,2)\ \text{or}\ (2,1)\ \text{or}\ a=b. $$

Translating back:

$$ (x,y)=(-1,-2),;(-2,-1),;\text{or } x=y. $$

Case 3: mixed signs

If $x\ge 0 > y$, then

$$ x \gg y = \left\lfloor x\cdot 2^{|y|} \right\rfloor \ge 0, $$

while

$$ y \gg x = \left\lfloor \frac{y}{2^x} \right\rfloor < 0, $$

so equality is impossible. The other mixed case is symmetric.

Result for (a)

$$ \boxed{x=y ;\text{or}; (x,y)=(-1,-2);\text{or};(-2,-1).} $$

(b) $x \ll y = y \ll x$

We solve

$$ x2^y = y2^x. $$

Case 1: $x,y \ge 0$

If $x=y$, the equation holds.

Assume $x\ne y$. WLOG $x>y\ge 0$. Then

$$ x = y2^{x-y}. $$

If $y=0$, then $x=0$, contradiction. So $y\ge 1$, hence $y \mid x$. Write $x=ky$, $k\ge 2$. Then

$$ ky = y2^{x-y} \Rightarrow k = 2^{x-y}. $$

So

$$ k = 2^{(k-1)y}. $$

The only possibility is $k=2$, giving $2 = 2^{(2-1)y} = 2^y$, hence $y=1$, $x=2$.

Thus nonnegative solutions:

$$ (x,y)=(1,1),(2,2),(1,2),(2,1). $$

Case 2: $x,y<0$

Write $x=-a,;y=-b$, $a,b\ge 1$. Then

$$ (-a)2^{-b} = (-b)2^{-a} ;\Longleftrightarrow; a2^{-b} = b2^{-a}. $$

Multiply by $2^{a+b}$:

$$ a2^a = b2^b. $$

As in part (a), the only integer solutions are $a=b$. Hence

$$ x=y. $$

Case 3: mixed signs

If $x\ge 0>y$, then $x2^y$ is nonnegative while $y2^x<0$, impossible. Symmetric case similarly impossible.

Result for (b)

$$ \boxed{x=y ;\text{or}; (x,y)=(1,2);\text{or};(2,1).} $$

Final answer

• (a) $x=y$ or $(x,y)=(-1,-2),(-2,-1)$
• (b) $x=y$ or $(x,y)=(1,2),(2,1)$