Двоичное разложение положительного целого числа и его половины

Question

Я цитирую главу 1 (стр. 29) в «Иллюстрированной теории чисел» Вайсмана:

Если $x$ положительное целое число, напишите $\mathrm{bits}(x)$ для количества битов в двоичном разложении $x$. Напомним, что$\mathrm{bits}(x) = \lfloor \log_2(x) \rfloor + 1$; это следует из того$\mathrm{bits}(\lfloor x/2 \rfloor) \leqslant \mathrm{bits}(x) - 1$.

Я не понимаю, почему это правда; Я рассуждаю следующим образом.

Если $x = 1$, тогда $\left \lfloor \frac{x}{2} \right \rfloor = 0$. Итак, у нас есть$\mathrm{bits}(\left \lfloor \frac{x}{2} \right \rfloor) = \mathrm{bits}(x)$.

Если $x \geqslant 2$, то существует единственный $k \in \mathbb{Z}$такое, что \ begin {уравнение *} k \ geqslant 2 \ quad \ text {and} \ quad 2 ^ {k-1} \ leqslant x <2 ^ k, \ end {уравнение *}, то есть$\mathrm{bits}(x) = k$. Следовательно, мы имеем$2^{k-2} \leqslant \frac{x}{2} < 2^{k-1}$, а количество битов в двоичном разложении $\lfloor \frac{x}{2} \rfloor$ точно $k - 1$, то есть $\mathrm{bits}(\left \lfloor \frac{x}{2} \right \rfloor) = \mathrm{bits}(x) - 1$.

Почему я не прав?

Answer 1

Вы не ошиблись, но ваш результат не противоречит утверждению, что $$\operatorname{bits}(\lfloor x/2\rfloor)\le\operatorname{bits}(x)-1\,:$$ в конце концов, если $a=b$, то верно и то, что $a\le b$. Однако я должен признать, что не понимаю, почему автор решил сформулировать более слабый вывод, поскольку более сильный легко следует из его собственных расчетов:

$$\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*}$$

Да, ему действительно следовало бы ограничиться целыми числами $x\ge 2$ или упомянуть, что $x=1$ является исключением, хотя на практике я сомневаюсь, что надзор доставит много хлопот.