Parity and Gray code

Overview

Two classic bit tricks, each built on XOR. Parity asks whether a value has an odd number of set bits — computed not by counting them but by folding the word onto itself with XOR shifts until the answer collapses into bit 0, five steps for 32 bits. Gray code is a numbering in which consecutive values differ in exactly one bit; converting binary to Gray is the single expression x ^ (x >> 1). Both matter because XOR is associative and self-inverse, which is precisely what makes error detection and glitch-free encoding possible.

Why it matters

Parity is the simplest error-detection scheme there is — one bit that catches every single-bit corruption, used on serial links, in RAM, and inside more sophisticated codes. Gray code eliminates a whole class of hardware bug: when an ordinary binary counter steps from 0111 to 1000, four bits change and a reader that samples mid-transition can see a value that never existed. With Gray code exactly one bit changes per step, so an intermediate sample is always either the old value or the new one.

Core concepts

Parity by folding. XOR-ing a value with a shifted copy of itself combines the parity of two halves, because XOR is exactly addition modulo 2. x ^= x >> 16 merges the top and bottom halves; >> 8, >> 4, >> 2, >> 1 continue until the parity of the whole word sits in bit 0. Then x & 1u reads it. Five steps for 32 bits, versus 32 for a counting loop.

Why it works. Parity is the XOR of all bits. XOR is associative and commutative, so the bits can be combined in any grouping — the halving fold is just an efficient grouping.

Gray encoding. gray = x ^ (x >> 1). Adjacent values then differ in exactly one bit.

Gray decoding. The inverse is not symmetric — you must fold: x = g; x ^= x >> 1; x ^= x >> 2; x ^= x >> 4; x ^= x >> 8; x ^= x >> 16;. Forgetting that decode differs from encode is the usual mistake.

Unsigned only. Both rely on >> shifting in zeros; on a signed negative value it sign-extends and both results are wrong.

Syntax notes

int parity(unsigned x) {          // 1 if an odd number of bits are set
    x ^= x >> 16;
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return (int)(x & 1u);
}

unsigned binary_to_gray(unsigned x) { return x ^ (x >> 1); }

unsigned gray_to_binary(unsigned g) {   // NOT symmetric — must fold
    g ^= g >> 1;  g ^= g >> 2;  g ^= g >> 4;
    g ^= g >> 8;  g ^= g >> 16;
    return g;
}

Key points:

• The parity fold discards high garbage as it goes, so only bit 0 of the result is meaningful — always mask with & 1u.
• Encoding is one shift; decoding is a full fold.
• Use unsigned; a signed right shift breaks both.

Lesson

Parity is popcount mod 2 — a fold of XOR-shifts computes it fast. Gray code (x ^ (x>>1)) reorders values so consecutive ones differ by exactly one bit, avoiding glitches in encoders and simplifying Karnaugh maps.

The demo prints parities and the 3-bit Gray sequence.

Code examples

#include <stdio.h>
static int parity(unsigned x){ x^=x>>16; x^=x>>8; x^=x>>4; x^=x>>2; x^=x>>1; return (int)(x&1u); }
static unsigned binary_to_gray(unsigned x){ return x ^ (x>>1); }
int main(void){
    printf("parity(0x7) = %d  parity(0xF) = %d\n", parity(7u), parity(0xFu));
    printf("Gray code 0..7:");
    for(unsigned i=0;i<8;i++) printf(" %u", binary_to_gray(i));
    putchar('\n');
    return 0;
}

Line by line

Common mistakes

Returning the popcount instead of its low bit; OR-ing instead of XOR-ing for Gray.

Debugging tips

Compiler errors and warnings:

• warning: right shift count >= width of type — you added a >> 32 fold step to a 32-bit value.
• No warning for using encode where decode was needed — that is a logic bug only tests will catch.

Runtime symptoms:

• Parity is sometimes 2 or 3. You forgot the final & 1u; the fold leaves garbage above bit 0.
• Parity is wrong for large values. You started the fold at >> 8 instead of >> 16, so the top half was never merged.
• Gray decoding returns nonsense. You applied g ^ (g >> 1) again. Decoding needs the full fold, not the inverse-looking single shift.
• Everything breaks for values with the top bit set. Signed type — the right shift is sign-extending.

Technique: verify gray_to_binary(binary_to_gray(x)) == x over random values, and check that popcount(gray(i) ^ gray(i+1)) == 1 for a range of i — that is the defining property of Gray code.

Memory safety

• Signed right shift. The recurring hazard: >> on a signed negative value sign-extends, so both the parity fold and Gray decoding produce wrong answers. Use unsigned/uint32_t.
• Fold width must match the type. A 64-bit parity needs a leading x ^= x >> 32; a 32-bit fold applied to a 64-bit value silently ignores the top half. Conversely >> 32 on a 32-bit value is undefined.
• Only bit 0 is meaningful. The parity fold deliberately leaves debris in the upper bits. Never compare the raw folded value; always mask.
• Parity is not integrity. A single parity bit detects an odd number of flipped bits and nothing more — two flips cancel. It is an error detection hint, never a substitute for a checksum or a MAC in security contexts.

Real-world uses

Concrete uses: UART frames carry an optional parity bit; ECC memory builds on parity across groups of bits. RAID relies on XOR parity to rebuild a lost drive. Rotary encoders and absolute position sensors output Gray code so a sample taken during a transition is never a wild value. Clock-domain-crossing FIFOs in FPGAs pass their pointers as Gray code for the same reason. Karnaugh maps are ordered by Gray code.

Professional best practices:

Beginner:

• Always mask the parity result with & 1u.
• Remember encode and decode are different shapes — one shift versus a fold.

Intermediate:

• Test Gray code by its defining property (adjacent values differ in exactly one bit) rather than against hard-coded tables.
• Match the fold width to the type, ideally derived from sizeof.
• Do not present parity as an integrity guarantee; use a CRC for accidental corruption and a MAC for adversarial tampering.

Practice tasks

1. (Beginner) Parity two ways. Implement parity with the XOR fold and a second version that counts bits and takes the remainder mod 2; confirm they agree on 1,000 random values. Example: 0b1011 → 1. Concepts: XOR folding, oracle testing.

2. (Beginner) Encode Gray code. Implement binary_to_gray and print i and gray(i) in binary for i in 0..15. Concepts: x ^ (x>>1).

3. (Intermediate) Decode Gray code. Implement gray_to_binary with the full fold and assert the round trip over random values. Requirements: must not simply reapply the encode step. Concepts: asymmetric inverse.

4. (Intermediate) Prove the property. Write a test asserting popcount(gray(i) ^ gray(i+1)) == 1 for i in 0..1000. Concepts: the defining property of Gray code, reuse of popcount.

Summary

XOR underpins both tricks. Parity is the XOR of every bit, computed efficiently by folding the word in half repeatedly (>>16, >>8, >>4, >>2, >>1) until the answer lands in bit 0 — which you must then isolate with & 1u, because the fold leaves debris above it. Gray code, x ^ (x >> 1), numbers values so that neighbours differ in exactly one bit, eliminating the multi-bit transition glitch that plagues binary counters; decoding is not symmetric and needs a full fold. Keep everything unsigned, match the fold width to the type, and remember a parity bit detects simple corruption — it is not an integrity guarantee.

Practice with these exercises

• Compute parity
• Binary to Gray code