Bitsets and Hamming distance

Overview

Scale the single-word techniques up and you get a bitset: an array of words where bit i of the whole structure lives at bit i % 32 of word i / 32. That layout stores a membership set at one bit per element — 32 times denser than an array of int flags — and makes union, intersection and difference into simple word-wise OR, AND and AND-NOT. Hamming distance, the number of positions at which two values differ, falls straight out of the same toolkit: XOR reveals exactly the differing bits, and popcount counts them.

Why it matters

Density is the point. A bitset over a million elements fits in 128 KB and stays in cache, where an array of booleans would need a megabyte and an array of int four. That is why kernels track free blocks, garbage collectors track marked objects, and databases build bitmap indexes this way. Hamming distance, meanwhile, is the standard measure of similarity for hashes and codes — used for near-duplicate detection, error correction, and comparing perceptual image hashes.

Core concepts

The index split. For bit i: the word index is i / 32 (or i >> 5) and the bit index within that word is i % 32 (or i & 31). Every bitset operation is these two numbers plus the single-word primitives from earlier lessons.

Set, clear, test. bs[i>>5] |= 1u << (i & 31), bs[i>>5] &= ~(1u << (i & 31)), (bs[i>>5] >> (i & 31)) & 1u.

Word-wise set algebra. Union is a[w] | b[w], intersection a[w] & b[w], difference a[w] & ~b[w], each looped over the words — 32 elements processed per operation.

Population count. The bitset's cardinality is the sum of the popcounts of its words; use Kernighan's loop per word.

Hamming distance. popcount(a ^ b). XOR yields 1 exactly where the operands differ, so counting those 1s counts the differing positions. For multi-word values, sum per word.

Sizing. A bitset for n bits needs (n + 31) / 32 words — the round-up-division idiom, which is the alignment arithmetic from the previous lesson in disguise.

Syntax notes

#include <stdint.h>
#include <string.h>

#define BITS_PER_WORD 32
#define WORDS_FOR(n)  (((n) + BITS_PER_WORD - 1) / BITS_PER_WORD)   // round up

static void bs_set  (uint32_t *bs, int i) { bs[i >> 5] |=  1u << (i & 31); }
static void bs_clear(uint32_t *bs, int i) { bs[i >> 5] &= ~(1u << (i & 31)); }
static int  bs_test (const uint32_t *bs, int i) { return (int)((bs[i >> 5] >> (i & 31)) & 1u); }

int hamming_distance(uint32_t a, uint32_t b) {
    uint32_t x = a ^ b;            // 1 wherever they differ
    int c = 0;
    while (x) { c++; x &= x - 1u; }
    return c;
}

Key points:

• i >> 5 and i & 31 are the same as /32 and %32 for non-negative i, and make the word/bit split explicit.
• WORDS_FOR(n) must round up, or the last few bits have nowhere to live.
• Zero the array (memset(bs, 0, WORDS_FOR(n) * sizeof *bs)) before use — allocation does not.

Lesson

A bitset packs a set of small integers into an array of words — membership is one bit, and its size is a per-word popcount sum. Hamming distance, popcount(a ^ b), counts the bit positions where two values differ.

The demo sums a 3-word bitset and measures a distance.

Code examples

#include <stdio.h>
#include <stdint.h>
static int bitset_count(const uint32_t *bs,int n){ int c=0; for(int w=0;w<n;w++){ uint32_t x=bs[w]; while(x){ c+=(int)(x&1u); x>>=1; } } return c; }
static int hamming_distance(unsigned a,unsigned b){ unsigned x=a^b; int c=0; while(x){ c+=(int)(x&1u); x>>=1; } return c; }
int main(void){
    uint32_t set[] = {0x0000000Fu, 0xF0000000u, 0x00FF0000u};  /* 3-word bitset */
    printf("bitset population = %d\n", bitset_count(set, 3));
    printf("hamming(0x1234, 0x1256) = %d\n", hamming_distance(0x1234u, 0x1256u));
    return 0;
}

Line by line

Common mistakes

Reading past the word count; comparing values instead of XOR-ing.

Debugging tips

Compiler errors and warnings:

• warning: array subscript is above array bounds — your WORDS_FOR rounded down, or the index exceeded the capacity.
• -Wsign-compare mixing an int index with an unsigned word count.

Runtime symptoms:

• The last few elements misbehave or corrupt the heap. WORDS_FOR used n / 32 without rounding up, so the final partial word is missing. This is an out-of-bounds write.
• Random bits appear set on a fresh bitset. You allocated with malloc and never zeroed it. Use calloc or memset.
• Every bit lands in word 0. You wrote i & 5 / i >> 31 — the shift and mask are swapped. It is i >> 5 for the word, i & 31 for the bit.
• Hamming distance is always 0 or 32. You used & or | instead of ^, or compared a value with itself.
• Negative index. i >> 5 on a negative int is implementation-defined; validate i >= 0 first.

Technique: test the boundaries — bits 0, 31, 32, 63 and n-1 — because word-crossing is where the index arithmetic breaks.

Memory safety

A bitset is a real array, so ordinary memory-safety rules apply on top of the bit arithmetic:

• Bounds. bs_set(bs, i) with i >= n writes past the end — a genuine buffer overflow. Store the capacity alongside the array and validate every index; the bit arithmetic itself offers no protection.
• Round the size up. (n + 31) / 32 — using n / 32 silently under-allocates and every access to the final partial word is out of bounds.
• Initialise. malloc returns garbage; a bitset must be zeroed with calloc or memset before use or membership tests read indeterminate values.
• Index type. Use a non-negative type (or check i >= 0); >> on a negative signed value is implementation-defined and the resulting index may be wrong.
• Overflow in sizing. (n + 31) can wrap for an n near the maximum, producing a tiny allocation — check untrusted sizes before computing the word count.

Real-world uses

Concrete uses: Filesystems track free blocks and inodes in bitmaps. Garbage collectors keep mark bits per object. Databases use bitmap indexes to answer multi-predicate queries with word-wise ANDs. Bloom filters are bitsets. CPU affinity masks and select()'s fd_set are bitsets. Hamming distance compares perceptual image hashes for near-duplicate detection and measures codeword separation in error-correcting codes.

Professional best practices:

Beginner:

• Always round the word count up, and always zero the array.
• Keep the capacity next to the pointer and bounds-check every index.

Intermediate:

• Wrap the bitset in a small struct ({ uint32_t *w; size_t nbits; }) so the capacity cannot drift away from the data.
• Process word-at-a-time for bulk operations rather than bit-at-a-time — that is the entire performance argument for the layout.
• For similarity work, remember Hamming distance is meaningful only between equal-length codes; compare hashes of the same algorithm and width.

Practice tasks

1. (Beginner) Bitset basics. Implement bs_set, bs_clear and bs_test over a uint32_t array, plus WORDS_FOR(n). Requirements: zero the array before use. Example: set 70, test 70 → 1; test 71 → 0. Concepts: index split, rounding up.

2. (Beginner) Hamming distance. Implement int hamming_distance(uint32_t a, uint32_t b). Example: 0b1100 vs 0b1010 → 2; equal values → 0. Concepts: XOR then popcount.

3. (Intermediate) Bitset cardinality and union. Implement bitset_count and bitset_union (word-wise OR into a destination). Requirements: both take the word count explicitly. Concepts: word-wise set algebra.

4. (Intermediate) Bounds-checked wrapper. Wrap the bitset in a struct carrying nbits, and make set/test reject out-of-range indices instead of writing past the end. Concepts: encapsulating an invariant, buffer-overflow prevention.

Summary

A bitset stores one bit per element by splitting an index into a word (i >> 5) and a bit within it (i & 31), giving 32× the density of a byte-per-flag array and turning set union, intersection and difference into word-wise OR, AND and AND-NOT. Size it with a rounded-up (n + 31) / 32 words, zero it before use, and bounds-check every index — the bit arithmetic will happily write past the end otherwise. Hamming distance reuses the same toolkit: XOR marks the differing positions and popcount counts them.

Practice with these exercises

• Population count of a bitset
• Hamming distance