Expansão binária de um número inteiro positivo e sua metade

Aug 18 2020

Cito o Capítulo 1 (página 29) em "Uma Teoria Ilustrada dos Números" de Weissman:

E se $x$ é um número inteiro positivo, escreva $\mathrm{bits}(x)$ para o número de bits na expansão binária de $x$. Lembre-se disso$\mathrm{bits}(x) = \lfloor \log_2(x) \rfloor + 1$; segue que$\mathrm{bits}(\lfloor x/2 \rfloor) \leqslant \mathrm{bits}(x) - 1$.

Não entendo por que isso é verdade; Estou raciocinando da seguinte maneira.

E se $x = 1$, então $\left \lfloor \frac{x}{2} \right \rfloor = 0$. Então nós temos$\mathrm{bits}(\left \lfloor \frac{x}{2} \right \rfloor) = \mathrm{bits}(x)$.

E se $x \geqslant 2$, então existe um único $k \in \mathbb{Z}$de modo que \ begin {equation *} k \ geqslant 2 \ quad \ text {e} \ quad 2 ^ {k-1} \ leqslant x <2 ^ k, \ end {equation *} que é$\mathrm{bits}(x) = k$. Portanto, temos$2^{k-2} \leqslant \frac{x}{2} < 2^{k-1}$, e o número de bits na expansão binária de $\lfloor \frac{x}{2} \rfloor$ é exatamente $k - 1$, isso é $\mathrm{bits}(\left \lfloor \frac{x}{2} \right \rfloor) = \mathrm{bits}(x) - 1$.

Por que estou errado?

Respostas

2 BrianM.Scott Aug 18 2020 at 22:27

Você não está errado, mas seu resultado não contradiz a afirmação de que $$\operatorname{bits}(\lfloor x/2\rfloor)\le\operatorname{bits}(x)-1\,:$$ afinal, se $a=b$, então certamente também é verdade que $a\le b$. No entanto, devo admitir que não vejo por que o autor optou por afirmar a conclusão mais fraca, uma vez que a mais forte decorre facilmente de seus próprios 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*}$$

Sim, ele realmente deveria se restringir a inteiros $x\ge 2$ ou mencione isso $x=1$ é uma exceção, embora na prática eu duvide que o descuido cause muitos problemas.