TAOCP 7.1.3 Exercise 40
Let $\lambda x$ denote the index of the most significant $1$ in $x$, with the convention $\lambda 0 = 0$, so that $2^{\lambda x - 1} \le x < 2^{\lambda x}$ for $x > 0$.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 40. ▶ [21] Prove (58), and find a simple way to decide if $\lambda x < \lambda y$, given $x$ and $y \ge 0$.
Verified: yes
Solve time: 1m04s
Solution
Let $\lambda x$ denote the index of the most significant $1$ in $x$, with the convention $\lambda 0 = 0$, so that $2^{\lambda x - 1} \le x < 2^{\lambda x}$ for $x > 0$.
Proof of (58)
Let $x,y \ge 0$ and consider $x \mid y$. For each bit position $k$, the binary digit of $x \mid y$ is $x_k \vee y_k$. Hence a $1$ occurs in position $k$ of $x \mid y$ if and only if at least one of $x$ or $y$ has a $1$ in that position.
If $k \ge \lambda x$ and $k \ge \lambda y$, then $x_k = y_k = 0$, so $(x \mid y)_k = 0$. Therefore no bit above $\max(\lambda x, \lambda y) - 1$ can be nonzero in $x \mid y$, which implies
$\lambda(x \mid y) \le \max(\lambda x, \lambda y).$
Let $m = \max(\lambda x, \lambda y)$. Then either $\lambda x = m$ or $\lambda y = m$. In the first case, bit $m-1$ of $x$ is $1$, hence bit $m-1$ of $x \mid y$ is $1$. In the second case, bit $m-1$ of $y$ is $1$, hence bit $m-1$ of $x \mid y$ is $1$. In either case, bit $m-1$ of $x \mid y$ equals $1$, so
$\lambda(x \mid y) \ge m.$
Combining both inequalities yields
$\lambda(x \mid y) = \max(\lambda x, \lambda y).$
This completes the proof. ∎
Decision procedure for $\lambda x < \lambda y$
Let $z = x \oplus y$. Let $k = \lambda z$. Then bit $k-1$ is the most significant position where $x$ and $y$ differ.
If $\lambda x < \lambda y$, then all bits above $\lambda x - 1$ in $x$ are zero, while bit $\lambda y - 1$ of $y$ equals $1$. Hence the most significant differing bit between $x$ and $y$ occurs at position $\lambda y - 1$, so $\lambda(x \oplus y) = \lambda y$.
If $\lambda(x \oplus y) = \lambda y$, then bit $\lambda y - 1$ differs between $x$ and $y$. Since $y_{\lambda y - 1} = 1$, this forces $x_{\lambda y - 1} = 0$, hence $\lambda x < \lambda y$.
Conversely, if $\lambda(x \oplus y) \ne \lambda y$, then the most significant differing bit lies below $\lambda y - 1$, so $x$ and $y$ share the same leading $1$ position, giving $\lambda x = \lambda y$ or $\lambda x > \lambda y$; in either case $\lambda x < \lambda y$ fails.
Thus a valid test is
$\lambda x < \lambda y \iff \lambda(x \oplus y) = \lambda y.$
Since $\lambda y$ is the position of the highest $1$ in $y$, this can be decided by first locating the highest $1$ in $y$, then checking whether the highest $1$ in $x \oplus y$ occurs in the same position.
This completes the proof. ∎