c++ - हरण - सम संख्या परिभाषा




बिट प्रोग्रामिंग में(संख्या &-number) का क्या अर्थ है? (2)

इस सवाल का पहले से ही यहाँ एक जवाब है:

उदाहरण के लिए:

int get(int i) {
    int res = 0;
    while (i) {
        res = (res + tree[i]) % MOD;
        i -= ( (i) & (-i) );
    }
    return res;
}

एक पेड़ अद्यतन समारोह:

void update(int i, int val) {
    while (i <= m) {
        tree[i] = (tree[i] + val) % MOD;
        i += ( (i) & (-i) );
    }
}

क्या आप कृपया बता सकते हैं कि वे ( (i) & (-i) ) का उपयोग करके कोड में क्या करते हैं?


मुझे लगता है कि दो के पूरक का उपयोग करके नकारात्मक मूल्य का प्रतिनिधित्व किया जाता है। इस स्थिति में, -i गणना (~i)+1 (फ्लिप बिट्स, फिर 1 जोड़ें) के रूप में की जा सकती है।

उदाहरण के लिए, मुझे i = 44 विचार करने दें। फिर, बाइनरी में,

i           = 0000 0000 0000 0000 0000 0000 0010 1100
~i          = 1111 1111 1111 1111 1111 1111 1101 0011
-i = (~i)+1 = 1111 1111 1111 1111 1111 1111 1101 0100
(i) & (-i)  = 0000 0000 0000 0000 0000 0000 0000 0100

जैसा कि आप देख रहे हैं, कि 1 (i) & (-i) का उपयोग करके कम से कम बिट की गणना की जा सकती है।


यदि कोई और अधिक सामान्य प्रमाण चाहता है, तो

मान लें कि x का a10 k (यहाँ अर्थ है, कुछ बिटस्ट्रिंग a, उसके बाद 1, k शून्य के बाद)।

-x है (परिभाषा के अनुसार) ~x + 1 , के समान

  • x & -x = (भरें)
  • a10 k & - (a10 k ) = (अवहेलना की)
  • a10 k & ~ (a10 k ) + 1 = (उलटा लागू करें)
  • a10 k & ~ a01 k + 1 = (1 जोड़ें)
  • a10 k & ~ a10 k = (और किसी चीज़ और उसके व्युत्क्रम के बीच)
  • 0 डब्ल्यू 10 के

इसलिए हम केवल उस एकल सबसे सही 1 के साथ बचे हैं जिसे हमने ग्रहण किया था।

x के रूप के बारे में धारणा मामले को छोड़ देती है कि x = 0 , जिस स्थिति में परिणाम स्पष्ट रूप से अभी भी शून्य है।







fenwick-tree