Pozitif bir tamsayının ve yarısının ikili açılımı

Question

Weissman'ın "Resimli Sayılar Teorisi" ndeki 1. Bölümden (sayfa 29) alıntı yapıyorum:

Eğer $x$ pozitif bir tam sayıdır, yazın $\mathrm{bits}(x)$ ikili açılımındaki bit sayısı için $x$. Hatırlamak$\mathrm{bits}(x) = \lfloor \log_2(x) \rfloor + 1$; onu takip eder$\mathrm{bits}(\lfloor x/2 \rfloor) \leqslant \mathrm{bits}(x) - 1$.

Bunun neden doğru olduğunu anlamıyorum; Ben aşağıdaki gibi muhakeme ediyorum.

Eğer $x = 1$, sonra $\left \lfloor \frac{x}{2} \right \rfloor = 0$. Böylece sahibiz$\mathrm{bits}(\left \lfloor \frac{x}{2} \right \rfloor) = \mathrm{bits}(x)$.

Eğer $x \geqslant 2$o zaman benzersiz bir $k \in \mathbb{Z}$öyle ki \ başlar {denklem *} k \ geqslant 2 \ dört \ metni {ve} \ dört 2 ^ {k-1} \ leqslant x <2 ^ k, \ ucu {denklem *} olduğu$\mathrm{bits}(x) = k$. Bu nedenle, biz var$2^{k-2} \leqslant \frac{x}{2} < 2^{k-1}$ve ikili açılımındaki bit sayısı $\lfloor \frac{x}{2} \rfloor$ tam olarak $k - 1$, yani $\mathrm{bits}(\left \lfloor \frac{x}{2} \right \rfloor) = \mathrm{bits}(x) - 1$.

Neden hatalıyım

Answer 1

Yanlış değilsiniz, ancak sonucunuz şu iddiayla çelişmiyor: $$\operatorname{bits}(\lfloor x/2\rfloor)\le\operatorname{bits}(x)-1\,:$$ sonuçta eğer $a=b$o zaman kesinlikle doğru $a\le b$. Bununla birlikte, yazarın neden daha zayıf sonucu ifade etmeyi seçtiğini anlamadığımı itiraf etmeliyim, çünkü güçlü olan kendi hesaplamalarından kolayca çıkar:

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

Evet, kendini tam sayılarla sınırlandırması gerekiyor. $x\ge 2$ veya bundan bahset $x=1$ bir istisnadır, ancak uygulamada gözetimin çok fazla soruna neden olacağından şüpheliyim.