Check even parity from byte

Question

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

Don't forget the last `& 1`. Only the rightmost bit matters in the end. — John Kugelman, May 22 '19 at 18:19
`01001001 & 1 == 1`. I can't understand why you expect it as `0`. — yaho cho, May 22 '19 at 18:37
Your manual walk through doesn't appear to carry over the value to the next row. The "^=" does the XOR and then sets the value to the result of the XOR. — rallen911, May 22 '19 at 20:12

John Kugelman · Accepted Answer · 2019-05-22T18:45:04.137

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.

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.
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.
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.

score 2 · Answer 2 · answered May 22 '19 at 18:56

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.

score -1 · Answer 3 · answered Aug 18 '23 at 16:46

-1

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

answered Aug 18 '23 at 16:46

Christoph Baumeister

1

1

Thank you for contributing to the Stack Overflow community. This may be a correct answer, but it’d be really useful to provide additional explanation of your code so developers can understand your reasoning. This is especially useful for new developers who aren’t as familiar with the syntax or struggling to understand the concepts. **Would you kindly [edit] your answer to include additional details for the benefit of the community?** – Jeremy Caney Aug 19 '23 at 00:26

Check even parity from byte

3 Answers3