Expansión binaria de un entero positivo y su mitad
Cito del Capítulo 1 (página 29) de "Una teoría ilustrada de los números" de Weissman:
Si $x$ es un entero positivo, escribe $\mathrm{bits}(x)$ para el número de bits en la expansión binaria de $x$. Recordar que$\mathrm{bits}(x) = \lfloor \log_2(x) \rfloor + 1$; resulta que$\mathrm{bits}(\lfloor x/2 \rfloor) \leqslant \mathrm{bits}(x) - 1$.
No entiendo por qué esto es cierto; Estoy razonando como sigue.
Si $x = 1$, luego $\left \lfloor \frac{x}{2} \right \rfloor = 0$. Entonces tenemos$\mathrm{bits}(\left \lfloor \frac{x}{2} \right \rfloor) = \mathrm{bits}(x)$.
Si $x \geqslant 2$, entonces existe un único $k \in \mathbb{Z}$tal que \ begin {ecuación *} k \ geqslant 2 \ quad \ text {y} \ quad 2 ^ {k-1} \ leqslant x <2 ^ k, \ end {ecuación *} que es$\mathrm{bits}(x) = k$. Por lo tanto, tenemos$2^{k-2} \leqslant \frac{x}{2} < 2^{k-1}$, y el número de bits en la expansión binaria de $\lfloor \frac{x}{2} \rfloor$ es exactamente $k - 1$, es decir $\mathrm{bits}(\left \lfloor \frac{x}{2} \right \rfloor) = \mathrm{bits}(x) - 1$.
¿Por qué me equivoco?
Respuestas
No se equivoca, pero su resultado no contradice la afirmación de que $$\operatorname{bits}(\lfloor x/2\rfloor)\le\operatorname{bits}(x)-1\,:$$ después de todo, si $a=b$, entonces también es cierto que $a\le b$. Sin embargo, debo admitir que no veo por qué el autor eligió enunciar la conclusión más débil, ya que la más sólida se deduce fácilmente de sus propios cálculos:
$$\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*}$$
Sí, realmente debería restringirse a números enteros $x\ge 2$ o mencionar eso $x=1$ es una excepción, aunque en la práctica dudo que el descuido cause muchos problemas.