टीएल;डीआर
- समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
- दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ५.७: पूर्णांक में हर विषम-सम बिट जोड़े को अदला-बदली करो। विषम और सम मास्क, एक-एक दिशा में शिफ्ट, फिर दोनों आधे भागों का ओआर।
- जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।
३२ लोगों को ० से ३१ नंबर वाली जगहों पर खड़ा करो। जगह ० और १ अदलें। २ और ३ अदलें। ४ और ५, और आगे। सब एक साथ हिलें। कोई अपनी जोड़ी के पार न जाए। यही पूर्णांक के बिट्स पर पेयरवाइज़ स्वैप है: हर सम बिट बगल वाले विषम बिट से जगह बदलता है।
यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली बिट प्रश्नों का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ५, बिट मैनिपुलेशन, समस्या ५.७।
१. रोज़मर्रा की उपमा
स्विच की एक कतार सोचो। स्विच जोड़ों में हैं: (०, १), (२, ३), (४, ५), ... हर जोड़े में तुम अदला-बदली करते हो कि कौन सा भौतिक स्विच अपने साथी की ऑन/ऑफ अवस्था "रखता" है। अगर ० चालू था और १ बंद, तो बाद में ० बंद और १ चालू। बाकी जोड़े भी साथ-साथ वही करते हैं।
पूरी कतार उलटी नहीं होती। पूरा शब्द एक बिट घूमता नहीं। सिर्फ हर बगल की जोड़ी के अंदर अदल-बदल।
कागज़ पर यह १६ जोड़ों का लूप लगता है। बिट्स में मास्क से कुछ ही निर्देशों में हो जाता है।
२. समस्या सादे शब्दों में
इनपुट: ३२-बिट int मान x (चौड़ाई स्थिर मानो)।
आउटपुट: ऐसा int जहाँ बिट 0 और बिट 1 अदले, 2 और 3, 4 और 5, और इसी तरह 30 और 31 तक।
नाम (एलएसबी = बिट ०):
- सम बिट: स्थान
0, 2, 4, ..., 30 - विषम बिट: स्थान
1, 3, 5, ..., 31
पेयरवाइज़ स्वैप: हर i के लिए 0, 2, 4, ... में, स्थान i और i + 1 के बिट अदला-बदली।
उदाहरण (साफ देखने के लिए ८ बिट; विचार ३२ तक बढ़ता है):
| इनपुट बिट (एमएसबी→एलएसबी) | पेयरवाइज़ स्वैप के बाद | क्यों |
|---|---|---|
0101 0110 |
1010 1001 |
हर जोड़ी (b1 b0) बनती है (b0 b1) |
0000 0001 (१) |
0000 0010 (२) |
बिट ० गया बिट १ पर |
0000 0010 (२) |
0000 0001 (१) |
बिट १ गया बिट ० पर |
1111 1111 |
1111 1111 |
सब एक: स्वैप कुछ नहीं बदलता |
0000 0000 |
0000 0000 |
शून्य शून्य ही रहता है |
एक जोड़ी: इनपुट ... ab (a = विषम बिट, b = सम बिट) बनता है ... ba।
कोड से पहले साफ करो:
- बिट ० सबसे कम महत्वपूर्ण है? (हाँ, इस पोस्ट में और सामान्य जावा
intबात में।) - जावा में साइन वाला
int? हाँ। विषम आधे को नीचे ले जाते समय बिना साइन वाला राइट शिफ्ट>>>पसंद करो, ताकि साइन बिट ऊपर एक भर न दे। - क्या वे ओ(१) बिट ऑपरेशन चाहते हैं, १६-इटरेशन लूप नहीं? जब कहते हैं "जितने कम निर्देश संभव", तब मास्क वाला रूप चाहिए।
३. पहले सोचो
सादा लूप
i = 0; i < 32; i += 2 के लिए:
१. बिट i और बिट i + 1 पढ़ो।
२. बिट i को स्थान i + 1 पर लिखो, बिट i + 1 को स्थान i पर।
चलता है। करीब १६ चक्कर, हर एक में शिफ्ट और मास्क। साफ, पर "कम निर्देश" का जवाब नहीं।
बेहतर विचार: दोनों आधे एक साथ हिलाओ
अगर तुम:
१. सिर्फ विषम बिट निकालो, उन्हें एक स्थान दाएँ शिफ्ट करो (सम स्लॉट पर गिरें)। २. सिर्फ सम बिट निकालो, उन्हें एक स्थान बाएँ शिफ्ट करो (विषम स्लॉट पर गिरें)। ३. दोनों नतीजों का ओआर करो।
तो हर जोड़ी समानांतर अदलती है। कोई लूप नहीं।
दो मास्क चाहिए:
- विषम मास्क
0xaaaaaaaa= द्विआधारी1010 1010 ... 1010। सिर्फ विषम स्थानों पर एक। - सम मास्क
0x55555555= द्विआधारी0101 0101 ... 0101। सिर्फ सम स्थानों पर एक।
याद रखो: 0xA है 1010, 0x5 है 0101। आठ हेक्स अंक ३२ बिट ढकते हैं।
x = ... a b a b a b a b (a = विषम, b = सम)
x & 0xAA.. = ... a 0 a 0 a 0 a 0
>>> 1 = ... 0 a 0 a 0 a 0 a (विषम → सम स्लॉट)
x & 0x55.. = ... 0 b 0 b 0 b 0 b
<< 1 = ... b 0 b 0 b 0 b 0 (सम → विषम स्लॉट)
OR = ... b a b a b a b a (जोड़ी अदल गई)
पूरा एल्गोरिदम यही है।
विषम आधे के लिए >> क्यों नहीं?
जावा में >> साइन बढ़ाता है। अगर बिट ३१ एक है, x >> 1 ऊपर एक भरता है। तुम्हें सिर्फ चुने विषम बिट एक कदम नीचे चाहिए। मास्क के बाद >>> (लॉजिकल राइट शिफ्ट) इस्तेमाल करो।
४. जावा समाधान
/**
* Swap odd and even bits of a 32-bit int.
* Bit 0 <-> 1, bit 2 <-> 3, ..., bit 30 <-> 31.
*/
int swapOddEvenBits(int x) {
int oddsMovedRight = (x & 0xaaaaaaaa) >>> 1;
int evensMovedLeft = (x & 0x55555555) << 1;
return oddsMovedRight | evensMovedLeft;
}
एक पंक्ति (वही ऑपरेशन):
int swapOddEvenBits(int x) {
return ((x & 0xaaaaaaaa) >>> 1) | ((x & 0x55555555) << 1);
}
हेक्स लिटरल ठीक हैं। अगर नाम चाहिए:
private static final int ODD_BITS = 0xaaaaaaaa; // 1010...
private static final int EVEN_BITS = 0x55555555; // 0101...
int swapOddEvenBits(int x) {
return ((x & ODD_BITS) >>> 1) | ((x & EVEN_BITS) << 1);
}
वैकल्पिक: छोटे मान से चलकर देखो
लो x = 0b_0000_0000_0000_0000_0000_0000_0010_0110, यानी दशमलव 38।
३८ के निचले ८ बिट, एमएसबी→एलएसबी 00100110 (दाएँ बिट ० = ०):
| कदम | निचले ८ बिट | नोट |
|---|---|---|
x |
00100110 |
bit०=०, bit१=१, bit२=१, bit३=०, bit४=०, bit५=१, bit६=०, bit७=० |
x & 0xAA |
00100010 |
सिर्फ विषम स्थान |
>>> 1 |
00010001 |
विषम सम स्लॉट में |
x & 0x55 |
00000100 |
सिर्फ सम स्थान (बिट २) |
<< 1 |
00001000 |
सम विषम स्लॉट में |
| ओआर | 00011001 |
मान २५ |
हाथ से जोड़ी जाँच:
- बिट (१,०):
10→01 - बिट (३,२):
01→10 - बिट (५,४):
10→01 - बिट (७,६):
00→00
नतीजा निचले ८: 00011001। मेल खाता है।
५. जटिलता और "कम निर्देश"
| तरीका | समय | अतिरिक्त जगह | निर्देश का अहसास |
|---|---|---|---|
| १६ जोड़ों का लूप | ओ(१) (स्थिर ३२ बिट), ज़्यादा ऑपरेशन | ओ(१) | कई शिफ्ट/मास्क |
| दो मास्क + शिफ्ट + ओआर | ओ(१) | ओ(१) | करीब ५ बिट ऑपरेशन |
इंटरव्यू में मास्क वाला रूप मायने रखता है, बिग-ओ नहीं। बत्तीस दोनों तरफ स्थिरांक है। "जितने कम निर्देश संभव" का मतलब: शब्द-स्तर मास्क काम करे तो बिट-बिट मत घूमो।
६४-बिट long पर वही तरीका: 0xaaaaaaaaaaaaaaaaL और 0x5555555555555555L।
६. किनारे के मामले और आम गलतियाँ
- सब शून्य / सब एक → पहचान। स्वैप मान नहीं बदलता।
- ऋणात्मक संख्याएँ → सिर्फ बिट पैटर्न। विषम आधे पर
>>>सही रखता है; खाली जगहों में साफ शून्य चाहिए तो अंकगणितीय>>मत लगाओ। - पूरे नंबर पर सिर्फ
<< 1→ दो से गुणा / सब कुछ बाएँ, पेयरवाइज़ स्वैप नहीं। - बगल के बाइट या निबल अदलना → दूसरी समस्या। पेयरवाइज़ स्वैप सिर्फ बिट जोड़ियाँ।
- गलत मास्क → एलएसबी = बिट ० हो तो विषम के लिए
0xaaaaaaaa, सम के लिए0x55555555। - ओआर भूलना → सिर्फ आधे बिट बचते हैं।
- पढ़ते-पढ़ते बदलना → अभी चाहिए बिट मिट सकता है; नया नतीजा बनाओ।
छोटा स्मोक टेस्ट:
System.out.println(swapOddEvenBits(0)); // 0
System.out.println(swapOddEvenBits(1)); // 2
System.out.println(swapOddEvenBits(2)); // 1
System.out.println(swapOddEvenBits(38)); // 25
System.out.println(swapOddEvenBits(0xffffffff)); // -1 (सारे बिट अभी भी एक)
System.out.println(swapOddEvenBits(0xaaaaaaaa)); // 0x55555555
System.out.println(swapOddEvenBits(0x55555555)); // 0xaaaaaaaa
अगर यादृच्छिक int पर swap(swap(x)) == x, तो फ़ंक्शन इनवोल्यूशन है, जैसा पेयरवाइज़ स्वैप होना चाहिए। यूनिट टेस्ट में सस्ता चेक।
७. दोस्त को समझाने वाला सार
पेयरवाइज़ स्वैप पूछता है: बिट ० को १ से, २ को ३ से, और आगे अदला-बदली, लगभग बिना निर्देशों के।
१. विषम बिट मास्क 0xaaaaaaaa, दाएँ १ (>>>)।
२. सम बिट मास्क 0x55555555, बाएँ १।
३. दोनों आधे का ओआर।
४. हर जोड़ी समानांतर हिलती है। जोड़ों पर लूप नहीं।
५. लॉजिकल >>> इस्तेमाल करो ताकि ऊपरी एक गलत तरह से एक न भरे।
८-बिट उदाहरण खींच सको, दोनों मास्क याद से नाम ले सको, और यहाँ >>> क्यों >> से बेहतर बता सको, तो समस्या ५.७ तुम्हारी है। अध्याय में आगे: बिट-पैक स्क्रीन बफ़र में क्षैतिज रेखा खींचना।
सीरीज़
- गाइड: सीटीसीआई सीरीज़ गाइड
- पिछला: कन्वर्शन
- अगला: ड्रॉ लाइन