समस्या
n को binary में ठीक width बिट्स में लिखिए, ज़रूरत हो तो आगे शून्य जोड़कर, फिर उन बिट्स को उलटे क्रम में पढ़िए। n = 6 और width = 4 के लिए 6 है 0110, उलटने पर फिर से 0110, इसलिए परिणाम 6 है। width = 8 के लिए यह 00000110 है, उलटने पर 01100000, यानी 96। बिट्स उलटने का इस्तेमाल fast Fourier transform और कुछ hashing तरकीबों में होता है।
reverse_the_bits(n, width) लिखिए।
इनपुट
n: एक ऋणेतर पूर्णांक जो width बिट्स में समा जाता है।
width: कितने बिट्स उलटने हैं।
आउटपुट
उलटे गए width-बिट पैटर्न का मान लौटाइए।
सीमाएँ
1 ≤ width ≤ 63
0 ≤ n < 2^width
उदाहरण
इनपुट:
n = 6
width = 8
अपेक्षित आउटपुट:
expected = 96
इनपुट:
long long n = 6;
long long width = 8;
अपेक्षित आउटपुट:
long long expected = 96;
इनपुट:
long n = 6;
long width = 8;
अपेक्षित आउटपुट:
long expected = 96;
व्याख्या
8 बिट्स में 6 है 00000110; उलटने पर 01100000 मिलता है, जो 96 है।
इनपुट:
n = 1
width = 3
अपेक्षित आउटपुट:
expected = 4
इनपुट:
long long n = 1;
long long width = 3;
अपेक्षित आउटपुट:
long long expected = 4;
इनपुट:
long n = 1;
long width = 3;
अपेक्षित आउटपुट:
long expected = 4;
व्याख्या
1 है 001; उलटने पर 100 मिलता है, जो 4 है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
width बार दोहराइए: n का सबसे निचला बिट लीजिए, फिर n को दाईं ओर shift कीजिए।
संकेत 2
अभी लिया गया बिट जोड़ने से पहले परिणाम को एक स्थान बाईं ओर shift कीजिए।
संकेत 3
n के शुरुआती शून्य परिणाम के आख़िरी शून्य बन जाते हैं, और loop की तय गिनती इसे अपने आप संभाल लेती है।
अपेक्षित जटिलता
समय O(width), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।