</>EmbeddedInterview

How do you find the parity of a number?

MediumBit Manipulation

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.