बाइनरी टू स्ट्रिंग: भिन्न को बिट्स में छापो या एरर (जावा)

टीएल;डीआर

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

दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली समस्या ५.२: (०, १) में डबल लो, उसका बाइनरी भिन्न स्ट्रिंग छापो, या बिंदु के बाद ३२ बिट से ज़्यादा लगे तो एरर। जावा में गुणा-दो विधि।

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

तुम्हारे पास एक मापने वाला गिलास है जिस पर सिर्फ आधा, चौथाई, आठवाँ, और ऐसे ही निशान हैं। कोई थोड़ा पानी डालता है: खाली से ज़्यादा, भरा से कम। तुम लिखना चाहते हो कि कितना भरा है, सिर्फ बाइनरी बिंदु के बाद ० और १ से: 0.101 मतलब आधा और आठवाँ। कुछ मात्राएँ छोटी बाइनरी स्ट्रिंग में समा जाती हैं। कुछ हमेशा और छोटे निशान माँगती रहती हैं। अगर ३२ निशानों के बाद जगह खत्म, तो रुक जाओ और एरर कहो। यही है ० और १ के बीच वास्तविक संख्या के लिए बाइनरी टू स्ट्रिंग।

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

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

बाइनरी भिन्न को दशमलव भिन्न की तरह सोचो, बस आधार २।

दशमलव में 0.75 का मतलब:

7 * (1/10) + 5 * (1/100)

बाइनरी में 0.11 का मतलब:

1 * (1/2) + 1 * (1/4) = 0.75

तो बाइनरी बिंदु के बाद हर स्थान पिछले का आधा भार रखता है: १/२, १/४, १/८, १/१६, ...

वे बिट बिना अनुमान के कैसे निकालें? दशमलव में स्कूल वाला तरीका: १० से गुणा करो, अगला अंक निकालो। यहाँ २ से गुणा करो और अगला बिट निकालो:

१. num को (०, १) में शुरू करो। २. num = num * 2। ३. अगर परिणाम कम से कम १ है, अगला बिट 1 है, और सिर्फ भिन्न भाग रखने के लिए १ घटाओ। ४. अगर परिणाम अभी भी १ से छोटा है, अगला बिट 0 है। ५. दोहराओ जब तक भिन्न ठीक ० न हो (हो गया) या ३२ बिट लिख चुके हो और अभी बाकी हो (एरर)।

क्यों चलता है: २ से गुणा बाइनरी बिंदु को एक स्थान बाएँ खिसकाता है। जो पूर्णांक बिट बाहर निकलता है, वही बिंदु के बाद अगला बाइनरी अंक है।

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

इनपुट: एक double num जहाँ 0 < num < 1 (सख्ती से ० और १ के बीच)।

आउटपुट: एक String जैसे "0." के बाद बाइनरी अंक, उदाहरण "0.101"। अगर मान बाइनरी बिंदु के बाद ज़्यादा से ज़्यादा ३२ बिट में ठीक-ठीक नहीं बन सकता, तो "ERROR" लौटाओ।

उदाहरण:

इनपुट (दशमलव)	बाइनरी स्ट्रिंग	क्यों
`0.5`	`"0.1"`	एक आधा
`0.25`	`"0.01"`	एक चौथाई
`0.75`	`"0.11"`	आधा + चौथाई
`0.625`	`"0.101"`	आधा + आठवाँ
`0.1`	`"ERROR"`	०.१ बाइनरी में आवर्ती; ३२ बिट में ठीक ० नहीं
`0.0` या `1.0`	सीमा से बाहर	समस्या मानती है सख्ती से ० और १ के बीच

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

० या १ मान्य? (क्लासिक कथन: ० और १ के बीच, सिरे नहीं।)
स्ट्रिंग लौटाएँ या प्रिंट? (दोनों ठीक; लौटाना टेस्ट के लिए आसान।)
सीमा बिंदु के बाद ३२ बिट है, या "0." मिलाकर कुल ३२ अक्षर? (ज़ोर से दोनों बोलो। इस लेख में बिंदु के बाद ३२ बिट, कोडिंग की आम मंशा।)
फ्लोटिंग पॉइंट शोर: असली double पहले से बाइनरी है। फिर भी इंटरव्यू गुणा-दो लूप और न रुकने वाले मामलों के लिए एरर रास्ता चाहता है।

इस लेख में: (०, १) में double, लौटाओ "0." + bits या "ERROR", बिंदु के बाद अधिकतम ३२ बिट।

३. पहले सोचो

क्या न करें

पूरे डबल पर Integer.toBinaryString। वह पूर्णांकों के लिए है, भिन्न भाग के लिए नहीं।
Double.toHexString या वैज्ञानिक संकेतन छापना। गलत प्रारूप।
मान लेना कि हर दशमलव भिन्न छोटी बाइनरी रूप में है। कई नहीं। दशमलव 0.1 क्लासिक उलटा उदाहरण है, जैसे दशमलव में 1/3 = 0.333...।

मुख्य लूप: २ से गुणा

builder = "0."
while num > 0:
    if builder length (बिंदु के बाद बिट) पहले से 32:
        return ERROR
    num = num * 2
    if num >= 1:
        append '1'
        num = num - 1
    else:
        append '0'
return builder

जब num ० हो जाए: ठीक-ठीक दर्शाया।

अगर ३३वाँ बिट चाहिए, एरर लौटाओ।

कुछ संख्याएँ कभी खत्म क्यों नहीं होतीं

जिस भिन्न का हर (न्यूनतम रूप में) २ के अलावा कोई अभाज्य गुणनखंड रखता हो, वह सीमित बाइनरी विस्तार नहीं हो सकता। दशमलव 0.1 है 1/10। दस में ५ का गुणनखंड है, इसलिए ०.१ का बाइनरी विस्तार दोहराता है। लूप बिट बनाता रहता है और कभी ठीक ० पर नहीं बैठता। ३२ कदम बाद सही से छोड़ देते हो।

फ्लोटिंग पॉइंट सावधानी (एक बार कहो, फिर आगे)

जावा का double पहले से आईईईई-७५४ बाइनरी में है। तो "इस डबल का बाइनरी छापो" का मतलब "मेंटिसा के बिट पढ़ो" भी हो सकता है। इंटरव्यू ५.२ आमतौर पर एल्गोरिदमी संस्करण है: गुणा-दो से वास्तविक संख्या फैलाओ, और ३२ बिट में न रुके तो एरर। ० से तुलना सावधानी से; शिक्षण में सादा लूप। प्रोडक्शन में कभी एप्सिलॉन से बाँधते हैं, पर इंटरव्यू साफ़ एरर नियम चाहता है।

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

/**
 * Binary representation of a real number strictly between 0 and 1.
 * Returns "0." followed by bits, or "ERROR" if more than 32 bits are needed.
 */
String binaryToString(double num) {
    if (num <= 0 || num >= 1) {
        return "ERROR";
    }

    StringBuilder bits = new StringBuilder("0.");
    int maxBits = 32;

    while (num > 0) {
        if (bits.length() - 2 >= maxBits) {
            // Already used 32 places after the point and still not zero.
            return "ERROR";
        }

        num = num * 2;
        if (num >= 1) {
            bits.append('1');
            num = num - 1;
        } else {
            bits.append('0');
        }
    }

    return bits.toString();
}

चलकर देखो: `0.625`

कदम	पहले `num`	`* 2` के बाद	बिट	बाद का `num`
१	०.६२५	१.२५	`1`	०.२५
२	०.२५	०.५	`0`	०.५
३	०.५	१.०	`1`	०.०

परिणाम: "0.101"। लूप इसलिए रुकता है क्योंकि num ० है।

चलकर देखो: `0.1` (एरर आएगा)

कदम	विचार
१	`0.1 * 2 = 0.2` → बिट `0`
२	`0.2 * 2 = 0.4` → बिट `0`
३	`0.4 * 2 = 0.8` → बिट `0`
४	`0.8 * 2 = 1.6` → बिट `1`, शेष `0.6`
...	बिट आते रहते हैं; ३२ कदम में शेष ठीक ० नहीं

बिंदु के बाद ३२ बिट के बाद "ERROR" लौटाओ।

न्यूनतम स्मोक टेस्ट

public static void main(String[] args) {
    System.out.println(binaryToString(0.5));    // 0.1
    System.out.println(binaryToString(0.25));   // 0.01
    System.out.println(binaryToString(0.75));   // 0.11
    System.out.println(binaryToString(0.625));  // 0.101
    System.out.println(binaryToString(0.1));    // ERROR
    System.out.println(binaryToString(0.0));    // ERROR (out of range here)
    System.out.println(binaryToString(1.0));    // ERROR
}

नोट: कुछ जेवीएम पर 0.1 जैसा लिटरल पहले से फ्लोटिंग पॉइंट राउंडिंग रखता है। फिर भी जो मान डायडिक भिन्न नहीं (हर घात-२), लूप ३२ बिट में ठीक ० नहीं साफ़ करता। एरर रास्ते के लिए यही चाहिए।

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

तरीका	समय	अतिरिक्त जगह	नोट
गुणा-दो लूप	ओ(१)	ओ(१)	अधिकतम ३२ दोहराव; स्ट्रिंग लंबाई ≤ ३४ (`"0."` + ३२ बिट)
सारी डायडिक भिन्न पहले से	ओ(१) या बदतर	बड़ी	ज़रूरत से ज़्यादा; इंटरव्यू लूप चाहता है
आईईईई मेंटिसा बिट-ट्विडल	ओ(१)	ओ(१)	अलग समस्या: संग्रहीत बिट निकालना, न कि "३२ में ठीक न हो तो एरर"

३२ कदम की सीमा से इंटरव्यू के लिए समय और जगह स्थिर।

६. किनारे के मामले और आम गलतियाँ

इंटरव्यूअर ये छेड़ते हैं:

ठीक ० या १ → इस समस्या के लिए अमान्य, एरर या शुरू में रोक।
ठीक ०.५, ०.२५, ०.१२५, ... → सीमित बाइनरी; साफ़ छापकर रुकना चाहिए।
३२वें बिट पर अभी शेष → एरर। लंबाई जाँच में एक-अधिक-एक-कम आम है।
हमेशा == 0 से तुलना → असली गैर-डायडिक भिन्न पर लंबाई की छत पर भरोसा। अनंत घुमाव नहीं।
"0." उपसर्ग भूलना → इंटरव्यू में प्रारूप मायने रखता है।
>= 1 की जगह int कास्ट → गुणा के बाद (int) num तब चलता है जब num [०, २) में हो, पर >= 1 साफ़ है।
बिना गिने char[३२] में बिट ठूँसना → मानसिक सीमा पार आसान।

आम गलतियाँ:

१. लंबाई जाँच अपेंड के बाद, पहले नहीं। एक बार ३३ बिट निकल सकते हैं। हर नए बिट से पहले जाँचो (या बाद में > 32 से, एक जैसा)। २. num *= 2 और हमेशा १ घटाना। सिर्फ जब बिट १ हो तब घटाओ। ३. अधिकतम लंबाई के बिना अनंत लूप। एरर का पूरा मतलब ३२ बिट बजट है। ४. अक्षर बजट और बिट बजट मिलाना। कोड से पहले नियम तय करो। ५. सोचना एरर सिर्फ "खराब इनपुट" है। एरर का मतलब यह भी है: "३२ बिट में ठीक-ठीक नहीं बन सकता।"

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

बाइनरी टू स्ट्रिंग पूछता है: ० और १ के बीच डबल को "0." प्लस बाइनरी अंकों में लिखो, या बिंदु के बाद ३२ बिट में न समाए तो एरर।

१. हर बिट अगला स्थान मान: १/२, १/४, १/८, ... २. भिन्न को २ से गुणा करो। पूर्णांक भाग (० या १) अगला बिट है। भिन्न शेष रखो। ३. शेष ० हो तो रुको: ठीक प्रतिनिधित्व। ४. ३२ बिट से ज़्यादा चाहिए तो "ERROR" लौटाओ। ५. कई रोज़मर्रा के दशमलव (जैसे ०.१) बाइनरी में कभी नहीं रुकते। छत वैकल्पिक नहीं।

अगर व्हाइटबोर्ड पर 0.625 → 0.101 चला सको और बता सको 0.1 पर एरर क्यों, तो समस्या ५.२ तुम्हारी है।