algorithm - log2 value




लूप के बिना दी गई संख्या के नकारात्मक अभिप्राय की गणना करना (2)

क्या आप एक ठोस स्पष्टीकरण, या गणितीय सबूत प्रदान कर सकते हैं, क्यों निम्नलिखित फ़ंक्शन किसी दिए गए नंबर के नकारात्मक अभिप्राय की गणना करता है?

function quickNegabinary(number) {
  var mask = 0xAAAAAAAA;
  return ((number + mask) ^ mask).toString(2);
}

"0xAAAAAAAA" उन जादू संख्याओं में से एक है जिसमें 10 (बाइनरी) पैटर्न का अनुक्रम होता है इसे मुखौटा के रूप में प्रयोग किया जाता है क्योंकि आप थोड़ी-सी XOR ऑपरेशन कर रहे हैं। जब आप इस मुखौटा में संख्या जोड़ते हैं और एक XOR करते हैं, तो परिणाम केवल संख्या के आधार पर उन बिट्स से प्रभावित होगा, बाकी परिणाम 0 में होगा। [चूंकि दो समान बिट्स के एक्सओआर 0 है] अंत में, टूस्ट्रिंग (2) परिणाम को बाइनरी में परिवर्तित कर रहा है

उदाहरण: -> 3 पर विचार करें आपका नंबर है 3 से 2863311530 [जो कि 0xAAAAAAAA का दशमलव प्रतिनिधित्व है] जोड़ें। -> एक्सओआर राशि (मुखौटा + 3) 0xAAAAAAAA के साथ, जो कि .... 10101010 1101 ^ .... 10101010 यह आपको 111 देता है (आखिरकार मुखौटा में पिछले 3 संगत बिट्स और योग भिन्न हैं) -> 111 को द्विआधारी में कनवर्ट करें, जो 7 है


निगैनी नोटेशन

Negabinary नोटेशन -2 का रेडिक्स का उपयोग करता है इसका मतलब है कि, प्रत्येक संख्या प्रणाली में एक नकारात्मक आधार के साथ, हर दूसरे बिट में एक नकारात्मक मूल्य होता है:

position:    ...     7    6    5    4    3    2    1    0  

binary:      ...   128   64   32   16    8    4    2    1  
negabinary:  ...  -128  +64  -32  +16   -8   +4   -2   +1  

त्वरित रूपांतरण विधि

त्वरित बाइनरी → न्यूज़ैबिनरी कनवर्ज़न विधि जोड़ता है और फिर 0xAAAAAAAA या बाइनरी के साथ एक संख्या है ...10101010 (एक मुखौटा जो अजीब स्थिति को इंगित करता है जो कि नकारात्मक मानदंड में नकारात्मक मान है), उदाहरण के लिए मूल्य 82:

binary:               01010010  =  82 (binary: 64 + 16 + 2)  
mask:                 10101010  = 170  
bin+mask              11111100  = 252  
(bin+mask) XOR mask:  01010110  =  82 (negabinary: 64 + 16 + 4 - 2)  

यह कैसे काम करता है: एक सेट बिट

यह देखने में आसान है कि विधि कैसे काम करती है, यदि आप किसी संख्या का उदाहरण द्विआधारी संकेतन में केवल एक सेट बिट के साथ करते हैं यदि सेट बिट किसी भी स्थिति में है, तो कुछ भी परिवर्तन नहीं होता है:

binary:               00000100  =   4 (binary: 4)  
mask:                 10101010  = 170  
bin+mask              10101110  = 174  
(bin+mask) XOR mask:  00000100  =   4 (negabinary: 4)  

हालांकि, यदि सेट बिट एक अजीब स्थिति में है:

binary:               00001000  =   8 (binary: 8)  
mask:                 10101010  = 170  
bin+mask              10110010  = 178  
(bin+mask) XOR mask:  00011000  =   8 (negabinary: 16 - 8)  

सेट बिट को स्थानांतरित कर दिया गया है (इसे 1 जोड़कर), और फिर उसके मूल मान के नकारात्मक (मुखौटा के साथ XOR-ING द्वारा) के साथ जोड़ा जाता है, ताकि मूल्य 2 एन के साथ 2 n + 1 - 2 एन

तो आप त्वरित रूपान्तरण पद्धति के बारे में सोच सकते हैं जैसे: "हर 2 से 4 - 2, प्रति 8 से 16 - 8, प्रत्येक 32 को 64 - 32, और इसी तरह बदलें"।

यह कैसे काम करता है: एकाधिक सेट बिट्स

कई सेट बिट्स के साथ एक नंबर को परिवर्तित करते समय, ऊपर वर्णित एक सेट बिट के साथ एक नंबर को परिवर्तित करने के परिणाम को एक साथ जोड़ दिया जा सकता है। जैसे कि 4 और 8 के एकल-सेट-बिट उदाहरण (ऊपर देखें) का संयोजन करने के लिए 12:

binary:               00001100  =  12 (binary: 8 + 4)  
mask:                 10101010  = 170  
bin+mask              10110110  = 182  
(bin+mask) XOR mask:  00011100  =  12 (negabinary: 16 - 8 + 4)  

या, एक और अधिक जटिल उदाहरण के लिए, जहां कुछ अंक किए जाते हैं:

binary:               00111110  =  62 (binary: 32 + 16 + 8 + 4 + 2)  
mask:                 10101010  = 170  
bin+mask              11101000  = 232  
(bin+mask) XOR mask:  01000010  =  62 (negabinary: 64 - 2)  

यहाँ क्या होता है जो उस राशि में है जो द्विआधारी संख्या का वर्णन करता है:

32 + 16 + 8 + 4 + 2

32 को 64 - 32, 8 में 16 - 8 और 2 में 4 - 2 में परिवर्तित किया जाता है, ताकि राशि बन जाती है:

64 - 32 + 16 + 16 - 8 + 4 + 4 - 2

जहां दो 16 हैं तब 32 बनने के लिए और दो 4 को 8 बनने के लिए किया जाता है:

64 - 32 + 32 - 8 + 8 - 2

और -32 और +32 एक-दूसरे को रद्द करते हैं, और -8 और +8 देने के लिए प्रत्येक दूसरे को रद्द करते हैं:

64 - 2

या, गणितीय अंकगणित का उपयोग कर:

          +1    +1                 (carry)
     0  1 -1  0  0  0  0  0  =  32 (negabinary: 64 - 32)  
     0  0  0  1  0  0  0  0  =  16 (negabinary: 16)  
     0  0  0  1 -1  0  0  0  =   8 (negabinary: 16 - 8)  
     0  0  0  0  0  1  0  0  =   4 (negabinary: 4)  
  +  0  0  0  0  0  1 -1  0  =   2 (negabinary: 4 - 2)  
     ----------------------  
  =  0  1  0  0  0  0 -1  0  =  62 (negabinary: 64 - 2)  

नकारात्मक मूल्य

त्वरित रूपान्तरण पद्धति भी दो अंकों की संख्या में नकारात्मक संख्याओं के लिए काम करती है, उदाहरण के लिए:

binary:                       11011010  =    -38 (two's complement)  
mask:                         10101010  =    -86 (two's complement)  
bin+mask                      10000100  =   -124 (two's complement)  
(bin+mask) XOR mask:          00101110  =    -38 (negabinary: -32 - 8 + 4 - 2)  
binary:              11111111 11011010  =    -38 (two's complement)  
mask:                10101010 10101010  = -21846 (two's complement)  
bin+mask             10101010 10000100  = -21884 (two's complement)   
(bin+mask) XOR mask: 00000000 00101110  =    -38 (negabinary: -32 - 8 + 4 - 2)  

रेंज और अतिप्रवाह

एन बीट्स (जहां n एक संख्या भी है) के साथ एक नकारात्मक संख्या की सीमा है:

-2/3 × (2 एन -1) → 1/3 × (2 एन -1)

या, आम बिट गहराई के लिए:

 8-bit:            -170  ~             85  
16-bit:         -43,690  ~         21,845  
32-bit:  -2,863,311,530  ~  1,431,655,765  
64-bit:       -1.23e+19  ~       6.15e+18  
80-bit:       -8.06e+23  ~       4.03e+23  

यह सीमा एक ही बिट गहराई के साथ हस्ताक्षरित और अहस्ताक्षरित मानक पूर्णांक अभ्यावेदन दोनों की तुलना में कम है, इसलिए दोनों ही हस्ताक्षरित और अहस्ताक्षरित पूर्णांक बहुत बड़ी हो सकती हैं, जो कि थोड़ी गहराई के साथ अस्वीकार्य संकेतन में प्रतिनिधित्व किया जा सकता है।

यद्यपि त्वरित रूपांतर पद्धति प्रतीत हो सकती है -1 / 6 × (2 एन -4) के नीचे नकारात्मक मानों के लिए अतिप्रवाह में, रूपांतरण के परिणाम अभी भी सही हैं:

binary:                       11010011  =    -45 (two's complement)  
mask:                         10101010  =    -86 (two's complement)  
bin+mask             11111111 01111101  =   -131 (two's complement)  
overflow truncated:           01111101  =    125 (two's complement)  
(bin+mask) XOR mask:          11010111  =    -45 (negabinary: -128 + 64 + 16 + 4 - 2 + 1)  
binary:              11111111 11010011  =    -45 (two's complement)  
mask:                10101010 10101010  = -21846 (two's complement)  
bin+mask             10101010 01111101  = -21891 (two's complement)  
(bin+mask) XOR mask: 00000000 11010111  =    -45 (negabinary: -128 + 64 + 16 + 4 - 2 + 1)  

रिवर्स फ़ंक्शन

नेगैबरी संख्याओं को वापस जोड़कर मानक पूर्णांक मानों में परिवर्तित किया जा सकता है और मुखौटा के साथ XOR- आईएनजी, जैसे:

uint64_t negabinary(int64_t bin) {
    if (bin > 0x5555555555555555) throw std::overflow_error("value out of range");
    const uint64_t mask = 0xAAAAAAAAAAAAAAAA;
    return (mask + bin) ^ mask;
}

int64_t revnegabin(uint64_t neg) {
    // const uint64_t even = 0x2AAAAAAAAAAAAAAA, odd = 0x5555555555555555;
    // if ((neg & even) > (neg & odd)) throw std::overflow_error("value out of range");
    const uint64_t mask = 0xAAAAAAAAAAAAAAAA;
    return (mask ^ neg) - mask;
}

(यदि रिवर्स फ़ंक्शन को केवल negatial () फ़ंक्शन द्वारा बनाई जाने वाली नकारात्मक संख्या पर कॉल किया जाता है, तो अतिप्रवाह का कोई खतरा नहीं है। हालांकि, अन्य स्रोतों से 64-बिट अस्वीकार्य संख्या int64_t श्रेणी के नीचे एक मान हो सकती है, इसलिए अतिप्रवाह जांच हो जाती है ज़रूरी।)





base-conversion