नकारात्मक संख्याएँ बाइनरी में
अब तक हमने सकारात्मक पूर्णांकों के बारे में चर्चा की है और यह देखा है कि मशीनों में उन्हें किस तरह दर्शाया जाता है। लेकिन कभी-कभी हमें ऋणात्मक संख्याओं पर भी काम करना पड़ता है। तो कंप्यूटर इन्हें कैसे संग्रहीत करते हैं?
हमने देखा है कि संख्या 1 का बाइनरी में निरूपण
0001 है, संख्या 6 का 0110 है, आदि। 0 का निरूपण सभी शून्य bits (जैसे 0000) से होता है। एक व्यावहारिक युक्ति जो हम ऋणात्मक संख्याओं को संग्रहीत करने के लिए अपना सकते हैं, वह है एक “विशेष” bit रखना, जो बताता है कि संख्या ऋणात्मक है या नहीं। अगर यह bit 1 है, तो संख्या ऋणात्मक है; और अगर 0 है, तो संख्या धनात्मक है। अधिकांश कंप्यूटर वास्तव में ऋणात्मक संख्याओं के लिए इसी तरीके का प्रयोग करते हैं: बाइनरी निरूपण के सबसे बाएँ (leftmost) bit को यह बताने के लिए इस्तेमाल किया जाता है कि संख्या ऋणात्मक है (1) या धनात्मक (0)।हालाँकि, बाइनरी निरूपण में सिर्फ पहले bit को 1 बना देने से बात पूरी नहीं हो जाती। दशमलव अभिव्यक्ति (जैसे 4, 5, 10, 311 इत्यादि) में धनात्मक और ऋणात्मक संख्याएँ एक-दूसरे को संतुलित कर देती हैं, जैसे 6 और -6 को जोड़ने पर 0 मिलता है। यह गुण बाइनरी में भी बना रहना चाहिए। यदि हम बाइनरी में 6 और -6 जोड़ें, तो परिणाम 0 होना चाहिए।
कल्पना कीजिए कि हमारे पास किसी संख्या को दर्शाने के लिए 4 bits हैं और एक अतिरिक्त bit संकेत (sign) को सँभालने के लिए है। कुल मिलाकर 5 bits हुए। तो 6 का निरूपण
00110 होगा, और 0 का निरूपण 00000। -6 का बाइनरी निरूपण 6 का उल्टा (opposite) होना चाहिए ताकि दोनों को जोड़ने पर 0 प्राप्त हो। थोड़ा आगे देखें तो -6 का निरूपण 11010 होगा। इस तरह, अगर हम 00110 और 11010 को जोड़ें, तो परिणाम 00000 आता है।बाइनरी में किसी धनात्मक संख्या को ऋणात्मक में बदलने (या विपरीत दिशा में) के लिए हम एक सरल तरीका अपना सकते हैं: सभी bits को पलट (flip) दीजिए (यानि 0 को 1 और 1 को 0) और फिर इस नए नंबर में 1 जोड़ दीजिए।
x = 6 # 00110
x = ~x + 1 # Flip all the bits and add 1 => -6
x = ~x + 1 # Flip all the bits and add 1 => 6
z = 0 # 00000
z = ~z + 1 # Flip and +1 => 0
z = ~z + 1 # Flip and +1 => 0
z = ~z # -1 (all 1s in the binary representation)
z = ~z # 0 (all 0s in the binary representation)ध्यान दें कि बाइनरी में जोड़ने की प्रक्रिया ठीक वैसी ही है जैसे दशमलव में जोड़ते समय हम कम महत्वपूर्ण अंक से लेकर सबसे महत्वपूर्ण अंक तक जाते हैं और कैरी (carry) को ध्यान में रखते हैं।
प्रोग्रामिंग भाषा और उसके व्यवहार के अनुसार, कंप्यूटर अलग-अलग तरीकों से संख्याएँ सँभालते हैं। उदाहरण के लिए, C++ और Java में अलग-अलग प्रकार (types) अलग-अलग सीमा (range) वाली संख्याओं के लिए होते हैं। इन भाषाओं में
int प्रकार 32 bits का होता है: 31 bits संख्या के लिए और सबसे सामने (front) का bit संकेत (sign) के लिए। इससे संख्याओं की सीमा -2,147,483,648 () से लेकर 2,147,483,647 () तक जाती है। ध्यान दें कि धनात्मक सीमा एक कम होती है, क्योंकि धनात्मक संख्या 0-bit से शुरू होती है और वही 0-bit से शुरू होने वाली पहली संख्या स्वयं 0 होती है (यानि सभी bits 0)।Challenge
7 की जादुई भूमि में सब कुछ 7 से जुड़ा हुआ है। इसी कारण वहाँ के कंप्यूटर वैज्ञानिकों ने एक ऐसी प्रणाली बनाई है, जिसमें बाइनरी संख्याओं को 77 bits में संग्रहीत किया जाता है (चाहे वे धनात्मक हों या ऋणात्मक)।
दिया गया है कि आपके पास एक bit-string
b है। आपको उसका ऋणात्मक मान (negative value) 77 bits में प्रदर्शित करना है।Input
इनपुट में एक ही पंक्ति में bit-string
b दिया जाता है (1 ≤ |b| ≤ 77)। यह संख्यात्मक रूप से धनात्मक या ऋणात्मक दोनों ही हो सकता है।Output
आउटपुट में एक ही पंक्ति में
-b का 77 bits लंबा प्रतिनिधित्व दिखाना होगा।Examples
इनपुट | आउटपुट |
1 | 11111111111111111111111111111111111111111111111111111111111111111111111111111 |
11111111111111111111111111111111111111111111111111111111111111111111111111111 | 00000000000000000000000000000000000000000000000000000000000000000000000000001 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB