Bit parity code for odd number of bits

Question

I am trying to find the parity of a bitstring so that it returns 1 if x has an odd # of 0's.
I can only use basic bitwise operations and what I have so far passes most of the tests, but I'm wondering 2 things:

1. Why does x ^ (x + ~1) work? I stumbled upon this, but it seems to give you 1 if there are an odd number of bits and something else if even. Like 7^6 = 1 because 7 = 0b0111

2. Is this the right direction of problem solving for this? I'm assuming my problem is stemming from the first operation, specifically (x + ~1) because it would overflow certain 2's complement numbers. Thanks

Code:

int bitParity(int x) {
    int first = x ^ (x + ~1);
    int second = first ^ 1; // if first XOR gave 1 you'll return 0 here
    int result = !!second;
return result;
}

Answer 1

Your parity function doesn't actually work as far as I can tell - it seems to get the answer right about half of the time, which is about as good as returning a random result (or even just returning 0 or 1 all the time).

There are several bit level hacks which do actually work at: http://graphics.stanford.edu/~seander/bithacks.html#ParityNaive - you probably want to look at the last one of these: http://graphics.stanford.edu/~seander/bithacks.html#ParityParallel