c++ हरण बिट प्रोग्रामिंग में(संख्या और संख्या) का क्या अर्थ है?




सम संख्या परिभाषा (3)

इस प्रश्न का उत्तर यहां दिया गया है:

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

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) का उपयोग करके गणना की जा सकती है।


यह दो कार्य एक बाइनरी इंडेक्स पेड़ (फेनविक पेड़) डेटा संरचना का एक संशोधित कार्यान्वयन है।
माइककैट के उत्तर को पूरक करने के लिए यहां दो चित्र दिए गए हैं जो दिखाते हैं कि मैं विभिन्न मानों के लिए अद्यतन कैसे बदलता हूं

"प्राप्त करें" फ़ंक्शन:
मान लें कि फ़ंक्शन में इनपुट में अधिकतम मान प्रतिनिधित्व की सादगी के लिए 15 है।

उस पर संख्या टी वाला नोड पेड़ सरणी में पेड़ [टी] का प्रतिनिधित्व करता है।
यदि आप कॉल के लिए फ़ंक्शन प्राप्त करते हैं तो लौटाया गया मूल्य पेड़ का योग है [i] प्लस समस्त पेड़ सरणी तत्वों का योग है कि सरणी में उनकी अनुक्रमणिका शून्य में छोड़कर चित्र में मेरे माता-पिता है।
यहाँ कुछ उदाहरण हैं:

get(15) = tree[15] + tree[14] + tree[12] + tree[8]
get(14) = tree[14] + tree[12] + tree[8]
get(13) = tree[13] + tree[12] + tree[8]
get(12) = tree[12] + tree[8]
get(11) = tree[11] + tree[10] + tree[8]
get(10) = tree[10] + tree[8]
get(9) = tree[9] + tree[8]
get(8) = tree[8]
get(7) = tree[7] + tree[6] + tree[4]
get(6) = tree[6] + tree[4]
get(5) = tree[5] + tree[4]
get(4) = tree[4]
get(3) = tree[3] + tree[2]
get(2) = tree[2]


उपर्युक्त चित्र में नोड्स पर लेबलों पर संख्याओं में संपत्ति है कि प्रत्येक नोड के माता-पिता यह है कि नोड लेबल कम से कम महत्वपूर्ण 1 (कम से कम @MikeCAT उत्तर पर समझाया गया है) "अद्यतन" फ़ंक्शन:
तस्वीर की सादगी के लिए, मान लीजिए कि पेड़ सरणी की अधिकतम लंबाई 16 है।
अद्यतन फ़ंक्शन थोड़ा सा ट्रिकियर है।

यह पेड़ [i] और सभी वृक्ष तत्वों के लिए वैल जोड़ता है कि उनकी अनुक्रमणिका तस्वीर में लेबल के साथ नोड के पैरेंट है।

update(16, val) --> tree[16] += val;
update(15, val) --> tree[15] += val, tree[16] += val;
update(14, val) --> tree[14] += val, tree[16] += val;
update(13, val) --> tree[13] += val, tree[14] += val; tree[16] += val;
update(12, val) --> tree[12] += val, tree[16] += val;
update(11, val) --> tree[11] += val, tree[12] += val, tree[16] += val;
update(10, val) --> tree[10] += val, tree[12] += val, tree[16] += val;
update(9, val)  --> tree[9] += val, tree[10] += val, tree[12] += val, tree[16] += val;
update(8, val)  --> tree[8] += val, tree[16] += val;
update(7, val)  --> tree[7] += val, tree[8] += val, tree[16] += val;
update(6, val)  --> tree[6] += val, tree[8] += val, tree[16] += val;
update(5, val)  --> tree[5] += val, tree[6] += val, tree[8] += val, tree[16] += val;
update(4, val)  --> tree[4] += val, tree[8] += val, tree[16] += val;
update(3, val)  --> tree[3] += val, tree[4] += val, tree[8] += val, tree[16] += val;
update(2, val)  --> tree[2] += val, tree[4] += val, tree[8] += val, tree[16] += val;
update(1, val)  --> tree[1] += val, tree[2] += val, tree[4] += val, tree[8] += val, tree[16] += val;

यदि कोई भी एक सामान्य प्रमाण भी चाहता था,

मान लें कि x में प्रारूप 10 है (जिसका अर्थ है, कुछ बिटस्ट्रिंग ए, उसके बाद 1, उसके बाद के ज़ीरो)।

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

  • एक्स और -एक्स = (भरें)
  • ए 10 के एंड - (ए 10 के ) = (अस्वीकृति का डीफ़)
  • ए 10 के और ~ (ए 10 के ) + 1 = (उलटा लागू करें)
  • ए 10 के और ~ ए01 के + 1 = (1 जोड़ें)
  • ए 10 के और ~ ए 10 के = (और कुछ और इसके विपरीत के बीच)
  • 0 डब्ल्यू 10 के

इसलिए हमें केवल एक ही दाएं 1 के साथ छोड़ दिया गया है जिसे हम अस्तित्व में रखते थे।

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







fenwick-tree