नेक्स्ट नंबर: समान बिट गिनती, अगला बड़ा और छोटा (जावा)

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ५.४: धनात्मक पूर्णांक से वही संख्या वाली एक-बिट वाली अगली बड़ी और पिछली छोटी संख्या निकालो। अंतिम शून्य और एक गिनो, एक बिट पलटो, बाकी फिर सजाओ।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

तुम्हारे पास द्विआधारी अंकों की थैली है जिसमें 1 की संख्या तय है। उन्हें फिर से सजा सकते हो, लेकिन अतिरिक्त एक नहीं बना सकते और कोई एक फेंक भी नहीं सकते। जितनी संख्याएँ बन सकती हैं, उनमें वर्तमान मान से ठीक ऊपर कौन सी है और ठीक नीचे कौन सी? यही नेक्स्ट नंबर है: समान पॉपकॉउंट, पूर्णांक रेखा पर निकटतम पड़ोसी।

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

---

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

स्विचों की एक पंक्ति सोचो। कुछ ऑन (1), कुछ ऑफ (0)। इस पहेली का नियम: हर वैध पैटर्न में ऑन स्विचों की गिनती बिल्कुल वही रहनी चाहिए।

• अगला बड़ा पैटर्न वह सबसे छोटी संख्या है जो वर्तमान से बड़ी हो और ऑन की गिनती वही रखे।
• अगला छोटा पैटर्न वह सबसे बड़ी संख्या है जो वर्तमान से छोटी हो और ऑन की गिनती वही रखे।

ब्रूट फोर्स n+1, n+2, ... आज़माएगा और हर बार बिट गिनेगा। छोटे डेमो के लिए ठीक। इंटरव्यू में सीधा बिट निर्माण चाहते हैं: सही जगह एक बिट पलटो, फिर दिशा के हिसाब से बाकी एकों को समेटो।

---

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

इनपुट: धनात्मक int n (इंटरव्यू में ३२-बिट द्वि-पूरक पैटर्न समझो; जब तक न कहा जाए, धनात्मक पर रहो)।

आउटपुट:

• getNext(n): n से बड़ी सबसे छोटी संख्या जिसमें 1 बिटों की गिनती वही हो, या शब्द चौड़ाई में न मिले तो संकेत (जैसे -1)।
• getPrev(n): n से छोटी सबसे बड़ी संख्या जिसमें 1 बिटों की गिनती वही हो, या न मिले तो संकेत।

समान एक-बिट गिनती का मतलब समान पॉपकॉउंट: Integer.bitCount(result) == Integer.bitCount(n)।

उदाहरण:

न (द्विआधारी)	एक	अगला बड़ा	अगला छोटा
11011001111100 (१३९४८)	९	11011010001111 (१३९६७)	(मिलता है; नीचे चाल-विचार देखो)
10110 (२२)	३	11001 (२५)	10101 (२१)
10011100 (१५६)	४	10100011 (१६३)	10011010 (१५४)
1	१	10 (२)	कोई नहीं (-1 लौटाओ)
सिर्फ निचले क बिट पर एक, ऊपर खाली नहीं	क	अगर कोई शून्य ऊपर नहीं पलट सकता तो नहीं	ऊपर शून्य हों तो अक्सर मिलता है

कोड से पहले स्पष्ट करो:

• सिर्फ धनात्मक, या चिह्न बिट सहित पूरे ३२ बिट? (धनात्मक से शुरू; धनात्मक int के लिए व्यावहारिक ऊपरी बिट ३१ कहो।)
• अगर नेक्स्ट/प्रिव न हो? (-1 या अपवाद; एक चुनो और टिके रहो।)
• n == 0 मान्य? (शून्य एक: सिर्फ शून्य में शून्य एक। न नेक्स्ट, न प्रिव।)
• दोनों जवाब एक विधि में, या दो हेल्पर?

---

३. पहले सोचो

ब्रूट (वार्म-अप के लिए ठीक)

next = n + 1
while bitCount(next) != bitCount(n): next++

प्रिव के लिए नीचे की ओर वही विचार। छोटे न पर सही। सबसे खराब में गैप बड़ा हो सकता है, और तय शब्द पर ओवरफ्लो पर रुकना पड़ता है। आमतौर पर ओ(१) या ओ(शब्द आकार) बिट काम चाहते हैं।

अगले बड़े के लिए समझ

एक-गिनती बचाते हुए सबसे छोटा इज़ाफा चाहिए।

मतलब:

१. सबसे दायाँ गैर-अंतिम शून्य ढूँढो: सबसे निचला 0 जिसके दाएँ कम से कम एक 1 हो। उसका सूचकांक p। २. उस 0 को 1 कर दो। संख्या बढ़ी, अस्थायी रूप से एक 1 ज़्यादा। ३. p से नीचे सारे बिट साफ करो। ४. बकाया एक p के नीचे सबसे दाएँ रखो, लेकिन सिर्फ c1 - 1 (एक फ्लिप पहले ही p पर खर्च हो चुका)। इससे p के नीचे मान न्यूनतम रहता है।

p कैसे बिना अंधे स्कैन के:

• c0 = अंतिम 0 की गिनती (बिट ० से ऊपर)।
• c1 = उन शून्यों के बाद 1 की गिनती (एकों की दौड़)।
• फिर p = c0 + c1। बिट p उस एक-दौड़ के ठीक बाएँ वाला शून्य है।

अगले छोटे के लिए समझ

आईना:

१. अंतिम 1 गिनो (c1), फिर उनके ऊपर शून्य (c0)। २. स्थिति p = c0 + c1 सबसे दायाँ गैर-अंतिम एक है। ३. उस 1 को 0 करो (संख्या घटती है) और नीचे के बिट साफ करो। ४. c1 + 1 एक रखो मानक पैक से: (c1 + 1) एकों का ब्लॉक (c0 - 1) से खिसकाया।

अगर निचले एकों के ऊपर कोई शून्य नहीं (पैटर्न जैसे 000...00111), समान गिनती से छोटा नहीं जा सकते।

अंकगणितीय शॉर्टकट (वही गिनती)

जब c0 और c1 मिल जाएँ:

• अगला बड़ा: n + (1 << c0) + (1 << (c1 - 1)) - 1
• अगला छोटा: n - (1 << c1) - (1 << (c0 - 1)) + 1

पलट-और-फिर-सजा के बराबर। बिट चित्र समझाने के बाद दूसरी अमल अच्छी है।

---

४. जावा हल

गेटनेक्स्ट: समान बिट गिनती वाला अगला बड़ा

/**
 * Smallest number greater than n with the same number of 1 bits.
 * Returns -1 if none exists within a 32-bit positive pattern.
 */
int getNext(int n) {
    if (n <= 0) {
        return -1;
    }

    int c = n;
    int c0 = 0; // trailing zeros
    int c1 = 0; // ones right after those zeros

    // count trailing zeros
    while ((c & 1) == 0 && c != 0) {
        c0++;
        c >>>= 1;
    }
    // count ones after that
    while ((c & 1) == 1) {
        c1++;
        c >>>= 1;
    }

    // no larger number with same 1-count in 32-bit space
    // (e.g. 111...11000...0 with no non-trailing zero to flip)
    if (c0 + c1 == 31 || c0 + c1 == 0) {
        return -1;
    }

    int p = c0 + c1; // position of rightmost non-trailing zero

    // Flip the zero at p to one.
    n |= (1 << p);

    // Clear all bits to the right of p.
    n &= ~((1 << p) - 1);

    // Insert (c1 - 1) ones on the right.
    n |= (1 << (c1 - 1)) - 1;

    return n;
}

अंकगणितीय जुड़वाँ:

int getNextArithmetic(int n) {
    if (n <= 0) {
        return -1;
    }
    int c = n;
    int c0 = 0;
    int c1 = 0;
    while ((c & 1) == 0 && c != 0) {
        c0++;
        c >>>= 1;
    }
    while ((c & 1) == 1) {
        c1++;
        c >>>= 1;
    }
    if (c0 + c1 == 31 || c0 + c1 == 0 || c1 == 0) {
        return -1;
    }
    return n + (1 << c0) + (1 << (c1 - 1)) - 1;
}

गेटप्रिव: समान बिट गिनती वाला अगला छोटा

/**
 * Largest number less than n with the same number of 1 bits.
 * Returns -1 if none exists.
 */
int getPrev(int n) {
    if (n <= 0) {
        return -1;
    }

    int c = n;
    int c0 = 0; // zeros after the trailing ones
    int c1 = 0; // trailing ones

    // count trailing ones
    while ((c & 1) == 1) {
        c1++;
        c >>>= 1;
    }
    if (c == 0) {
        // pattern like 00...00111: no smaller with same ones
        return -1;
    }

    // count zeros after those ones
    while ((c & 1) == 0 && c != 0) {
        c0++;
        c >>>= 1;
    }

    int p = c0 + c1; // rightmost non-trailing one

    // Clear bits from p down through 0.
    n &= (-1 << (p + 1)); // same as ~0 << (p + 1)

    // Sequence of (c1 + 1) ones.
    int mask = (1 << (c1 + 1)) - 1;

    // Place that block as far right as allowed: leave (c0 - 1) zeros at the bottom.
    n |= mask << (c0 - 1);

    return n;
}

अंकगणितीय जुड़वाँ:

int getPrevArithmetic(int n) {
    if (n <= 0) {
        return -1;
    }
    int c = n;
    int c0 = 0;
    int c1 = 0;
    while ((c & 1) == 1) {
        c1++;
        c >>>= 1;
    }
    if (c == 0) {
        return -1;
    }
    while ((c & 1) == 0 && c != 0) {
        c0++;
        c >>>= 1;
    }
    if (c0 == 0) {
        return -1;
    }
    return n - (1 << c1) - (1 << (c0 - 1)) + 1;
}

c घुमाते समय >>> (बिना चिह्न शिफ्ट) इस्तेमाल करो ताकि ऊँचा 1 (चिह्न बिट) अंकगणितीय >> से लूप न लटकाए। इंटरव्यू के धनात्मक इनपुट पर दोनों चलते हैं; >>> बेहतर आदत है।

---

५. चाल-फिरताल

अगला बड़ा: १३९४८

n  = 11011001111100
       trailing zeros: 00  → c0 = 2
       then ones: 11111    → c1 = 5
       p = 7  (0-based from the right)

Flip bit 7:     11011011111100
Clear below 7:  11011010000000
Add c1-1 = 4 ones on the right:
                11011010001111  = 13967

जाँच: दोनों में नौ 1, और १३९४८ व १३९६७ के बीच किसी में नौ 1 नहीं।

अगला छोटा: १५६ (10011100)

n  = 10011100
       trailing ones: none → c1 = 0
       then zeros: 00      → c0 = 2
       next bit is 1, so p = 2

Clear from bit 2 down:  10011000
mask = (c1 + 1) ones = 1
shift by (c0 - 1) = 1:  10011010  = 154

हर में चार एक। १५५ में पाँच, इसलिए १५४ पड़ोसी है।

छोटा मामला: २२ (10110)

दिशा	गिनती	परिणाम द्विआधारी	दशमलव
नेक्स्ट	c०=१, c१=२, p=३	11001	२५
प्रिव	c१=०, c०=१, p=१	10101	२१

---

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

विषय	जवाब
समय	दौड़ गिनने में ओ(ब), ब = शब्द आकार (३२)। फ्लिप और मास्क ओ(१)।
अतिरिक्त जगह	ओ(१)
ब्रूट विकल्प	ओ(गैप) बढ़ोतरी; गैप बड़ा हो सकता है
नेक्स्ट नहीं	बिना पलटने योग्य गैर-अंतिम शून्य वाले पैटर्न (c0 + c1 की रक्षा)
प्रिव नहीं	सिर्फ नीचे एक भरे (c == 0 अंतिम एक गिनने के बाद)
n = 0	सिर्फ शून्य में शून्य एक; दोनों पर -1
चिह्न बिट	स्कैन में >>> पसंद; इंटरव्यू में धनात्मक रहो

आम गलतियाँ:

१. व्यापक मामलों में ऋणात्मक बीच-मान पर अंकगणितीय >>। २. एक-बटे-एक: ऊपर पलटने के बाद c1 एक डालना, c1 - 1 नहीं। ३. एक डालने से पहले p के नीचे साफ न करना (पुराने बिट गिनती बिगाड़ते हैं)। ४. अंतिम-दौड़ संरचना देखे बिना "हल नहीं" कहना। ५. "मान से अगला बड़ा" को "बिट घुमाकर अगला" समझना। यह समस्या पूर्णांक क्रम की है, घुमाव की नहीं।

कैसे बोलो:

१. दोहराओ: समान पॉपकॉउंट, निकटतम बड़ा और निकटतम छोटा। २. एक बिट-स्ट्रिंग खींचो। अंतिम शून्य, फिर एक, फिर फ्लिप स्थान चिह्नित करो। ३. पलटो, दाएँ साफ, एक फिर समेटो। ४. प्रिव के लिए आईना। ५. वैकल्पिक: दिखाओ अंकगणितीय रूप तुम्हारे उदाहरण पर मेल खाता है।

---

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

नेक्स्ट नंबर (समस्या ५.४) पूछता है: धनात्मक पूर्णांक से वही 1 बिट गिनती वाले अगले बड़े और अगले छोटे पूर्णांक निकालो।

१. अगला बड़ा: अंतिम शून्य (c0) फिर एक (c1) गिनो। स्थान p = c0 + c1 पर शून्य पलटो। p नीचे साफ। दाएँ c1 - 1 एक रखो। २. अगला छोटा: अंतिम एक (c1) फिर शून्य (c0) गिनो। p = c0 + c1 वाले एक को p से ० तक साफ कर के गिराओ। c0 - 1 से खिसकाकर c1 + 1 एक रखो। ३. अंकगणित: गिनती मिलने पर n + (1<<c0) + (1<<(c1-1)) - 1 और n - (1<<c1) - (1<<(c0-1)) + 1। ४. जब पैटर्न में जगह न हो तो संकेत लौटाओ (नेक्स्ट के लिए गैर-अंतिम शून्य नहीं, प्रिव के लिए गैर-अंतिम एक नहीं)। ५. बिट घुमाते समय बिना-चिह्न शिफ्ट पसंद करो।

अगर हाथ से १३९४८ से १३९६७ निकाल सको और समझा सको फ्लिप के बाद एक दाएँ क्यों बैठते हैं, तो ५.४ तुम्हारा है।

---

सीरीज़

• गाइड: सीटीसीआई सीरीज़ गाइड
• पिछला: फ्लिप बिट टू विन
• अगला: डिबगर