[SOLVED] Check even parity from byte

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

Solution

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.