Binary expansion of a positive integer and its half

binaryelementary-number-theorysolution-verification

I quote from Chapter 1 (page 29) in Weissman's "An Illustrated Theory of Numbers":

If $x$ is a positive integer, write $\mathrm{bits}(x)$ for the number of bits in the binary expansion of $x$. Recall that $\mathrm{bits}(x) = \lfloor \log_2(x) \rfloor + 1$; it follows that $\mathrm{bits}(\lfloor x/2 \rfloor) \leqslant \mathrm{bits}(x) – 1$.

I don't understand why this is true; I'm reasoning as follows.

If $x = 1$, then $\left \lfloor \frac{x}{2} \right \rfloor = 0$. So we have $\mathrm{bits}(\left \lfloor \frac{x}{2} \right \rfloor) = \mathrm{bits}(x)$.

If $x \geqslant 2$, then there exists a unique $k \in \mathbb{Z}$ such that
\begin{equation*}
k \geqslant 2 \quad \text{and} \quad 2^{k-1} \leqslant x < 2^k,
\end{equation*}

that is $\mathrm{bits}(x) = k$. Therefore, we have $2^{k-2} \leqslant \frac{x}{2} < 2^{k-1}$, and the number of bits in the binary expansion of $\lfloor \frac{x}{2} \rfloor$ is exactly $k – 1$, that is $\mathrm{bits}(\left \lfloor \frac{x}{2} \right \rfloor) = \mathrm{bits}(x) – 1$.

Why am I wrong?

Best Answer

You’re not wrong, but your result does not contradict the assertion that $$\operatorname{bits}(\lfloor x/2\rfloor)\le\operatorname{bits}(x)-1\,:$$ after all, if $a=b$, then it’s certainly also true that $a\le b$. However, I have to admit that I don’t see why the author chose to state the weaker conclusion, since the stronger one follows easily from his own calculations:

$$\begin{align*} \operatorname{bits}(\lfloor x/2\rfloor)&=\lfloor\log_2(x/2)\rfloor+1\\ &=\lfloor\log_2x-1\rfloor+1\\ &=\lfloor\log_2x\rfloor-1+1\\ &=\operatorname{bits}(x)-1\,. \end{align*}$$

Yes, he really ought either to restrict himself to integers $x\ge 2$ or mention that $x=1$ is an exception, though in practice I doubt that the oversight will cause much trouble.