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:

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
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;
}

don't use `int`, there will be overflow and this then is undefined behavior. Use `unsigned` and `1u` instead, here the wrap around is well defined. — Jens Gustedt, Sep 23 '11 at 14:57
This algorithm does not work. It returns 1 for all values between 0 and 255. — undur_gongor, Sep 23 '11 at 15:01
I took odd bit binary numbers and XOR'd, AND'd, and OR'd them with themselves minus 1 and XOR was the only one that gave something useful (or so I thought). — tippenein, Sep 23 '11 at 15:06
Possible duplicate of [bitParity - Finding odd number of bits in an integer](http://stackoverflow.com/questions/9133279/bitparity-finding-odd-number-of-bits-in-an-integer) — Troyseph, Oct 27 '15 at 09:58

score 4 · Answer 1 · answered Sep 23 '11 at 15:02

4

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

answered Sep 23 '11 at 15:02

Paul R

208,748
37
389
560

I realize my full code doesn't work, but the x ^ (x-1) seemed to give answers that made sense for the values I tried. If you're correct, then I should just dump that and start over. – tippenein Sep 23 '11 at 15:13
Just try the input values 0, 1, 2 and 3 and you will see that it is not going to work. – Paul R Sep 23 '11 at 15:23

unwind · Accepted Answer · 2011-09-23T14:56:51.967

3

I would use actual counting rather than bit-level hacks that exploit the representation of the numbers, that would both feel safer and be more clean and easy to understand. Probably slower, of course, but that's a quite nice trade-off especially when one doesn't know anything about the performance expectations.

Do to this, just write code to count the number of 1 bits, the most straight-forward solution generally boils down to a loop.

UPDATE: Given the (weird and annoying) limitations, my response would probably be to unwind the loop given in the "naive" solution on the bithacks page. That wouldn't be pretty, but then I could go do something useful. :)

edited Sep 23 '11 at 14:56

answered Sep 23 '11 at 14:45

unwind

391,730
64
469
606

I certainly would use a loop to easily count each bit or even just XOR all the bits together, but for this assignment, I'm not allowed to use control structures. Just | ^ & >> << ~ + ! So, your response was my immediate reaction to this, but no dice. – tippenein Sep 23 '11 at 14:50
I've taken a previously written code for bit counting and just AND'd the result with 0x1 to see if there are an odd number of bits or not. However, I did the bitCount(int x) algorithm via brute force; checked each bit with !!(x & (1< – tippenein Sep 23 '11 at 15:35

sastanin · Answer 3 · 2011-09-23T15:16:19.500

1

Bit parity may be done like this:

#include <stdio.h>

int parity(unsigned int x) {
    int parity=0;
    while (x > 0) {
       parity = (parity + (x & 1)) % 2;
       x >>= 1;
    }
}

int main(int argc, char *argv[]) {
    unsigned int i;
    for (i = 0; i < 256; i++) {
        printf("%d\t%s\n", i, parity(i)?"odd":"even");
    }
}

edited Sep 23 '11 at 15:16

answered Sep 23 '11 at 15:05

sastanin

40,473
13
103
130

Bit parity code for odd number of bits

3 Answers3

Linked