Data Structure Bit Operations

Why Bit Operations Matter in Data Structures

Early in my career, I treated data structures as abstract concepts — linked lists, binary trees, hash maps — each with a clean API and a big-O time complexity. The actual bits inside them seemed like an implementation detail that the compiler would handle. Then I spent a week chasing a performance bug and discovered that my hash table's modulo operation alone was consuming 5% of total CPU time. Replacing it with a bitwise AND was a one-line fix.

Bit operations matter in data structures for two fundamental reasons: speed and density. Bitwise AND, OR, XOR, NOT, and shift execute in 1 clock cycle on modern CPUs — they are the fastest operations available. Compare this to modulo (20-80 cycles) or multiplication (3-10 cycles). And at the density level, storing information in individual bits rather than bytes or words enables 8x to 64x memory savings. These two factors together make bit operations indispensable in high-performance data structure design.

I keep a utility library with bit-based data structures — bit arrays, bitsets, rank-select structures — that I reuse across projects. The common thread is that all of them use bitwise AND, OR, and shift as their fundamental operations. Once you are comfortable at the bit level, implementing these structures feels natural.

Bit Operations by Data Structure

Bitset / Bit Array

Bitsets are the simplest bit-level data structure: a contiguous array of bits where each bit represents a boolean. Every operation on a bitset is a bitwise operation — set uses OR, clear uses AND NOT, toggle uses XOR, and test uses AND. Bulk operations (union, intersection, difference) apply the same operation word by word across the entire array, processing 32 or 64 bits per instruction.

// Bitset operations — all bitwise
void set(char *bitset, int pos) {
    bitset[pos >> 3] |= 1 << (pos & 7);    // OR
}
void clear(char *bitset, int pos) {
    bitset[pos >> 3] &= ~(1 << (pos & 7)); // AND NOT
}
int test(char *bitset, int pos) {
    return (bitset[pos >> 3] >> (pos & 7)) & 1; // shift + AND
}
void toggle(char *bitset, int pos) {
    bitset[pos >> 3] ^= 1 << (pos & 7);    // XOR
}

Bloom Filter

Bloom filters extend the bitset concept with multiple hash functions for probabilistic membership testing. The core operations remain bitwise: insertion uses OR to set k bits, and queries use AND to test all k bits. The false positive rate is bounded by the bit array size, number of hash functions, and number of inserted elements.

Hash Table (Power-of-Two)

Modern hash tables derive enormous performance from one trick: keeping the bucket count a power of two. This enables bucket selection via hash & (capacity - 1) — a single AND instruction — instead of modulo. During rehashing, each entry's new bucket is determined by a single bit of the hash: hash & oldCapacity. Java's HashMap, Rust's HashMap (hashbrown), and Go's map all use this pattern.

Binary Indexed Tree (Fenwick Tree)

A BIT uses the lowbit operation — x & -x — for both query and update traversal. Query subtracts lowbit repeatedly: while (k > 0) { sum += tree[k]; k -= k & -k; }. Update adds lowbit: while (k <= n) { tree[k] += delta; k += k & -k; }. Both operations run in O(log n) time using nothing but bitwise AND and subtraction.

Binary Trie (Radix Tree / Patricia Trie)

A binary trie stores strings one bit at a time rather than one character at a time. Each node has two children (bit 0 and bit 1), and navigation uses a single bit of the key: node = node.children[(key >> bit) & 1]. This is the data structure behind IP routing tables — routers use Patricia tries for longest-prefix matching in O(bits) time. The entire routing table for the internet fits in a binary trie of maybe a million nodes.

// Binary trie insertion — one bit at a time
typedef struct TrieNode {
    struct TrieNode *children[2]; // child[0] for bit=0, child[1] for bit=1
    int isEnd;
} TrieNode;

void insert(TrieNode *root, unsigned int key, int bits) {
    TrieNode *node = root;
    for (int i = bits - 1; i >= 0; i--) {
        int bit = (key >> i) & 1; // extract one bit using shift + AND
        if (!node->children[bit]) {
            node->children[bit] = calloc(1, sizeof(TrieNode));
        }
        node = node->children[bit];
    }
    node->isEnd = 1;
}

// Longest-prefix match (used in CIDR routing)
int longestPrefix(TrieNode *root, unsigned int key, int bits) {
    TrieNode *node = root;
    int lastMatch = -1;
    for (int i = bits - 1; i >= 0; i--) {
        int bit = (key >> i) & 1;
        if (!node->children[bit]) break;
        node = node->children[bit];
        if (node->isEnd) lastMatch = i;
    }
    return lastMatch;
}

Priority Queue (d-ary Heap)

In a binary heap, the parent of index i is floor((i-1)/2), and children are at 2i+1 and 2i+2. For a 4-ary heap, children are at 4i+1 through 4i+4, and the parent is floor((i-1)/4). When d is a power of two, these index computations reduce to shifts: parent = (i - 1) >> log2(d). This matters in Dijkstra's algorithm and other graph algorithms where a d-ary heap with d=4 or d=8 is measurably faster than a binary heap.

Bit Packing: Storing More in Less Space

Bit packing — storing multiple small values within a single machine word — is the density counterpart to the speed of bitwise operations. The pattern is universal: use shift-AND to extract fields and OR-shift to insert them.

// Bit packing example: RGBA color (4 × 8-bit channels in one 32-bit word)
const rgba = (r, g, b, a) =>
    (r << 24) | (g << 16) | (b << 8) | a;

const getRed   = (pixel) => (pixel >> 24) & 0xFF;
const getGreen = (pixel) => (pixel >> 16) & 0xFF;
const getBlue  = (pixel) => (pixel >>  8) & 0xFF;
const getAlpha = (pixel) => (pixel >>  0) & 0xFF;

// Example: 0x3FB87AFF = R:0x3F, G:0xB8, B:0x7A, A:0xFF
// Packed: 1 word (4 bytes). Unpacked in struct: 16+ bytes (with padding)

Bit packing is used throughout systems programming: TCP/IP packet headers pack fields into 16-bit words, file permission bits pack rwx triples into 12 bits, x86 instruction encoding packs opcode, registers, and addressing modes into variable-length bit sequences. Everywhere that data crosses a wire or a memory bus, bit packing reduces bandwidth and improves throughput.

Choosing the Right Bit-Optimized Structure

Over the years, I have developed a mental checklist for when to apply bit-level optimization to a data structure problem:

• Pure membership test (is element x in the set?) — use a bloom filter if false positives are acceptable, a bitset if the universe is small and bounded
• Small boolean flags (up to 64 flags) — pack them into a single integer with bitwise get/set/clear/toggle operations
• Large integer datasets with known range — use bitmap sort or a bitset for deduplication and queries
• Dynamic prefix sums (lots of queries and updates) — use a Binary Indexed Tree with lowbit traversal
• String prefix matching (autocomplete, routing) — use a binary trie or radix tree with bit-level node navigation
• Hash table with known approximate size — use power-of-two capacity and the AND trick
• Sorting millions of fixed-width integers — use binary radix sort with bit extraction

The unifying principle: if your data structure involves integers, and if those integers represent values in a known range or pattern, bit-level operations can almost certainly make it faster and more memory-efficient.