Bitmap Algorithm

What Is a Bitmap Algorithm?

The first time I needed to sort a billion 32-bit integers on a machine with only 2 GB of RAM, I knew the standard quicksort approach wasn't going to work. Loading a billion integers into memory would require 4 GB just for the data. That is when I discovered bitmap algorithms — techniques that use bit arrays to represent data at the bit level, achieving massive memory savings by trading some generality for space efficiency.

A bitmap (or bit array) is an array of bits where each bit represents the presence or absence of an element. If the element at position i is in the set, bit i is 1. Otherwise, it is 0. Instead of storing the actual values — which takes 32 or 64 bits per integer — you store just a single bit per possible value. For dense datasets where the range is not much larger than the number of elements, this is a transformative optimization.

For a URL deduplication system, I implemented a bitmap-based set that could track 100 million entries in under 12 MB of memory. The key was using multiple rotating bitmaps to handle the high insertion rate.

Bitmap Sort: The Classic Example

Bitmap sort was described by Jon Bentley in his classic book "Programming Pearls," and it remains one of the most elegant demonstrations of bit-level algorithmic thinking. The algorithm works in three passes:

1. Initialize: Set all bits in the bitmap to 0.
2. Read and set: For each integer x in the input, set bit x to 1 using bitwise OR.
3. Scan and output: Iterate through the bitmap from low to high. For each bit that is 1, output its position index.

The output is automatically sorted in ascending order, and duplicates are automatically removed. Time complexity is O(n + range), which reduces to O(n) when the range is proportional to n. Space complexity is O(range) bits.

function bitmapSort(nums, maxValue) {
    // Each byte stores 8 bits — allocate (maxValue + 8) / 8 bytes
    const bitmap = new Uint8Array(Math.ceil((maxValue + 1) / 8));

    // Phase 1: set bits for each number
    for (const x of nums) {
        const byteIdx = x >> 3;         // x / 8
        const bitIdx = x & 0x07;         // x % 8
        bitmap[byteIdx] |= (1 << bitIdx); // set bit using OR
    }

    // Phase 2: scan bitmap and output sorted values
    const result = [];
    for (let i = 0; i <= maxValue; i++) {
        const byteIdx = i >> 3;
        const bitIdx = i & 0x07;
        if (bitmap[byteIdx] & (1 << bitIdx)) { // test bit using AND
            result.push(i);
        }
    }
    return result;
}

// Example: sort [3, 7, 1, 3, 5, 9] with maxValue = 10
// Output: [1, 3, 5, 7, 9] — sorted and deduplicated

Memory Comparison: Bitmap vs Conventional

Here is a concrete breakdown that I use when deciding whether a bitmap algorithm is appropriate for a problem. For a range of 0 to 1,000,000:

The crossover point depends on the density of your data. With a 32-bit integer array (4 bytes per element), the bitmap is more memory-efficient when the number of distinct elements exceeds (range / 32). That is only about 3% density. For many real-world datasets — IP addresses, user IDs, sensor readings — the range is large but the density is low, so bitmap algorithms become even more attractive.

I once optimized a network traffic analysis pipeline that was tracking which source IPs had been seen in each 5-minute window. With the bitmap approach, processing 1 million unique IPs across the 32-bit IPv4 range took 512 MB of bitmap memory — which was acceptable for our server. The previous implementation used a hash set and consumed over 4 GB.

Bitwise Operations on Bitmaps

The real power of bitmap algorithms becomes apparent when you need to perform set operations on large datasets. Because a bitmap is just an array of bits, set operations reduce to fast bitwise word-level operations.

// Set operations on bitmaps using 32-bit word-level operations

// Union: A ∪ B
function bitmapUnion(a, b, wordCount) {
    const result = new Uint32Array(wordCount);
    for (let i = 0; i < wordCount; i++) {
        result[i] = a[i] | b[i];  // bitwise OR
    }
    return result;
}

// Intersection: A ∩ B
function bitmapIntersection(a, b, wordCount) {
    const result = new Uint32Array(wordCount);
    for (let i = 0; i < wordCount; i++) {
        result[i] = a[i] & b[i];  // bitwise AND
    }
    return result;
}

// Difference: A \ B
function bitmapDifference(a, b, wordCount) {
    const result = new Uint32Array(wordCount);
    for (let i = 0; i < wordCount; i++) {
        result[i] = a[i] & ~b[i]; // bitwise AND NOT
    }
    return result;
}

On modern CPUs, these bitwise operations process 32 or 64 bits per instruction cycle. For a 1-million-bit bitmap, the union, intersection, or difference completes in under a microsecond. This is the foundation for high-performance data processing in databases, search engines, and analytics platforms.

Real-World: EWAH and Roaring Bitmaps

Plain bitmaps have a problem: if your dataset is sparse — only 1% of bits are set — you waste 99% of memory on zeros. Two optimized bitmap formats solve this. EWAH (Enhanced Word-Aligned Hybrid) compresses runs of consecutive zero words using a single marker word. Roaring Bitmaps, developed at the University of Lyon and now used by Apache Druid, Spark SQL, and Elasticsearch, take a different approach: they partition the bitmap into 16-bit chunks and use either an array or a bitmap per chunk depending on density. Roaring is faster than EWAH for most real-world workloads and is my default choice when I need bitmap operations in production.

Applications in Practice

Database Indexing

PostgreSQL uses BRIN (Block Range INdex) indexes that store a bitmap summary of each block range. When a query filters on the indexed column, PostgreSQL checks the bitmap before scanning the block — skipping entire ranges that cannot contain matching rows. This is identical in spirit to the bitmap sort algorithm.

Time-Series Databases

InfluxDB uses bitmaps for its tag index system. Each tag value (like "host=server01") has an associated bitmap where bit i is 1 if that tag value appears in the i-th series. Queries like "find all series where host=server01 AND region=us-east" reduce to a bitwise AND between two bitmaps — a single CPU instruction per 32 or 64 series.

Audience Targeting

Ad platforms represent user segments as bitmaps. Segment A (users interested in sports) and Segment B (users aged 18-35) each have a bitmap over the user ID space. To find the intersection for a targeting campaign, the platform performs a bitwise AND. The result is a bitmap of user IDs who match all criteria, computed in microseconds.

// Audience targeting with bitwise operations
const sportsLovers = loadBitmap("segment_sports");     // 1M users
const age18to35 = loadBitmap("segment_age_18_35");    // 800K users
const premiumUsers = loadBitmap("segment_premium");    // 200K users

// Target: sports lovers aged 18-35 who are also premium users
const target = bitmapIntersection(
    bitmapIntersection(sportsLovers, age18to35),
    premiumUsers
);
// Result: ~50K matching user IDs in under 100 microseconds