양의 정수와 그 절반의 이진 확장

Question

나는 Weissman의 "An Illustrated Theory of Numbers"의 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$.

내가 왜 틀렸어?

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$ 예외이지만 실제로는 감독이 많은 문제를 일으킬 것이라고 의심합니다.