का अर्थ (संख्या) और (-नंबर)

Question

(number) & (-number) का अर्थ क्या है? मैं यह खोज की, लेकिन अर्थ

मैं जैसे पाश के लिए में i & (-i) उपयोग करना चाहते हैं खोजने में असमर्थ था की है:

for (i = 0; i <= n; i += i & (-i)) 

Answer 1

2 के पूरक मानते हुए (या कि i अहस्ताक्षरित है), -i~i+1 के बराबर है।

i & (~i + 1)i के निम्नतम सेट बिट को निकालने का एक चाल है।

यह काम करता है, क्योंकि जो +1 लेकिन वास्तव में ऐसा सबसे कम स्पष्ट बिट सेट, और सभी बिट्स से कम स्पष्ट करने के लिए है। तो i और ~i+1 दोनों में सेट किया गया एकमात्र बिट i से सबसे कम सेट बिट है (यानी ~i में सबसे कम स्पष्ट बिट है)। ~i+1 में उससे कम बिट्स स्पष्ट हैं, और इससे अधिक बिट्स i और ~i के बीच गैर-बराबर हैं।

लूप में इसका उपयोग करना अजीब लगता है जब तक कि लूप बॉडी i संशोधित नहीं करता है, क्योंकि i = i & (-i) एक बेवकूफ ऑपरेशन है: इसे दो बार करने से एक ही परिणाम मिलता है।

[संपादित करें: एक टिप्पणी में कहीं आप का कहना है कि कोड वास्तव में i += i & (-i) है। (न्यूनतम सेट बिट से कोई स्पष्ट बिट उच्च साथ i के लिए> 110000. - तो है कि क्या के लिए गैर शून्य i करता i के सेट बिट्स की न्यूनतम समूह, उदाहरण के 101,100 के लिए स्पष्ट और सबसे बढ़कर अगले स्पष्ट बिट स्थापित करने के लिए है i = 0 सहित), यह है, अंत में जब तक यह अधिक है i तो अगर यह सच है कि 0 पर i शुरू होता है, प्रत्येक पाश दो बार iकम से कम से बढ़ जाएगी पिछले पाश, कभी कभी अधिक हो उतना के लिए नहीं थे 0 पर सेट n और ब्रेक या 0 और हमेशा के लिए loops पर चला जाता है।

यह सामान्य रूप से एक टिप्पणी के बिना इस तरह कोड लिखने की अक्षम्य होगा, लेकिन समस्या शायद के डोमेन के आधार पर यह एक "स्पष्ट" पाश से अधिक करने के लिए मूल्यों का अनुक्रम है।]

Answer 2

मैंने सोचा कि मैं यह दिखाने के लिए बस एक पल लें कि यह कैसे काम करता है।

int i = 0xFFFFFFFF; //Last byte is 1111(base 2), -1(base 10) 
int j = -i;   //-(-1) == 1 
int k = i&j;  // 1111(2) = -1(10) 
        // & 0001(2) = 1(10) 
        // ------------------ 
        // 0001(2) = 1(10). So the lowest set bit here is the 1's bit 


int i = 0x80;  //Last 2 bytes are 1000 0000(base 2), 128(base 10) 
int j = -i;   //-(128) == -128 
int k = i&j;  // ...0000 0000 1000 0000(2) = 128(10) 
        // & ...1111 1111 1000 0000(2) = -128(10) 
        // --------------------------- 
        // 1000 0000(2) = 128(10). So the lowest set bit here is the 128's bit 

int i = 0xFFFFFFC0; //Last 2 bytes are 1100 0000(base 2), -64(base 10) 
int j = -i;   //-(-64) == 64 
int k = i&j;  // 1100 0000(2) = -64(10) 
        // & 0100 0000(2) = 64(10) 
        // ------------------ 
        // 0100 0000(2) = 64(10). So the lowest set bit here is the 64's bit 

यह अहस्ताक्षरित मूल्यों के लिए एक ही काम करता है, परिणाम हमेशा न्यूनतम सेट बिट के मूल्य है: यह कोड आपको सबसे कम सेट बिट के मूल्य देता है।

अपने पाश को देखते हुए:

for(i=0;i<=n;i=i&(-i)) 

कोई बिट्स सेट (i=0) कर रहे हैं तो आप वापस इस आपरेशन के वेतन वृद्धि कदम के लिए एक 0 पाने के लिए जा रहे हैं। तो यह लूप हमेशा तक जारी रहेगा जब तक कि n=0 या i संशोधित नहीं किया गया है।

Answer 3

मानते हैं कि नकारात्मक मान दो पूरक का उपयोग कर रहे हैं। फिर -number की गणना (~number)+1 के रूप में की जा सकती है, बिट्स को फ्लिप करें और 1.

उदाहरण के लिए यदि number = 92।तो फिर यह क्या यह बाइनरी में कैसा दिखेगा है:

number    0000 0000 0000 0000 0000 0000 0101 1100 
~number    1111 1111 1111 1111 1111 1111 1010 0011 
(~number) + 1  1111 1111 1111 1111 1111 1111 1010 0100 
-number    1111 1111 1111 1111 1111 1111 1010 0100 
(number) & (-number) 0000 0000 0000 0000 0000 0000 0000 0100 

आप उदाहरण से देख सकते हैं इसके बाद के संस्करण कि (number) & (-number) आप कम से कम बिट देता है।

आप कर सकते हैं आईडीई वन पर ऑनलाइन चलाने कोड देखें: http://ideone.com/WzpxSD

यहाँ कुछ सी कोड है:

#include <iostream> 
#include <bitset> 
#include <stdio.h> 
using namespace std; 

void printIntBits(int num); 
void printExpression(char *text, int value); 

int main() { 
    int number = 92; 

    printExpression("number", number); 
    printExpression("~number", ~number); 
    printExpression("(~number) + 1", (~number) + 1); 
    printExpression("-number", -number); 
    printExpression("(number) & (-number)", (number) & (-number)); 

    return 0; 
} 

void printExpression(char *text, int value) { 
    printf("%-20s", text); 
    printIntBits(value); 
    printf("\n"); 
} 

void printIntBits(int num) { 
    for(int i = 0; i < 8; i++) { 
     int mask = (0xF0000000 >> (i * 4)); 
     int portion = (num & mask) >> ((7 - i) * 4); 
     cout << " " << std::bitset<4>(portion); 
    } 
} 

इसके अलावा यहां सी # .NET में एक संस्करण है: https://dotnetfiddle.net/ai7Eq6