टीएल;डीआर

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

दो पंक्तियों में बल्ब हैं, हर पंक्ति में उतनी ही जगहें। दोनों पंक्तियों में कितने बल्ब अलग हैं? वही संख्या बताती है कि पहली पंक्ति पर कितनी बार स्विच दबाना पड़ेगा ताकि वह दूसरी से मिल जाए।

पूर्णांकों पर यही कन्वर्ज़न है: ए और बी के बीच हैमिंग दूरी। बिट पलटना यानी ० को १ या १ को ० करना। गिनो कहाँ ए और बी नहीं मिलते।

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

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

कागज़ पर दो छोटी द्विआधारी पंक्तियाँ लिखो, एक के नीचे एक:

A:  1 1 1 0 1
B:  0 1 1 1 1
    ^       ^

चिह्न उन स्तंभों को दिखाते हैं जो नहीं मिलते। दो अंतर। ए में वे दो बिट पलटो तो बी मिल जाता है।

संख्या को शून्य से दोबारा बनाने की ज़रूरत नहीं। सिर्फ असहमत जगहें छुओ। सवाल: ऐसी जगहें कितनी हैं?

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

इनपुट: दो पूर्णांक a और b (इंटरव्यू में जावा int काफ़ी; long पर भी वही विचार)।

आउटपुट: उन बिट स्थानों की संख्या जहाँ a और b अलग हैं। इतने पलट a को b बना देते हैं।

उदाहरण:

ए (दशमलव) बी (दशमलव) ए द्विआधारी (निचले बिट) बी द्विआधारी पलट
२९ १५ 11101 01111 २
० ० 0 0 ०
१ ० 1 0 १
७ ० 111 000 ३
-१ ० सब एक (३२ बिट) सब शून्य ३२

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

  • चिह्नित int, टूज़ कॉम्प्लिमेंट? (जावा में हाँ। ऋणात्मक पर भी एक्सओआर और बिट गिनती चलती है।)
  • सिर्फ काम के निचले बिट, या int के पूरे ३२? (पूरे ३२; आगे के शून्य मिलते हैं और शून्य पलट जोड़ते हैं।)
  • स्थानों की सूची या सिर्फ गिनती? (सिर्फ गिनती।)
  • long (६४ बिट) या सिर्फ int? (पूछो। नीचे का कोड int पर है।)

३. पहले सोचो

एक पलट क्या करता है

ए का बिट i पलटने से सिर्फ वही बिट बदलता है। ए को बी बनाने के लिए हर वह बिट पलटना होगा जहाँ वे अलग हैं, और जहाँ पहले से मिलते हैं वहाँ नहीं छूना। जवाब ठीक उतने अलग बिट हैं। इस लागत मॉडल में कोई छोटा रास्ता नहीं।

अंतर एक्सओआर से पकड़ो

एक्सओआर तब १ जब बिट अलग, ० जब मिलें:

ए बिट बी बिट ए एक्सओआर बी
० ० ०
० १ १
१ ० १
१ १ ०

तो a ^ b एक मास्क है जिसमें १ सिर्फ वहीं जहाँ पलट चाहिए। समस्या सिकुड़कर: a ^ b में एक बिट गिनो।

एक की गिनती

तीन आम रास्ते:

१. शिफ्ट लूप: निचला बिट देखो, दाएँ शिफ्ट, ३२ बार दोहराओ (या ० तक अगर सिर्फ धनात्मक के निचले बिट; ऋणात्मक जावा में अंकगणितीय शिफ्ट चिह्न रखता है, इसलिए ३२ कदम या अचिह्नित शैली बेहतर)। २. ब्रायन कर्निघन: c = c & (c - 1) सबसे निचला सेट बिट बुझाता है। c शून्य होने तक लूप। पुनरावृत्तियाँ एक की संख्या के बराबर, चौड़ाई के नहीं। ३. लाइब्रेरी: जावा में Integer.bitCount(c)। अक्सर पॉपकॉउंट निर्देश पर बैठता है। प्रोडक्शन में ठीक; कुछ इंटरव्यू में लूप खुद लिखने को कहते हैं।

साक्षात्कारकर्ता एक साँस में "एक्सओआर, फिर पॉपकॉउंट" सुनना पसंद करते हैं।

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

(क) एक्सओआर + ब्रायन कर्निघन (क्लासिक इंटरव्यू)

int bitFlipCount(int a, int b) {
    int c = a ^ b;
    int count = 0;
    while (c != 0) {
        // सबसे निचला सेट बिट बुझाओ
        c = c & (c - 1);
        count++;
    }
    return count;
}

a = 29, b = 15 का चलना:

29 = 11101
15 = 01111
XOR  = 10010   // दो एक

c = 10010
c & (c-1) = 10000   // count 1
c & (c-1) = 00000   // count 2
return 2

(ख) एक्सओआर + Integer.bitCount

int bitFlipCountLib(int a, int b) {
    return Integer.bitCount(a ^ b);
}

वही जवाब। छोटा। दोनों बताओ: असल कोड में वन-लाइनर, कर्निघन जब पूछें बिटकाउंट कैसे चल सकता है।

(ग) शिफ्ट और मास्क (स्पष्ट ३२ बिट घूमना)

int bitFlipCountShift(int a, int b) {
    int c = a ^ b;
    int count = 0;
    for (int i = 0; i < 32; i++) {
        count += (c & 1);
        c >>>= 1; // अचिह्नित शिफ्ट, ऋणात्मक int पर भी
    }
    return count;
}

हमेशा ३२ पुनरावृत्ति। हर स्थान देखना हो तो साफ़। कम एक होने पर कर्निघन से थोड़ा धीमा; वही बिग-ओ।

छोटी पूरी डेमो

public class Conversion {
    static int bitFlipCount(int a, int b) {
        int c = a ^ b;
        int count = 0;
        while (c != 0) {
            c &= (c - 1);
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(bitFlipCount(29, 15)); // 2
        System.out.println(bitFlipCount(0, 0));   // 0
        System.out.println(bitFlipCount(1, 0));   // 1
        System.out.println(bitFlipCount(7, 0));   // 3
        System.out.println(bitFlipCount(-1, 0));  // 32
    }
}

५. जटिलता तालिका

तरीका समय अतिरिक्त स्थान नोट
एक्सओआर + कर्निघन ओ(क) ओ(१) क = एक्सओआर में एक बिट की संख्या
एक्सओआर + ३२ शिफ्ट ओ(१) int पर ओ(१) तय ३२ पुनरावृत्ति
Integer.bitCount आमतौर ओ(१) ओ(१) अक्सर एक सीपीयू निर्देश

तय चौड़ाई के पूर्णांक पर सब स्थिर। अहम बात विचार है (एक्सओआर फिर गिनती), वृद्धि दर नहीं।

६. किनारे के मामले

  • a == b → ० पलट। एक्सओआर शून्य।
  • एक शून्य → जवाब दूसरे में एक की संख्या।
  • ऋणात्मक → जावा टूज़ कॉम्प्लिमेंट। एक्सओआर और कर्निघन चलते हैं। -1 ^ 0 में ३२ एक।
  • Integer.MIN_VALUE → ठीक। कर्निघन या >>> से मात्रा पर निर्भर भाग या शिफ्ट नहीं।
  • क्रम → flip(a, b) == flip(b, a)। दूरी सममित।
  • Math.abs या द्विआधारी स्ट्रिंग न बनाओ। धीमा, गन्दा, और बिट अध्याय की भावना से बाहर।
  • long संस्करण → long c = a ^ b और शिफ्ट पर ६४ कदम, या Long.bitCount।

न्यूनतम जाँच:

assert bitFlipCount(29, 15) == 2;
assert bitFlipCount(0, 0) == 0;
assert bitFlipCount(-1, 0) == 32;
assert bitFlipCount(7, 1) == 2; // 111 vs 001

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

कन्वर्ज़न पूछता है: ए को बी बनाने में कितने बिट पलट?

१. जो बिट पहले से मिलते हैं, उन्हें मत छुओ। हर अलग बिट पर एक पलट। २. a ^ b ठीक उन्हीं जगहों को जलाता है जहाँ अंतर है। ३. उस एक्सओआर में एक गिनो। वही जवाब। ४. ब्रायन कर्निघन हर चक्कर एक सेट बिट बुझाता है: c = c & (c - 1)। ५. या लाइब्रेरी मदद मिले तो Integer.bitCount(a ^ b)।

अगर बोर्ड पर २९ बनाम १५ घुमा सको, एक्सओआर लिख सको, दो एक घेर सको, और कर्निघन बिना अटकें लिख सको, तो समस्या ५.६ तुम्हारी है।

श्रृंखला