Développement binaire d'un entier positif et de sa moitié

Question

Je cite le chapitre 1 (page 29) de "Une théorie illustrée des nombres" de Weissman:

Si $x$ est un entier positif, écrivez $\mathrm{bits}(x)$ pour le nombre de bits dans le développement binaire de $x$. Rappeler que$\mathrm{bits}(x) = \lfloor \log_2(x) \rfloor + 1$; il s'ensuit que$\mathrm{bits}(\lfloor x/2 \rfloor) \leqslant \mathrm{bits}(x) - 1$.

Je ne comprends pas pourquoi c'est vrai; Je raisonne comme suit.

Si $x = 1$, puis $\left \lfloor \frac{x}{2} \right \rfloor = 0$. Nous avons donc$\mathrm{bits}(\left \lfloor \frac{x}{2} \right \rfloor) = \mathrm{bits}(x)$.

Si $x \geqslant 2$, alors il existe un unique $k \in \mathbb{Z}$tel que \ begin {équation *} k \ geqslant 2 \ quad \ text {et} \ quad 2 ^ {k-1} \ leqslant x <2 ^ k, \ end {équation *} soit$\mathrm{bits}(x) = k$. Par conséquent, nous avons$2^{k-2} \leqslant \frac{x}{2} < 2^{k-1}$, et le nombre de bits dans le développement binaire de $\lfloor \frac{x}{2} \rfloor$ est exactement $k - 1$, C'est $\mathrm{bits}(\left \lfloor \frac{x}{2} \right \rfloor) = \mathrm{bits}(x) - 1$.

Pourquoi ai-je tort?

Answer 1

Vous n'avez pas tort, mais votre résultat ne contredit pas l'affirmation selon laquelle $$\operatorname{bits}(\lfloor x/2\rfloor)\le\operatorname{bits}(x)-1\,:$$ après tout, si $a=b$, alors c'est certainement aussi vrai que $a\le b$. Cependant, je dois admettre que je ne vois pas pourquoi l'auteur a choisi d'énoncer la conclusion la plus faible, car la plus forte découle facilement de ses propres calculs:

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

Oui, il devrait vraiment soit se limiter aux entiers $x\ge 2$ ou mentionner que $x=1$ est une exception, même si, dans la pratique, je doute que la surveillance causera beaucoup de problèmes.