How to XOR all of the bits of a single number in C?

Question

Is there a simple way to XOR all of the bits of a single number together, i.e. a unary XOR in C?

Something that has the effect of:

result = ^(0x45); // ( 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 1 ^ 0 ^ 1 = 1)
result = ^(0x33); // ( 0 ^ 0 ^ 1 ^ 1 ^ 0 ^ 0 ^ 1 ^ 1 = 0)

Answer 1

GCC has a builtin for this:

int xor_bits(unsigned x) {
    return __builtin_parity(x);
}

Alternatively, you can compute the parity by counting the number of set bits. The gcc builtin for this is __builtin_popcount():

int xor_bits(unsigned x) {
    return __builtin_popcount(x) & 1;
}

If you care to stick to only standard C, https://graphics.stanford.edu/~seander/bithacks.html and How to count the number of set bits in a 32-bit integer? have some great solutions for counting the number of set bits.

Answer 2

A simplified O(log2(n)) approach.

#include <limits.h>

int odd_parity(unsigned v) { 
    #if (UINT_MAX > 0xFFFFFFFFFFFFFFFFu)
    v ^= v >> 64;  // Prepare for the future
    #endif
    #if (UINT_MAX > 0xFFFFFFFFu)
    v ^= v >> 32;
    #endif
    #if (UINT_MAX > 0xFFFFu)
    v ^= v >> 16;
    #endif
    v ^= v >> 8;
    v ^= v >> 4;
    v ^= v >> 2;
    v ^= v >> 1;
    return (int) (v&1);
}

Answer 3

There's no special operator for that. You would need to do that manually as follows:

unsigned int value = 0x45;
unsigned int result = 0;
while (value) {
    result ^= value & 1;
    value >>= 1;
}

You can also create a lookup table containing the parity for all 1 byte values:

char parity[256] = { 0, 1, 1, 0, 1, 0, 0, 1,
                    ...
                     1, 0, 0, 1, 0, 1, 1, 0 };

Answer 4

If you are using gnu gcc you should be able to use __builtin_popcount to count the number of on bits(i.e. bits set to 1). The result of the XOR would be the parity of this number. However this solution is not using the standard and will not always work.

I believe there is no elegant solution that is using only the standard.

Answer 5

if the number of 1s in the binary representation is odd then the answer is 1 ; if it is even then the answer is 0

Answer 6

You can count all bits in a loop, or if you want something that might be slightly more efficient you can mask off portions of the original number and xor them, repeatedly, until you get down to 1 bit operands. Assuming a 32-bit integer with 2's complement representation:

int xor_all(int v)
{
    int l = (v & 0xFFFF0000) >> 16;
    int r = v & 0x0000FFFF;
    int m = l ^ r;

    l = (m & 0xFF00) >> 8;
    r = m & 0x00FF;
    m = l ^ r;

    l = (m & 0xF0) >> 4;
    r = m & 0x0F;
    m = l ^ r;

    l = (m & 0xC) >> 2;
    r = m & 3;
    m = l ^ r;

    l = (m & 2) >> 1;
    r = m & 1;
    m = l ^ r;
    return m;
}

There are other techniques also; any good routine for counting set bits will work if you just take the lowest bit of the result. The above code has the benefit that it is relatively easy to understand, but it's unlikely to be the fastest.

As Peter Cordes points out, you can skip the masks (&s) until the last step (i.e. just replace m = l ^ r; with m = (l ^ r) & 1; and replace all other M & N for any M/N with just M). I have left them in above as they perhaps make clearer how the algorithm works.

Answer 7

Try this:

unsigned long parity(unsigned long x) {
    for(char i=sizeof(unsigned long)<<2;x>1;i>>=1) x=(x^(x<<i))>>i;
    return x;
}

unsigned long is the largest type supported (unsigned long long is the largest possible). It is defined in <cstdint> or <stdint.h>. sizeof(unsigned long) is bytes. We need half bits to start, so it's bytes*4. Then, upper half is XORed with lower half. Then we get rid of the lower half. The edited answer guarantees convergence, there should be at most one overflow.