इन्सर्शन: पूर्णांक एम को एन में बिट आई से जे तक बैठाओ (जावा)

टीएल;डीआर

समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।

दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ५.१: एन में बिट आई से जे साफ़ करो, एम को आई से खिसकाओ, फिर ओआर। बिट मास्क, क्लासिक उदाहरण की चाल, और जावा कोड।

जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

लंबी किताबों की शेल्फ सोचो (पूर्णांक N)। बीच में कुछ खाने नए सेट (M) के लिए आरक्षित हैं। वे खाने खाली करो, नई किताबें फिसलाओ, बाकी अकेला छोड़ो। यही बिट इन्सर्शन है: M के बिट N में बिट i से बिट j तक लिखना।

यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाले बिट मैनिपुलेशन वार्मअप का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ५, बिट मैनिपुलेशन, यहीं से शुरू।

१. रोज़मर्रा की उपमा

होटल की चाबी-कार्ड पर छोटी बत्तियों की कतार सोचो। कुछ पहले से जल रही या बुझी हैं (N)। मेहमान कोड (M) को उन जगहों की एक निश्चित खिड़की भरनी है, मान लो बत्ती i से बत्ती j तक (बिट ० दाईं ओर का सबसे कम महत्त्व वाला बिट है)।

हाथ से एक-एक बत्ती न पलटो अगर बचा जा सके। करो ये:

१. खिड़की की हर बत्ती बुझाओ (वे बिट साफ़ करो)। २. कोड इतना संरेखित करो कि उसका सबसे निचला बिट बत्ती i पर बैठे (M को i बाएँ खिसकाओ)। ३. ओआर से मिलाओ: जहाँ कोड जलना चाहे, जले; जहाँ बुझना चाहे, साफ़ खिड़की ० रहे; खिड़की के बाहर कुछ न बदले।

ये तीन कदम हर मज़बूत जवाब में आते हैं।

२. समस्या सादे शब्दों में

इनपुट: दो पूर्णांक N और M, और दो बिट सूचकांक i व j (दाईं ओर से, आधार ०)। इंटरव्यू में जब तक न कहा जाए, ३२-बिट int मानो।

आउटपुट: N जिसमें बिट i से j तक M के बिट से बदले गए हों। M का बिट 0 परिणाम की स्थिति i पर बैठता है। M के ऊँचे बिट j की ओर भरते हैं।

जो धारणाएँ ज़ोर से कहो:

खिड़की i..j इतनी चौड़ी है कि M के ज़रूरी बिट समा जाएँ (किताब: M i और j के बीच फिट)।
i <= j।
N में [i, j] के बाहर के बिट वही रहें।
फिट मान लिया तो j से ऊपर M के बिट विषय से बाहर; फिर भी कुछ लोग सुरक्षा के लिए M को खिड़की की चौड़ाई पर मास्क करते हैं।

क्लासिक उदाहरण (साफ़ दिखाने को बाइनरी; बिट ० सबसे दायाँ अंक):

N = 10000000000   (binary)
M = 10011
i = 2
j = 6

Result = 10001001100

इन्सर्ट के बाद परिणाम के बिट २-६ हैं 10011 (M का मान), और N का बाकी हिस्सा वैसा ही।

कोड से पहले साफ़ करो:

बिट ० एलएसबी (दायाँ) है? (इस समस्या में हाँ।)
साइन वाला int या अनसाइन? जावा में सब दो-की-पूरक साइन वाला है, पर शुद्ध बिट काम में ३२-बिट पैटर्न देखो।
M ठीक फिट हो या सिर्फ "कम से कम" चौड़ाई? (फिट मानो; अतिरिक्त मास्क वैकल्पिक।)
रिटर्न टाइप: N जितनी चौड़ाई (int, या जगह चाहिए तो long)।

३. पहले सोचो

गलत आदत: एम के बिट एक-एक करके लगाना

k को ० से j - i तक घुमा सकते हो, M का बिट k पढ़ो, N के बिट i + k पर लिखो। चलता है, पर इंटरव्यू मास्क वाला रास्ता चाहता है: रेंज साफ़ करो, संरेखित करो, ओआर। कम शाखाएँ, और मास्क समझ दिखती है।

सही आकार: साफ़, खिसकाओ, ओआर

१. N में बिट i से j साफ़ करो: मास्क उस रेंज में ०, बाहर १। २. M को i बाएँ खिसकाओ ताकि M का बिट ० बिट i पर बैठे। ३. साफ़ N और खिसकाया M का ओआर।

तीनों कदम स्थिर-चौड़ाई पूर्णांक पर ओ(१) शब्द संक्रियाएँ हैं।

साफ़ करने का मास्क बनाना

ऐसा कुछ चाहिए:

// for i=2, j=6 on a short word for illustration:
// ones, then zeros from j down to i, then ones again on the low side
// ...11110000011  (zeros in bits 2..6)

दो टुकड़ों में:

बाएँ वाले एक: j + 1 से ऊपर के बिट रखो।
left = ~0 << (j + 1)
जावा में ~0 सब १ (-1)। j + 1 बाएँ खिसकाने से बिट 0..j में शून्य आते हैं।
दाएँ वाले एक: बिट 0 से i - 1 तक रखो।
right = (1 << i) - 1
ये i निचले एक हैं। अगर i == 0 तो 0 (दाएँ कुछ नहीं रखना)।
मास्क: mask = left | right
सिर्फ बिट i..j पर शून्य, बाकी एक।
साफ़ एन: nCleared = N & mask
मिला हुआ: nCleared | (M << i)

जावा सावधानी: अगर j == 31 तो j + 1 == 32। int पर ३२ का शिफ्ट मॉड ३२ होता है (<< 32 कुछ नहीं करता)। अगर खिड़की ३२-बिट के सिरे तक पहुँचे तो शिफ्ट गणित के लिए long लो, या j == 31 पर left = 0। इंटरव्यू अक्सर j ३१ से नीचे रखते हैं, पर जाल बता दो।

४. जावा हल

/**
 * Insert M into N between bits i and j (inclusive).
 * Bit 0 is the least significant bit.
 * Assumes M fits in the window [i, j].
 */
int insertion(int N, int M, int i, int j) {
    // 1) Mask with 0s from bit i through bit j, 1s elsewhere.
    int allOnes = ~0;                 // 0xFFFFFFFF as a pattern
    int left = allOnes << (j + 1);    // 1s, then 0s from bit j downward
    int right = (1 << i) - 1;         // 1s in bits 0..i-1
    int mask = left | right;          // 0s only in [i, j]

    // 2) Clear the window in N.
    int nCleared = N & mask;

    // 3) Align M and merge.
    int mShifted = M << i;
    return nCleared | mShifted;
}

जब जे ३१ हो सकता है, ज़्यादा सुरक्षित

int insertionSafe(int N, int M, int i, int j) {
    int right = (1 << i) - 1;
    int left;
    if (j >= 31) {
        left = 0; // no bits above 31 on a 32-bit int
    } else {
        left = (~0) << (j + 1);
    }
    int mask = left | right;
    return (N & mask) | (M << i);
}

वैकल्पिक: एम को खिड़की की चौड़ाई तक काटो

अगर "एम फिट" पर पूरा भरोसा न हो:

int width = j - i + 1;
int mMasked = M & ((width >= 32) ? ~0 : (1 << width) - 1);
return (N & mask) | (mMasked << i);

फिर भी ओ(१)। अगर M के ऊँचे कचरा बिट पूछें तो अच्छा फॉलो-अप।

५. क्लासिक उदाहरण की चाल

N = 10000000000   (binary)   // think of this as bits; leading 1 is bit 10
M = 10011
i = 2, j = 6

कदम क: साफ़ मास्क

left = ~0 << 7 → नीचे ७ बिट ०, ऊपर १
right = (1 << 2) - 1 → बाइनरी में 11
mask = left | right → बिट २-६ पर शून्य, बाकी एक

कदम ख: एन साफ़

nCleared = N & mask
N के बिट २-६ शून्य हो जाते हैं। क्लासिक चित्र में वह बीच पहले से ० था, इसलिए दिखने में वही, पर जब वहाँ १ थे तब यह कदम ज़रूरी।

कदम ग: खिसकाओ और ओआर

M << 2 = 10011 दो जगह बाएँ → बिट २-६ में 10011
साफ़ N में ओआर → 10001001100

कोड में जाँच:

int N = 0b10000000000;
int M = 0b10011;
int result = insertion(N, M, 2, 6);
// result binary: 10001001100
// Integer.toBinaryString(result) -> "10001001100"

एक और तेज़ जाँच: अगर N की खिड़की में कचरा १ थे, साफ़ पहले मिटाता है ताकि ओआर वहाँ चिपका १ न छोड़ दे जहाँ M ० चाहता था।

// N has 1s in bits 2-6; after insert they must match M, not the old 1s
int dirty = 0b10001111100;
int cleaned = insertion(dirty, 0b10011, 2, 6);
// still 10001001100 in the low part of interest

६. जटिलता, किनारे, इंटरव्यू सुझाव

विषय	जवाब
समय	स्थिर-चौड़ाई `int` पर ओ(१)
अतिरिक्त जगह	ओ(१)
बिट क्रम	० = एलएसबी (दायाँ)
`i == 0`	`right = 0`; खिड़की सबसे कम महत्त्व वाले बिट से
`i == j`	एक बिट की खिड़की; साफ़ फिट के लिए `M` ० या १
`j == 31`	जावा `int` पर `<< (j + 1)` सावधान
ऋणात्मक	वही बिट ऑप; प्रिंट तक दशमलव में मत सोचो

आम गलतियाँ:

left बनाते समय j + 1 पर एक-बिट चूक।
M को i की जगह j से खिसकाना।
साफ़ के बाद ओआर की जगह एंड से मिलाना (एंड M के १ को N के शून्य पर बुझा देगा)।
पहले साफ़ भूलना: अकेला ओआर N का १ कभी M के ० वाली जगह पर ० नहीं बना सकता।

कैसे बोलो:

१. दोहराओ: "एन के बिट आई से जे तक एम से बदलो; एम का एलएसबी आई पर।" २. छोटी बिट स्ट्रिंग खींचो, खिड़की चिह्नित करो। ३. साफ़, शिफ्ट, ओआर कहो। ४. बाएँ-दाएँ आधे से मास्क लिखो। ५. दस सेकंड बचें तो j == 31 वाला जावा शिफ्ट जाल बताओ।

७. दोस्त को समझाओ सार

इन्सर्शन (समस्या ५.१) पूछती है: पूर्णांक M को पूर्णांक N में इस तरह बैठाओ कि M बिट i से j घेरे।

१. बिट i..j पर ० और बाकी १ वाला मास्क: left | right, जहाँ left = ~0 << (j + 1) और right = (1 << i) - 1। २. साफ़: N & mask। ३. संरेखण: M << i। ४. मिलान: साफ़ N ओआर खिसकाया M। ५. अगर j ३१ हो तो जावा शिफ्ट देखो। वैकल्पिक: M को खिड़की चौड़ाई पर मास्क।

क्लासिक 10000000000 / 10011 / i=2,j=6 खींच सको और ओआर से पहले साफ़ क्यों ज़रूरी बता सको, तो अध्याय ५ की शुरुआत तुम्हारी है।