c++bit-manipulationbitwise-xor

Bit operators C++


Can someone explain to me how this function works? I understand the drop the lowest set of a bit of x part which is the 5th line but I don't understand the assignment result ^= 1; Shouldn't result be counting 0 and 1 when deciding parity of a word?

short Parity_of_word(unsigned long long x) {
    short result = 0;
    while(x) {
        result ^= 1;
        x &= (x-1);
    }
    return result;
}

Solution

  • result ^= 1;
    

    changes result between 0 and 1, repeatedly. So, the question is: How many time will this be done?

    x&=(x-1);
    

    is a hacky way to do "remove the last bit from x". To see it, imagine x is

    0101000110
    

    removing one will make it:

    0101000101
    

    (all the 0 in the end became 1, and the first 1 became 0). Once you and both values together:

    0101000100
    

    Tada, one less 1. So, the while loop will execute just as many times as there are 1s in x. And it will flip result accordingly.