การขยายฐานสองของจำนวนเต็มบวกและครึ่งหนึ่ง
ฉันอ้างจากบทที่ 1 (หน้า 29) ใน "An Illustrated Theory of Numbers" ของ Weissman:
ถ้า $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 \ quad \ text {และ} \ 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$.
ทำไมฉันผิด?
คำตอบ
คุณไม่ผิด แต่ผลลัพธ์ของคุณไม่ได้ขัดแย้งกับคำยืนยันนั้น $$\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$ เป็นข้อยกเว้นแม้ว่าในทางปฏิบัติฉันสงสัยว่าการกำกับดูแลจะทำให้เกิดปัญหามาก