正の整数とその半分の2進展開

Aug 18 2020

ワイスマンの「図解された数の理論」の第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}$このようなこと\開始{式*} K \ geqslant 2 \クワッド\テキスト{と} \クワッド2 ^ {K-1} \ leqslant X <2 ^ kの、\端{式*}であります$\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$

なぜ私は間違っているのですか?

回答

2 BrianM.Scott Aug 18 2020 at 22:27

あなたは間違っていませんが、あなたの結果は次の主張と矛盾しません $$\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$ 例外ですが、実際には見落としが多くの問題を引き起こすとは思えません。