How do you find the parity of a number?
Short answer: Parity is whether the number of set bits is odd or even. Fold the word onto itself with XOR (x ^= x >> 16; x ^= x >> 8; ...) until one bit is left; that bit is 1 for odd parity. Or use __builtin_parity(x).
#include <stdbool.h>
#include <stdint.h>
bool parity_odd(uint32_t x)
{
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return x & 1u; /* 1 = odd number of set bits */
}
Why folding works: XOR of two bits is their sum modulo 2. Each step adds the top half of the remaining bits to the bottom half (mod 2), so after five steps bit 0 holds the XOR of all 32 bits, which is the parity.
Simple loop version:
bool parity_loop(uint32_t x)
{
bool p = 0;
while (x) { p = !p; x &= x - 1; } /* flip once per set bit */
return p;
}
Even vs odd parity in protocols
- Even parity: the transmitter sets the parity bit so the total number of 1s (data + parity) is even. The parity bit equals
parity_odd(data). - Odd parity: the total must be odd, so the parity bit is the inverse.
A UART set to 8E1 sends 8 data bits, an even-parity bit and 1 stop bit. The receiver recomputes parity and flags a parity error if it does not match.
What parity can and cannot do: it detects any odd number of flipped bits but misses every even number (two flipped bits cancel). For better detection use a CRC; for correction use Hamming or ECC codes, which are built from several overlapping parity bits.
Faster on a microcontroller: a 16-entry nibble table, or __builtin_parity, which GCC lowers to an efficient sequence.