डिबगर: ((n & (n-1)) == 0) असल में क्या जाँचता है (जावा)

टीएल;डीआर

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

दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली समस्या ५.५: साबित करो कि n & (n-१) तभी शून्य होता है जब n में ज़्यादा से ज़्यादा एक बिट १ हो। दो की घात, शून्य का जाल, बाइनरी चलते उदाहरण और जावा कोड।

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

कोई कोड रिव्यू में यह पंक्ति चिपकाकर पूछता है: ये किस काम की है?

((n & (n - 1)) == 0)

लगता है पहेली। कोई लूप नहीं। कोई भाग नहीं। एक घटाव, एक एंड, एक तुलना। छोटा जवाब: यह सत्य है जब n में ज़्यादा से ज़्यादा एक बिट १ हो। धनात्मक पूर्णांकों के लिए यही है "क्या n दो की घात है?" (१, २, ४, ८, १६, ...)। शून्य भी व्यंजक को सत्य बनाता है, इसलिए असल कोड में अक्सर n > 0 जोड़ते हैं।

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

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

एक गलियारा सोचो जिसमें स्विच लगे हैं। हर स्विच एक बिट: ऑन = १, ऑफ = ०। दो की घात वह गलियारा है जहाँ ठीक एक बत्ती जल रही हो। एक लैंप, कोई भी जगह। वही १ (सिर्फ सबसे दायाँ), २ (अगला), ४, ८, और आगे। दो बत्तियाँ जलें तो संख्या दो अलग घातों का योग है, शुद्ध दो की घात नहीं।

चालाकी: सबसे दाईं जलती बत्ती बुझा दो, पूरा गलियारा घूमे बिना।

यही n & (n - 1) करता है। एक घटाने से सबसे निचले १ से लेकर दाईं तरफ़ के शून्यों तक बिट पलटते हैं। मूल n से एंड करने पर वह सबसे निचला १ मर जाता है, ऊँचे बिट ज्यों के त्यों।

अगर सिर्फ एक बत्ती थी, बुझाने के बाद अँधेरा: परिणाम ०।
अगर दो या ज़्यादा थीं, सबसे दाईं मारने के बाद बाकी बचती हैं: परिणाम ० नहीं।

तो ((n & (n - 1)) == 0) पूछता है: "सबसे निचली जलती बत्ती बुझाई तो क्या गलियारा अँधेरा है?" यानी "शून्य या एक बिट सेट था?"

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

इनपुट: एक पूर्णांक n (इंटरव्यू में अक्सर गैर-ऋणात्मक int, या कम से कम यह कह दो)।

काम: बताओ यह व्यंजक क्या जाँचता है, और कब इस्तेमाल करोगे:

(n & (n - 1)) == 0

सादे शब्दों में मतलब:

सत्य जब n में शून्य या एक बिट १ हो (गैर-ऋणात्मक मानों पर जैसे उम्मीद है)।
n > 0 पर यह बराबर है: n दो की घात है।
n == 0 पर भी व्यंजक सत्य है (० & (-१) == ० टूज़ कम्प्लीमेंट में), पर ० दो की घात नहीं।

उदाहरण (धनात्मक पक्ष):

`n`	बाइनरी (निचले बिट)	`n - 1`	`n & (n - 1)`	व्यंजक	दो की घात?
१	`0001`	`0000`	`0000`	सत्य	हाँ
२	`0010`	`0001`	`0000`	सत्य	हाँ
३	`0011`	`0010`	`0010`	असत्य	नहीं
४	`0100`	`0011`	`0000`	सत्य	हाँ
५	`0101`	`0100`	`0100`	असत्य	नहीं
६	`0110`	`0101`	`0100`	असत्य	नहीं
८	`1000`	`0111`	`0000`	सत्य	हाँ
०	`0000`	सब १	`0000`	सत्य	नहीं (जाल)

कोड से पहले पूछो:

शून्य को खास मानें? (हाँ: "दो की घात" के लिए n > 0 ज़रूरी।)
ऋणात्मक? जावा में int साइन्ड है। दो की घात धनात्मक परिमाण पर। n <= 0 अस्वीकार करो।
३२ या ६४ बिट? चाल int और long दोनों पर एक जैसी।
सिर्फ व्याख्या या हेल्पर मेथड? दोनों आते हैं। यह समस्या अक्सर "ये क्या जाँचता है?" है, "शून्य से बनाओ" नहीं।

३. पहले सोचो

बाइनरी में दो की घात कैसी दिखती है

हर धनात्मक दो की घात एक अकेला १ और फिर शून्य:

 1 = 0000 0001
 2 = 0000 0010
 4 = 0000 0100
 8 = 0000 1000
16 = 0001 0000

बाकी हर धनात्मक पूर्णांक में कम से कम दो १ बिट होते हैं, या मिली-जुली बनावट (जैसे 6 = 0110, 7 = 0111, 12 = 1100)।

तो "दो की घात है" = n > 0 पर "ठीक एक बिट सेट"।

एक क्यों घटाएँ, फिर एंड

n = 12 लो (निचले बिट में 1100)। सबसे निचला सेट बिट बिट २ है (मान ४)।

n     = ... 1100
n - 1 = ... 1011
AND   = ... 1000   // सबसे निचला १ गया; ऊँचा १ बचा

n = 8 (1000):

n     = ... 1000
n - 1 = ... 0111
AND   = ... 0000   // सिर्फ एक १ था; अब कोई नहीं

ज़ोर से बोलने लायक नियम:

n & (n - 1) संख्या n का सबसे कम महत्वपूर्ण १-बिट साफ़ करता है।

अगर साफ़ करने के बाद शून्य मिले, तो कोई दूसरा १ नहीं बचा। या n शून्य था, या ठीक एक १ था।

यह "डिबगर" सवाल क्यों पसंद आता है

इंटरव्यूअर इसे इसलिए पसंद करते हैं:

१. या तो सबसे निचले बिट वाली चाल पता है, या कागज़ पर कुछ उदाहरणों से खुद खोज लेते हो। २. शून्य वाला किनारा याद करने वालों को समझने वालों से अलग करता है। ३. बिट लूप या लाइब्रेरी काउंट से कम शाखाओं के साथ ओ(१) है (हालाँकि Integer.bitCount(n) == 1 पठनीय विकल्प है)।

और तरीके जो काम करते हैं

लूप / बिट गिनती: सेट बिट गिनो; गिनती १ हो तो दो की घात। कुछ पाठकों के लिए साफ़।
दो से भाग: जब तक सम, दो से भाग; अंत में १। शून्य और ऋणात्मक पर गलती आसान।
n > 0 && (n & -n) == n: एक और क्लासिक। n & -n सबसे निचला सेट बिट अलग करता है। अगर वह n के बराबर, तो सिर्फ वही बिट था।

इस समस्या पर n & (n - 1) समझाने पर टिके रहो।

४. जावा समाधान

सिर्फ व्याख्या वाला रूप (व्यंजक क्या जाँचता है)

// सत्य जब n में ज़्यादा से ज़्यादा एक बिट सेट हो (n == 0 शामिल)।
boolean atMostOneBitSet(int n) {
    return (n & (n - 1)) == 0;
}

दो की घात (जो लगभग हमेशा चाहिए)

/**
 * n धनात्मक दो की घात हो (1, 2, 4, 8, ...) तो सत्य लौटाता है।
 * n & (n - 1) सबसे निचला सेट बिट साफ़ करता है, इसी पर टिकी है।
 */
boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

`long` पर वही विचार

boolean isPowerOfTwo(long n) {
    return n > 0 && (n & (n - 1)) == 0;
}

पठनीय विकल्प (प्रोडक्शन में अच्छा; इंटरव्यू में ज़िक्र करो)

boolean isPowerOfTwoBitCount(int n) {
    return n > 0 && Integer.bitCount(n) == 1;
}

अक्सर मास्क वाला रूप भी चाहते हैं ताकि लाइब्रेरी के बिना बिट समझ साबित हो।

वैकल्पिक: सबसे निचला सेट बिट अलग करना (संबंधित चाल)

// n का सबसे निचला १-बिट अलग करता है (n != 0 पर)।
int lowestSetBit(int n) {
    return n & -n;
}

boolean isPowerOfTwoIsolate(int n) {
    return n > 0 && (n & -n) == n;
}

दो की घात के हाँ/नहीं जवाब n & (n - 1) जैसे ही, अलग छोटी अभिव्यक्ति। दोनों नाम जानना फायदेमंद।

५. क्लासिक मामलों की सैर

मामला अ: दो की घात (`n = 16`)

n        = 0001 0000
n - 1    = 0000 1111
n & (n-1)= 0000 0000   → व्यंजक सत्य
n > 0    → isPowerOfTwo सत्य

मामला ब: दो की घात नहीं (`n = 10`)

n        = 0000 1010
n - 1    = 0000 1001
n & (n-1)= 0000 1000   → शून्य नहीं → असत्य

दो १-बिट (८ और २)। सबसे निचला साफ़ करने पर ८ बचता है।

मामला स: शून्य का जाल (`n = 0`)

n        = 0000 0000
n - 1    = 1111 1111   // int पर: -1, सारे बिट 1
n & (n-1)= 0000 0000   → व्यंजक सत्य, पर दो की घात नहीं

हमेशा कहो: कच्चा व्यंजक ० स्वीकार करता है; दो-की-घात हेल्पर को अस्वीकार करना चाहिए।

मामला द: एक (`n = 1`)

1 यानी 2^0। एक बिट सेट। व्यंजक सत्य। isPowerOfTwo सत्य।

लोग भूल जाते हैं कि १ भी दो की घात है। है।

त्वरित स्मोक टेस्ट

public static void main(String[] args) {
    int[] samples = {0, 1, 2, 3, 4, 5, 6, 7, 8, 15, 16, 17, 32};
    for (int n : samples) {
        boolean raw = (n & (n - 1)) == 0;
        boolean pow = n > 0 && (n & (n - 1)) == 0;
        System.out.println(n + " raw=" + raw + " powerOfTwo=" + pow);
    }
    // 0  raw=true  powerOfTwo=false
    // 1  raw=true  powerOfTwo=true
    // 2  raw=true  powerOfTwo=true
    // 3  raw=false powerOfTwo=false
    // ...
}

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

विषय	जवाब
समय	ओ(१) शब्द संक्रियाएँ
अतिरिक्त जगह	ओ(१)
मूल पहचान	`n & (n - 1)` सबसे निचला सेट बिट साफ़ करता है
दो की घात	`n > 0 && (n & (n - 1)) == 0`
शून्य	व्यंजक सत्य; दो की घात नहीं
एक	दो की घात (`2^0`)
ऋणात्मक	यहाँ दो की घात मत कहो; `n > 0` रखो
संबंधित उपयोग	कर्निघन बिट-गिनती लूप: `while (n != 0) { n &= n - 1; count++; }` बार-बार सबसे निचला साफ़ कर के सेट बिट गिनता है

आम गलतियाँ:

१. n > 0 भूलना। "दो की घात" जाँच भेज देते हो जो ० पर सत्य दे। २. बिना शून्य चेतावनी के कहना "ये दो की घात जाँचता है"। सही: ज़्यादा से ज़्यादा एक बिट; दो की घात सिर्फ धनात्मक के साथ। ३. सोचना n & (n + 1) वही काम करता है। नहीं। n - 1 पर रहो। ४. "सबसे निचला १ साफ़" को "सारे बिट पलट" से मिलाना। घटाव में सबसे निचला १ और दाईं तरफ़ के शून्य शामिल; एंड फिर वह सबसे निचला १ हटाता है। ५. ऋणात्मक पर हाथ हिलाना। जावा में साफ़ धनात्मक जाँच बेहतर है जब तक पूछा न जाए।

कैसे बोलें (३० सेकंड संस्करण):

१. दो की घातों में ठीक एक बिट १ होता है। २. n & (n - 1) सबसे निचला सेट बिट बंद करता है। ३. परिणाम ० हो तो शून्य या एक बिट सेट था। ४. n > 0 जोड़ो ताकि शून्य दो की घात न बने।

पहेली के बाहर कहाँ दिखता है:

बफ़र आकार जो दो की घात होने चाहिए (कुछ रिंग बफ़र, पुराने हैश टेबल आकार)।
ऐसे एल्गोरिदम से पहले तेज़ जाँच जो चौड़ाई n वाले मास्क इस्तेमाल करें।
बिट-गिनती और बिट-ट्विडलिंग लूप में (बार-बार सबसे निचला सेट बिट साफ़)।

७. दोस्त को समझाने वाला सार

डिबगर (समस्या ५.५) का मतलब "डिबगर बनाना" नहीं। मतलब: ((n & (n - 1)) == 0) क्या जाँचता है?

१. एक घटाकर एंड करने से n का सबसे कम महत्वपूर्ण १-बिट साफ़ होता है। २. अगर गुणनफल शून्य, तो n में दूसरा १ नहीं था: शून्य या एक बिट सेट। ३. ठीक एक बिट वाले धनात्मक पूर्णांक ही दो की घात हैं: १, २, ४, ८, ...। ४. दो की घात चाहिए तो लिखो n > 0 && (n & (n - 1)) == 0। ५. कच्चा व्यंजक शून्य पर भी सत्य। यही जाल आगे के सवालों के अंक दिलाता है।

अगर ८ और १० बाइनरी में चला सको, शून्य क्यों खास समझा सको, और धनात्मक जाँच वाली एक पंक्ति लिख सको, तो समस्या ५.५ तुम्हारी है।