CODEWITHSUNDEEP
cbitparity
MrEmper
MrEmper

Reputation: 235

Check even parity from byte

I've found a piece of code on Stackoverflow and edited it to my needs. source: How to check if value has even parity of bits or odd?

It works like a charm, but I can't get my head around WHY it works.

I tried writing it out, with example byte 0b01101101.

   01101101
   00000110
   -------- ^
   01101011
   00011010
   -------- ^
   01110001
   00111000
   -------- ^
   01001001

While my unit test gives the answer; 1 

uint8_t check_even_parity(uint8_t value){
     value ^= value >> 4;
     value ^= value >> 2;
     value ^= value >> 1;

     return value & 1;
}

Expected is; 0 Actual result when trying to write it out; 01001001

Upvotes: 1

Views: 2225

Answers (3)

Christoph Baumeister
Christoph Baumeister

Reputation: 1

byte parity_even_bit(byte val)
{
    for(int i=1;i<8;i++)
    {
        val   ^= ((val >> i) & 0x01);
    }
    return (val &= 0x01);
}

Upvotes: -1

Aviv Goll
Aviv Goll

Reputation: 300

I would like to propose a metaphor that may give some intuition:

Imagine you have 4 cards lying in front of you, which you need to pile up. As a person with 2 hands, you can pick up a card in each hand simultaneously and place them on top of the other 2, then pick up one of the pairs and put it on top of the other.

This piles 4 cards in 2 moves.

Now imagine you need to pile 32 cards and have 16 hands (or more). You can use the same technique: create 16 piles of 2 cards, than 8 piles of 4 cards, 4 piles of 8 cards, 2 piles of 16 cards and finally a single pile of 32 cards.

This piles 32 cards in 5 moves.

Now replace 'pile' with 'xor', 'cards' with 'bits' and 'hands' with the capability of the processor. In 5 shifts and xors, you get the 32 bits of a number xor-ed together, which gives you 0 if the number have even parity and 1 otherwise.

Upvotes: 2

John Kugelman
John Kugelman

Reputation: 361605

Each step combines two bitsets L and R such that L's parity is merged with R's. R ends up having the same parity as L+R did originally.

In step 1 we take 8 bits and produce a 4-bit number with the same parity as the 8-bit one. In step 2 we produce a 2-bit number with the same parity as the 4. In the last step we produce a 1-bit number with the same parity as the 2. That means in three steps we get a single bit with the same parity as the original 8.

Let me show you what I mean one step at a time.

  1. Let's start with the first step where L is the left 4 bits (0110) and R is the right 4 (1101).

    xxxx1101 (R)
xxxx0110 (L)
--------
xxxx1011 (R^L)

    I've gone ahead and x'ed out the left half of each number. Those bits don't matter. You'll see why as we progress: fewer and fewer bits will be relevant each step.

    L is even and R is odd, which means L+R is odd. R ^= L should therefore leave R with odd parity. Does it? It does indeed. 0110 has two set bits, so R ^= 0110 flips two of R's bits. Flipping an even number of bits won't change parity. R remains odd.

  2. In the second step, L is the left 2 bits (10) and R is the right 2 (11). 

    xxxxxx11 (R)
xxxxxx10 (L)
--------
xxxxxx01 (L^R)

    Now six bits are x'ed out. We're only concerned with two bits from each number.

    This time L is odd and R is even. Combined, L+R is odd, so this time we need to flip R's parity. Does R ^= L do that? Again, it does. L has an odd number of bits set, so XORing it will flip an odd number of bits of R, guaranteeing that R's parity is switched. R becomes odd.

  3. In the final step, L and R are just 1 bit apiece. 

    xxxxxxx1 (L)
xxxxxxx0 (R)
--------
xxxxxxx1 (L^R)

    L is 1, R is 0. Just like in the previous steps, we're hoping that R ^= L is odd, and it is. R is odd.

Wonderful. We started with 8 bits with odd parity and by successfully merging two halves together we got down to 1 bit with the same odd parity.

Upvotes: 2

Related Questions