एक सकारात्मक पूर्णांक और उसके आधे का द्विआधारी विस्तार
मैं वीज़मैन के "एन इलस्ट्रेटेड थ्योरी ऑफ़ नंबर्स" के अध्याय 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 \ 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$ एक अपवाद है, हालांकि व्यवहार में मुझे संदेह है कि ओवरसाइट बहुत परेशानी पैदा करेगा।