Project 12: Bit Module - Bit Vector Operations

Build a bit vector (bit array) ADT supporting set/clear/test operations plus set-theoretic operations (union, intersection, difference) on bits.

Quick Reference

Attribute Value
Difficulty Level 3 - Advanced
Time Estimate 4-6 days
Language C
Prerequisites Mem module, Assert module, Understanding of bitwise operators
Key Topics Bit manipulation, Set theory, Memory optimization, Word packing

1. Learning Objectives

By completing this project, you will:

  1. Master bit manipulation - Become fluent in bitwise AND, OR, XOR, NOT, and shift operations
  2. Implement space-efficient data structures - Store 1 bit per boolean instead of 8, 16, or 32 bits
  3. Apply set theory computationally - Union, intersection, difference, and symmetric difference as bitwise operations
  4. Handle word boundaries - Map bit indices to word indices and bit positions within words
  5. Optimize for performance - Use hardware popcount and find-first-set instructions

Why Bit Vectors Matter:

Bit vectors are the ultimate space optimization for boolean data:

  • Databases: Bitmap indices can represent millions of rows in kilobytes
  • Bloom Filters: Probabilistic data structures for set membership
  • Compilers: Live variable analysis, register allocation
  • File Systems: Free block tracking (ext4, NTFS)
  • Network Routers: Packet classification and ACL matching
  • Memory Allocators: Free block bitmaps

A bit vector storing 1 million booleans uses only 125KB, compared to 1MB for a char array or 4MB for an int array.

2. Theoretical Foundation

2.1 Core Concepts

Bit Manipulation Fundamentals

Bitwise Operations in C
--------------------------------------------------------------------------------

Given: a = 0b11001010, b = 0b10101100

AND (&): Both bits must be 1
    11001010 & 10101100 = 10001000
    Use: Clear specific bits, test if bit is set

OR (|): Either bit can be 1
    11001010 | 10101100 = 11101110
    Use: Set specific bits

XOR (^): Bits must differ
    11001010 ^ 10101100 = 01100110
    Use: Toggle bits, find differences

NOT (~): Flip all bits
    ~11001010 = 00110101 (in 8 bits)
    Use: Invert mask, clear bits

Left Shift (<<): Multiply by 2^n
    11001010 << 2 = 00101000 (bits fall off left)
    Use: Create bit masks, multiply

Right Shift (>>): Divide by 2^n
    11001010 >> 2 = 00110010
    Use: Test bits, divide

Common Idioms:
    Set bit n:     x |= (1UL << n)
    Clear bit n:   x &= ~(1UL << n)
    Toggle bit n:  x ^= (1UL << n)
    Test bit n:    (x >> n) & 1   or   (x & (1UL << n)) != 0

Word Packing

Bit vectors store bits packed into machine words. The key insight is mapping a bit index to a word index and bit position:

Bit Vector Word Packing
--------------------------------------------------------------------------------

Bit vector of 200 bits using 64-bit words:
    - Need ceil(200/64) = 4 words
    - Words: [word0, word1, word2, word3]

                      Word 0                    Word 1
    ┌─────────────────────────────────┬─────────────────────────────────┐
    │ bits 0-63                       │ bits 64-127                     │
    │ [63][62]...[2][1][0]           │ [127][126]...[66][65][64]       │
    └─────────────────────────────────┴─────────────────────────────────┘

                      Word 2                    Word 3
    ┌─────────────────────────────────┬─────────────────────────────────┐
    │ bits 128-191                    │ bits 192-199 (+ 56 unused)      │
    │ [191][190]...[130][129][128]   │ [199]...[192][unused...]        │
    └─────────────────────────────────┴─────────────────────────────────┘

To access bit n:
    word_index = n / BITS_PER_WORD    (or n >> 6 for 64-bit)
    bit_position = n % BITS_PER_WORD  (or n & 63 for 64-bit)
    mask = 1UL << bit_position

Example: Access bit 100
    word_index = 100 / 64 = 1
    bit_position = 100 % 64 = 36
    mask = 1UL << 36 = 0x0000001000000000

    Set:   words[1] |= mask
    Clear: words[1] &= ~mask
    Test:  (words[1] & mask) != 0

Set Operations on Bit Vectors

Set theory maps directly to bitwise operations:

Set Operations as Bit Operations
--------------------------------------------------------------------------------

Given bit vectors A and B representing sets:

UNION (A ∪ B): Elements in A OR B
    for each word i:
        result[i] = A[i] | B[i]

    Example:
    A = {0, 2, 4, 6}  →  bits: 01010101
    B = {1, 3, 5, 7}  →  bits: 10101010
    A ∪ B             →  bits: 11111111 = {0,1,2,3,4,5,6,7}

INTERSECTION (A ∩ B): Elements in A AND B
    for each word i:
        result[i] = A[i] & B[i]

    Example:
    A = {0, 1, 2, 3}  →  bits: 00001111
    B = {2, 3, 4, 5}  →  bits: 00111100
    A ∩ B             →  bits: 00001100 = {2, 3}

DIFFERENCE (A - B): Elements in A but not B
    for each word i:
        result[i] = A[i] & ~B[i]

    Example:
    A = {0, 1, 2, 3}  →  bits: 00001111
    B = {2, 3, 4, 5}  →  bits: 00111100
    A - B             →  bits: 00000011 = {0, 1}

SYMMETRIC DIFFERENCE (A △ B): Elements in A or B but not both
    for each word i:
        result[i] = A[i] ^ B[i]

    Example:
    A = {0, 1, 2, 3}  →  bits: 00001111
    B = {2, 3, 4, 5}  →  bits: 00111100
    A △ B             →  bits: 00110011 = {0, 1, 4, 5}

COMPLEMENT (~A): Elements NOT in A
    for each word i:
        result[i] = ~A[i]
    (Need to mask unused bits in last word)

Population Count (Popcount)

Counting set bits is a fundamental operation:

Population Count Algorithms
--------------------------------------------------------------------------------

Goal: Count the number of 1 bits in a word

Naive approach: O(n) where n = word size
    int count = 0;
    while (x) {
        count += x & 1;
        x >>= 1;
    }

Brian Kernighan's trick: O(k) where k = number of set bits
    int count = 0;
    while (x) {
        count++;
        x &= x - 1;  // Clears lowest set bit!
    }

    Why it works:
    x       = 01101000
    x - 1   = 01100111
    x & x-1 = 01100000  (lowest 1 bit cleared!)

Hardware instruction (fastest):
    __builtin_popcountl(x)  // GCC/Clang
    _mm_popcnt_u64(x)       // Intel intrinsic
    popcount(x)             // CPU instruction directly

Lookup table approach:
    Pre-compute popcount for all byte values (256 entries)
    Sum popcount of each byte in word

2.2 Why This Matters

Bit vectors enable algorithms that would be impractical otherwise:

Space Efficiency: | Data Type | Space for 1M booleans | |———–|———————-| | int array | 4,000,000 bytes | | char array | 1,000,000 bytes | | Bit vector | 125,000 bytes |

Applications:

  1. Bloom Filters: Probabilistic set membership
    • Hash elements to bit positions
    • Union of multiple hash functions
    • No false negatives, small false positive rate
  2. Bitmap Indices (Databases):
    • Each column value gets a bit vector
    • Query: WHERE color='red' AND size='large'
    • Implementation: red_bits & large_bits
  3. Memory Allocators:
    • Track free/used blocks with bits
    • Find first free: __builtin_ffsl(free_bitmap)
  4. Network ACLs:
    • Each rule is a bit in a bitmap
    • Matching: AND rule bitmaps together

2.3 Historical Context

Bit manipulation has been fundamental since the earliest computers:

  • 1950s: EDSAC used bit fields for instruction encoding
  • 1960s: Bloom filters invented (Burton Bloom, 1970)
  • 1970s: Bitmap indices for databases (research papers)
  • 1980s: GIF image format uses bit-packed pixel data
  • 1990s: PostgreSQL implements bitmap index scans
  • 2000s: Roaring Bitmaps for compressed bit vectors
  • Today: AVX-512 can process 512 bits in one instruction

2.4 Common Misconceptions

Misconception 1: “Bit manipulation is only for embedded systems”

  • Reality: High-performance databases, compilers, and network stacks rely heavily on bit operations.

Misconception 2: “Modern compilers optimize byte arrays to bit vectors”

  • Reality: Compilers cannot change data layout. You must explicitly choose bit vectors.

Misconception 3: “Popcount requires a loop”

  • Reality: Modern CPUs have hardware popcount instructions (SSE4.2, AVX2).

Misconception 4: “Bit vectors are harder to debug”

  • Reality: With proper abstractions (like this Bit module), they’re as debuggable as any data structure.

3. Project Specification

3.1 What You Will Build

A complete Bit module implementing Hanson’s CII interface:

// bit.h - The Interface

#ifndef BIT_INCLUDED
#define BIT_INCLUDED

#define T Bit_T
typedef struct T *T;

/* Creation and destruction */
extern T    Bit_new   (int length);
extern void Bit_free  (T *set);

/* Properties */
extern int  Bit_length(T set);
extern int  Bit_count (T set);  /* Number of set bits (popcount) */

/* Single-bit operations */
extern int  Bit_get   (T set, int n);                    /* Test bit n */
extern int  Bit_put   (T set, int n, int bit);           /* Set/clear bit n */
extern void Bit_set   (T set, int lo, int hi);           /* Set bits [lo, hi] */
extern void Bit_clear (T set, int lo, int hi);           /* Clear bits [lo, hi] */
extern void Bit_not   (T set, int lo, int hi);           /* Toggle bits [lo, hi] */

/* Set operations (modify set in place) */
extern void Bit_union     (T s, T t);   /* s = s ∪ t */
extern void Bit_inter     (T s, T t);   /* s = s ∩ t */
extern void Bit_minus     (T s, T t);   /* s = s - t */
extern void Bit_diff      (T s, T t);   /* s = s △ t (symmetric) */

/* Comparison */
extern int  Bit_eq    (T s, T t);       /* s == t */
extern int  Bit_subset(T s, T t);       /* s ⊆ t */
extern int  Bit_lt    (T s, T t);       /* s ⊂ t (proper subset) */
extern int  Bit_leq   (T s, T t);       /* s ⊆ t (same as subset) */

/* Utility */
extern void Bit_map   (T set, void apply(int n, int bit, void *cl), void *cl);

#undef T
#endif

3.2 Functional Requirements

  1. Bit_new(length): Create a bit vector of length bits, all initially 0
  2. Bit_free(&set): Deallocate and set pointer to NULL
  3. Bit_length(set): Return the number of bits (not words)
  4. Bit_count(set): Return number of set bits (population count)
  5. Bit_get(set, n): Return 1 if bit n is set, 0 otherwise
  6. Bit_put(set, n, bit): Set bit n to bit (0 or 1), return previous value
  7. Bit_set(set, lo, hi): Set all bits in range [lo, hi] to 1
  8. Bit_clear(set, lo, hi): Clear all bits in range [lo, hi] to 0
  9. Bit_not(set, lo, hi): Toggle all bits in range [lo, hi]
  10. Set operations: Union, intersection, difference, symmetric difference
  11. Comparison: Equality, subset, proper subset

3.3 Non-Functional Requirements

  1. Space efficient: 1 bit per element (plus small overhead)
  2. Time efficient: O(n/w) for operations where w = word size
  3. Portable: Handle different word sizes (32-bit and 64-bit)
  4. Bounds checking: Assert on out-of-range bit indices
  5. Length matching: Set operations require equal-length vectors

3.4 Example Usage / Output

$ ./bit_test

# Test 1: Basic bit operations
Created bit vector of 1000 bits
Setting bits: 0, 7, 42, 999
Testing bit 0: SET
Testing bit 1: CLEAR
Testing bit 42: SET
Testing bit 1000: ERROR - index out of range

# Test 2: Counting
Set 100 random bits...
Bit count (popcount): 100

# Test 3: Set operations
Vector A: bits {0, 1, 2, 3, 4}
Vector B: bits {3, 4, 5, 6, 7}
A ∪ B (union): {0, 1, 2, 3, 4, 5, 6, 7}
A ∩ B (intersection): {3, 4}
A - B (difference): {0, 1, 2}
A △ B (symmetric diff): {0, 1, 2, 5, 6, 7}

# Test 4: Range operations
Bit vector of 64 bits, all clear
Bit_set(bits, 10, 20)
Bits set: {10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
Bit_clear(bits, 14, 16)
Bits set: {10, 11, 12, 13, 17, 18, 19, 20}
Bit_not(bits, 0, 63)  # Toggle all
Bits set: {0-9, 14-16, 21-63}

# Test 5: Bloom filter simulation
$ ./bloom_test
Bloom filter: 10000 bits, 3 hash functions
Adding 1000 words from dictionary...
Testing known words: 1000/1000 found (100%)
Testing random strings: 23/1000 false positives (2.3%)

# Test 6: Performance
$ ./bit_perf
Popcount of 1M-bit vector: 500123 bits set
Time with loop: 4.2 ms
Time with __builtin_popcountl: 0.3 ms
Speedup: 14x

4. Solution Architecture

4.1 High-Level Design

Bit Module Architecture
--------------------------------------------------------------------------------

                    ┌─────────────────────────────────────┐
                    │           bit.h (Interface)           │
                    │                                       │
                    │  Bit_T ─────► opaque pointer          │
                    │  Bit_new, Bit_free                    │
                    │  Bit_get, Bit_put, Bit_set, Bit_clear │
                    │  Bit_union, Bit_inter, Bit_minus      │
                    │  Bit_count, Bit_length                │
                    └─────────────────┬─────────────────────┘
                                      │
                    ┌─────────────────┴─────────────────────┐
                    │          bit.c (Implementation)        │
                    │                                       │
                    │  struct Bit_T {                       │
                    │      int length;      // Bits         │
                    │      int nwords;      // Words used   │
                    │      unsigned long *words;            │
                    │  }                                    │
                    │                                       │
                    │  Macros:                              │
                    │  WORD(n) = n / BPW                    │
                    │  BIT(n)  = n % BPW                    │
                    │  MASK(n) = 1UL << BIT(n)              │
                    │                                       │
                    └───────────────────────────────────────┘
                                      │
                    ┌─────────────────┴─────────────────────┐
                    │              Dependencies             │
                    │                                       │
                    │  mem.h ─────► ALLOC, FREE             │
                    │  assert.h ──► precondition checks     │
                    └───────────────────────────────────────┘

4.2 Key Components

Header File (bit.h):

  • Type definition (opaque pointer)
  • Function declarations organized by category
  • Include guards

Implementation File (bit.c):

  • Private struct definition
  • Helper macros for bit/word indexing
  • Optimized popcount implementation

4.3 Data Structures

// Internal representation
struct Bit_T {
    int length;              // Total number of bits
    int nwords;              // Number of words in array
    unsigned long *words;    // Array of words
};

// Constants (adjust for platform)
#define BPW (8 * sizeof(unsigned long))  // Bits per word (32 or 64)

// Helper macros
#define WORD(n)  ((n) / BPW)         // Which word contains bit n
#define BIT(n)   ((n) % BPW)         // Position within that word
#define MASK(n)  (1UL << BIT(n))     // Mask for bit n within its word

// Example: 200-bit vector on 64-bit system
//
// length = 200
// nwords = ceil(200/64) = 4
// words = [word0, word1, word2, word3]
//
// Bit 100 is in:
//   WORD(100) = 100/64 = 1
//   BIT(100)  = 100%64 = 36
//   MASK(100) = 1UL << 36

// IMPORTANT: The last word may have unused bits
// For 200 bits with 64-bit words:
//   Words 0-2: all 64 bits used
//   Word 3: only bits 0-7 used, bits 8-63 are padding
// These padding bits should be kept at 0 to avoid issues with comparison

4.4 Algorithm Overview

Single Bit Operations:

// Get bit n
int Bit_get(T set, int n) {
    assert(set && 0 <= n && n < set->length);
    return (set->words[WORD(n)] >> BIT(n)) & 1;
}

// Put bit n
int Bit_put(T set, int n, int bit) {
    int prev;
    assert(set && 0 <= n && n < set->length);
    assert(bit == 0 || bit == 1);

    prev = Bit_get(set, n);
    if (bit)
        set->words[WORD(n)] |= MASK(n);
    else
        set->words[WORD(n)] &= ~MASK(n);
    return prev;
}

Range Operations:

// Set bits [lo, hi]
void Bit_set(T set, int lo, int hi) {
    assert(set && 0 <= lo && lo <= hi && hi < set->length);

    if (WORD(lo) == WORD(hi)) {
        // All bits in same word
        set->words[WORD(lo)] |= mask_range(BIT(lo), BIT(hi));
    } else {
        // Spans multiple words
        set->words[WORD(lo)] |= mask_from(BIT(lo));  // lo word
        for (int i = WORD(lo)+1; i < WORD(hi); i++)
            set->words[i] = ~0UL;                     // middle words
        set->words[WORD(hi)] |= mask_to(BIT(hi));   // hi word
    }
}

Population Count:

int Bit_count(T set) {
    int count = 0;
    assert(set);

    for (int i = 0; i < set->nwords; i++) {
        // Use hardware popcount if available
        count += __builtin_popcountl(set->words[i]);
    }
    return count;
}

5. Implementation Guide

5.1 Development Environment Setup

# Required tools
gcc --version          # GCC 4.8+ for __builtin_popcountl
make --version
valgrind --version

# Check if your CPU supports popcount
grep popcnt /proc/cpuinfo

# Project structure
C_INTERFACES_AND_IMPLEMENTATIONS_MASTERY/
├── include/
│   ├── bit.h
│   ├── mem.h
│   └── assert.h
├── src/
│   ├── bit.c
│   ├── mem.c
│   └── assert.c
├── tests/
│   ├── bit_test.c
│   └── bloom_test.c
└── Makefile

# Compiler flags
CFLAGS = -Wall -Wextra -Wpedantic -std=c11 -g
CFLAGS += -mpopcnt  # Enable popcount instruction

5.2 Project Structure

bit.h          Interface (public API)
bit.c          Implementation (private details)
bit_test.c     Comprehensive test suite
bloom_test.c   Bloom filter demonstration

5.3 The Core Question You’re Answering

“How do you store and manipulate millions of boolean values with minimal memory while maintaining fast set operations?”

This is critical for:

  • Database bitmap indices handling billions of rows
  • Network filtering with millions of rules
  • Compilers analyzing thousands of variables
  • Memory allocators tracking millions of blocks

5.4 Concepts You Must Understand First

Before implementing, ensure you can answer:

  1. Bitwise operations: What is 0x0F & 0x3C? What about 0x0F | 0x3C?
  2. Shifting: What is 1 << 5? What about 0x80 >> 3?
  3. Word size: How many bits in unsigned long on your system?
  4. Modulo for powers of 2: Why is n & 63 the same as n % 64?

5.5 Questions to Guide Your Design

  1. Word size: Use unsigned long (platform-dependent) or fixed-width uint64_t?
  2. Bit order: Is bit 0 the LSB or MSB of the first word?
  3. Length tracking: Store length in bits or words?
  4. Bounds checking: Check every operation or trust the caller?
  5. Padding bits: What value should unused bits in the last word have?

5.6 Thinking Exercise

Manually calculate these bit operations:

Given a 64-bit word and wanting to access bit 42:

  • Which word index? 42 / 64 = 0
  • Which bit within word? 42 % 64 = 42
  • Mask to test bit 42: 1UL << 42 = 0x0000040000000000

Now write the formulas for:

  1. Set bit N: word |= (1UL << N)
  2. Clear bit N: word &= ~(1UL << N)
  3. Test bit N: (word >> N) & 1 or (word & (1UL << N)) != 0
  4. Toggle bit N: word ^= (1UL << N)

Range mask calculation:

Create a mask for bits 5-10 (inclusive) in a 64-bit word:

Bits to set: 5, 6, 7, 8, 9, 10
Binary:      00000000...00000011111100000
Hex:         0x00000000000007E0

Method 1: ((1UL << 11) - 1) ^ ((1UL << 5) - 1)
Method 2: ((1UL << 6) - 1) << 5

5.7 Hints in Layers

Hint 1 - Starting Point (Conceptual Direction):

Choose your word type carefully. Using unsigned long is portable but its size varies. For consistency, consider uint64_t from <stdint.h>.

Define these macros early:

#define BPW (8 * sizeof(unsigned long))
#define nwords(len) (((len) + BPW - 1) / BPW)  // Ceiling division
#define WORD(n) ((n) / BPW)
#define BIT(n) ((n) % BPW)

Hint 2 - Next Level (More Specific Guidance):

For single-bit operations, the pattern is always:

  1. Calculate word index: WORD(n)
  2. Calculate bit position: BIT(n)
  3. Create mask: 1UL << BIT(n)
  4. Apply operation: |= (set), &= ~ (clear), ^= (toggle), & (test)
// All single-bit ops follow this pattern:
unsigned long *word = &set->words[WORD(n)];
unsigned long mask = 1UL << BIT(n);

*word |= mask;    // set
*word &= ~mask;   // clear
*word ^= mask;    // toggle
return (*word & mask) != 0;  // test

Hint 3 - Technical Details (Approach/Pseudocode):

Range operations are trickier because they may span multiple words:

void Bit_set(T set, int lo, int hi) {
    // Handle three cases:
    // 1. lo and hi in same word
    // 2. lo and hi in adjacent words
    // 3. lo and hi span multiple words

    int lo_word = WORD(lo);
    int hi_word = WORD(hi);

    if (lo_word == hi_word) {
        // All bits in one word
        // Create mask for bits [BIT(lo), BIT(hi)]
        unsigned long mask = /* ... */;
        set->words[lo_word] |= mask;
    } else {
        // Set high bits of lo_word (from BIT(lo) to end)
        set->words[lo_word] |= ~0UL << BIT(lo);

        // Set all bits in middle words
        for (int i = lo_word + 1; i < hi_word; i++)
            set->words[i] = ~0UL;

        // Set low bits of hi_word (from 0 to BIT(hi))
        set->words[hi_word] |= ~(~0UL << (BIT(hi) + 1));
    }
}

Hint 4 - Tools/Debugging (Verification Methods):

For population count, use hardware instruction when available:

int Bit_count(T set) {
    int count = 0;
    for (int i = 0; i < set->nwords; i++) {
#ifdef __GNUC__
        count += __builtin_popcountl(set->words[i]);
#else
        // Fallback: Brian Kernighan's algorithm
        unsigned long w = set->words[i];
        while (w) {
            count++;
            w &= w - 1;
        }
#endif
    }
    return count;
}

For finding first set bit:

int first_set_bit(T set) {
    for (int i = 0; i < set->nwords; i++) {
        if (set->words[i]) {
#ifdef __GNUC__
            return i * BPW + __builtin_ffsl(set->words[i]) - 1;
#else
            // Manual search
#endif
        }
    }
    return -1;  // No bits set
}

5.8 The Interview Questions They’ll Ask

  1. “Implement a Bloom filter. What operations does your bit vector need?”

    Expected Strong Answer: A Bloom filter needs: (1) Create bit vector of size m, (2) Set bit at position h(x) for each hash function h, (3) Test bit at position h(x) for each hash function. The key operations are Bit_put to set bits and Bit_get to test. For optimal performance, m should be power of 2 so hash % m is fast. I’d use k independent hash functions, typically k = (m/n) * ln(2) for n expected elements.

  2. “How would you find the first set bit in a bit vector efficiently?”

    Expected Strong Answer: Modern CPUs have a “find first set” instruction. In GCC, __builtin_ffsl(x) returns the position of the lowest set bit (1-indexed, 0 if none). For a bit vector, scan words until finding non-zero, then use ffs on that word. This is O(n/w) worst case but O(1) if the first word has a set bit. Intel calls this BSF (Bit Scan Forward).

  3. “Count set bits in a 64-bit integer without a loop.”

    Expected Strong Answer: Use hardware popcnt instruction via __builtin_popcountl(). Without hardware support, there’s a parallel counting technique using bit manipulation: split into pairs, sum pairs to nibbles, sum nibbles to bytes, sum bytes. The classic SWAR (SIMD Within A Register) approach. Or use a 256-entry lookup table for each byte.

  4. “Implement set intersection on two bit vectors. What’s the complexity?”

    Expected Strong Answer: Intersection is just bitwise AND on each word pair: result[i] = a[i] & b[i]. Complexity is O(n/w) where n is bits and w is word size (32 or 64). For 1 million bits on 64-bit system, that’s about 15,625 AND operations. With SIMD (AVX-512), we can process 512 bits per instruction, making it even faster.

  5. “Design a bitmap index for a database column with 1 billion rows.”

    Expected Strong Answer: For a column with cardinality k (k distinct values), create k bit vectors of 1 billion bits each (125 MB per value). For query WHERE color='red', return the ‘red’ bitmap. For WHERE color='red' AND size='large', return red_bitmap & large_bitmap. The challenge is storage: 1 billion bits = 125 MB, but for sparse data, use compression (RLE, Roaring Bitmaps). For very high cardinality, bitmap indices become impractical.

5.9 Books That Will Help

Topic Book Chapter
Bit vector implementation “C Interfaces and Implementations” by Hanson Ch. 13
Bit manipulation tricks “Hacker’s Delight” by Warren Throughout (essential!)
Bloom filters “Algorithms” by Sedgewick & Wayne Ch. 3.5
SIMD bit operations “The Art of Computer Programming” Vol. 4A by Knuth Bitwise tricks
Bitmap indices “Database Internals” by Petrov Index structures

5.10 Implementation Phases

Phase 1: Core Structure (Day 1)

  • Define struct Bit_T
  • Implement Bit_new and Bit_free
  • Implement Bit_length
  • Define BPW, WORD, BIT, MASK macros

Phase 2: Single-Bit Operations (Day 2)

  • Implement Bit_get
  • Implement Bit_put
  • Test with various bit positions including boundary cases

Phase 3: Range Operations (Day 3)

  • Implement Bit_set for ranges
  • Implement Bit_clear for ranges
  • Implement Bit_not for ranges
  • Handle same-word and multi-word cases

Phase 4: Set Operations (Day 4)

  • Implement Bit_union
  • Implement Bit_inter
  • Implement Bit_minus
  • Implement Bit_diff (symmetric difference)

Phase 5: Utility Functions (Day 5)

  • Implement Bit_count (with popcount optimization)
  • Implement Bit_eq, Bit_subset, Bit_lt, Bit_leq
  • Implement Bit_map for iteration

Phase 6: Testing & Applications (Day 6)

  • Comprehensive test suite
  • Bloom filter demonstration
  • Performance benchmarking

5.11 Key Implementation Decisions

  1. Word Type: unsigned long for portability or uint64_t for consistency?

  2. Bit Ordering: LSB-first (bit 0 = rightmost) is standard and matches hardware instructions

  3. Padding Bits: Keep unused bits in last word as 0 to simplify comparison operations

  4. Bounds Checking: Assert on invalid indices (Hanson’s approach) vs. return error code

  5. Equal Length Requirement: Set operations require equal-length vectors (simpler, matches mathematical definition)

6. Testing Strategy

Unit Tests

void test_create_destroy(void) {
    Bit_T b = Bit_new(1000);
    assert(b != NULL);
    assert(Bit_length(b) == 1000);
    assert(Bit_count(b) == 0);  // All bits should be clear
    Bit_free(&b);
    assert(b == NULL);
    printf("test_create_destroy: PASSED\n");
}

void test_single_bit_ops(void) {
    Bit_T b = Bit_new(100);

    // Test set and get
    assert(Bit_get(b, 42) == 0);
    Bit_put(b, 42, 1);
    assert(Bit_get(b, 42) == 1);

    // Test clear
    Bit_put(b, 42, 0);
    assert(Bit_get(b, 42) == 0);

    // Test boundaries
    Bit_put(b, 0, 1);
    Bit_put(b, 99, 1);
    assert(Bit_get(b, 0) == 1);
    assert(Bit_get(b, 99) == 1);

    Bit_free(&b);
    printf("test_single_bit_ops: PASSED\n");
}

void test_range_ops(void) {
    Bit_T b = Bit_new(100);

    // Set range [10, 20]
    Bit_set(b, 10, 20);
    for (int i = 0; i < 100; i++) {
        if (i >= 10 && i <= 20)
            assert(Bit_get(b, i) == 1);
        else
            assert(Bit_get(b, i) == 0);
    }

    // Clear range [14, 16]
    Bit_clear(b, 14, 16);
    assert(Bit_get(b, 13) == 1);
    assert(Bit_get(b, 14) == 0);
    assert(Bit_get(b, 16) == 0);
    assert(Bit_get(b, 17) == 1);

    Bit_free(&b);
    printf("test_range_ops: PASSED\n");
}

void test_set_operations(void) {
    Bit_T a = Bit_new(10);
    Bit_T b = Bit_new(10);

    // A = {0, 1, 2, 3, 4}
    Bit_set(a, 0, 4);

    // B = {3, 4, 5, 6, 7}
    Bit_set(b, 3, 7);

    // Test union
    Bit_T u = Bit_new(10);
    // Copy a to u, then union with b
    // ... (implementation specific)

    Bit_free(&a);
    Bit_free(&b);
    printf("test_set_operations: PASSED\n");
}

Edge Cases

void test_edge_cases(void) {
    // Single bit vector
    Bit_T b1 = Bit_new(1);
    Bit_put(b1, 0, 1);
    assert(Bit_get(b1, 0) == 1);
    assert(Bit_count(b1) == 1);
    Bit_free(&b1);

    // Exactly one word
    Bit_T b64 = Bit_new(64);
    Bit_set(b64, 0, 63);
    assert(Bit_count(b64) == 64);
    Bit_free(&b64);

    // Word boundary
    Bit_T bw = Bit_new(128);
    Bit_set(bw, 62, 66);  // Crosses word boundary
    assert(Bit_count(bw) == 5);
    Bit_free(&bw);

    printf("test_edge_cases: PASSED\n");
}

Bloom Filter Test

void test_bloom_filter(void) {
    // Simple Bloom filter with 10000 bits and 3 hash functions
    int m = 10000;
    int k = 3;
    Bit_T bloom = Bit_new(m);

    // Add some strings
    const char *words[] = {"apple", "banana", "cherry", "date", "elderberry"};
    int nwords = 5;

    for (int i = 0; i < nwords; i++) {
        // Simple hash functions (use better ones in production!)
        unsigned h1 = hash1(words[i]) % m;
        unsigned h2 = hash2(words[i]) % m;
        unsigned h3 = hash3(words[i]) % m;

        Bit_put(bloom, h1, 1);
        Bit_put(bloom, h2, 1);
        Bit_put(bloom, h3, 1);
    }

    // Test membership
    for (int i = 0; i < nwords; i++) {
        unsigned h1 = hash1(words[i]) % m;
        unsigned h2 = hash2(words[i]) % m;
        unsigned h3 = hash3(words[i]) % m;

        int present = Bit_get(bloom, h1) &&
                      Bit_get(bloom, h2) &&
                      Bit_get(bloom, h3);
        assert(present);  // Must find all added words
    }

    // Test false positive rate with random strings
    int false_positives = 0;
    for (int i = 0; i < 1000; i++) {
        char random[10];
        generate_random_string(random);

        unsigned h1 = hash1(random) % m;
        unsigned h2 = hash2(random) % m;
        unsigned h3 = hash3(random) % m;

        if (Bit_get(bloom, h1) && Bit_get(bloom, h2) && Bit_get(bloom, h3))
            false_positives++;
    }

    printf("False positive rate: %.2f%%\n", false_positives / 10.0);
    Bit_free(&bloom);
}

7. Common Pitfalls & Debugging

Problem 1: “Operations affect wrong bits”

  • Symptom: Setting bit 63 affects bit 0, or vice versa
  • Why: Using 1 << n instead of 1UL << n (integer overflow on 32-bit)
  • Fix: Always use 1UL << n for 64-bit shifts
  • Test: Set bit 63, verify bit 0 unchanged

Problem 2: “Popcount returns wrong value”

  • Symptom: Count is higher than expected
  • Why: Counting padding bits in last word
  • Fix: Mask out unused bits before counting last word
  • Test: Create 65-bit vector, set all bits, verify count is 65

Problem 3: “Range operations miss bits at word boundaries”

  • Symptom: Bit_set(b, 62, 66) doesn’t set bit 64
  • Why: Off-by-one in multi-word loop
  • Fix: Carefully handle lo_word, hi_word, and middle words separately
  • Test: Test range operations that cross every word boundary

Problem 4: “Set comparison says unequal when they should be equal”

  • Symptom: Two vectors with same bits set are not equal
  • Why: Padding bits differ between vectors
  • Fix: Ensure padding bits are always 0, or mask when comparing
  • Test: Create two vectors, set same bits, verify equality

Problem 5: “Crash on bit index equal to length”

  • Symptom: Bit_get(b, Bit_length(b)) crashes or corrupts
  • Why: Valid indices are 0 to length-1
  • Fix: Assert n < length, not n <= length
  • Test: Verify assertion fires for out-of-bounds access

8. Extensions & Challenges

8.1 Find First Set / Clear

Implement Bit_ffs(T set) to find the index of the first set bit, and Bit_ffc(T set) for first clear bit. Use hardware instructions when available.

8.2 Sparse Bit Vectors

For mostly-empty vectors, implement a sparse representation that only stores set bits (like Roaring Bitmaps).

8.3 SIMD Optimization

Use AVX2/AVX-512 to process multiple words in parallel:

#include <immintrin.h>
// Process 256 bits at once with AVX2
__m256i a = _mm256_loadu_si256((__m256i*)set->words);
__m256i b = _mm256_loadu_si256((__m256i*)other->words);
__m256i result = _mm256_and_si256(a, b);  // Intersection

8.4 Rank and Select

Implement:

  • Bit_rank(T set, int n): Count set bits in [0, n]
  • Bit_select(T set, int k): Find position of k-th set bit

These are fundamental for succinct data structures.

8.5 Serialization

Implement Bit_save(T set, FILE *f) and Bit_load(FILE *f) for persistence.

9. Real-World Connections

Database Bitmap Indices

PostgreSQL Bitmap Scans:

-- PostgreSQL uses bitmap scans to combine multiple index conditions
SELECT * FROM orders
WHERE status = 'shipped' AND region = 'west';

-- Internally:
-- 1. Scan status index for 'shipped' → bitmap A
-- 2. Scan region index for 'west' → bitmap B
-- 3. Return bitmap A AND bitmap B
-- 4. Fetch rows matching the combined bitmap

Bloom Filters in Practice

Google Bigtable:

Bloom filters reduce disk reads by ~100x for non-existent keys.
Each SSTable has an associated Bloom filter.
Before reading from disk, check the Bloom filter.
If filter says "not present", skip the disk read.

Operating System Memory Management

Linux Page Frame Allocator:

// Simplified from linux/mm/page_alloc.c
struct zone {
    unsigned long *pageblock_flags;  // Bit vector!
    // One bit per pageblock (typically 2MB)
    // Tracks whether block is movable, unmovable, etc.
};

Network Packet Classification

IP Access Control Lists:

Rule 1: Allow 192.168.1.0/24 → bitmap of matching packets
Rule 2: Deny 192.168.1.100 → bitmap of matching packets
Rule 3: Allow port 80 → bitmap of matching packets

Final allow = (Rule1 & ~Rule2) | Rule3

10. Resources

Primary References

  1. C Interfaces and Implementations by David Hanson, Chapter 13
    • Official CII source: https://github.com/drh/cii
  2. Hacker’s Delight by Henry Warren
    • The bible of bit manipulation tricks
    • Essential for understanding popcount, ffs, etc.

Online Resources

  1. Bit Twiddling Hacks: https://graphics.stanford.edu/~seander/bithacks.html
  2. Roaring Bitmaps: https://roaringbitmap.org/
  3. Intel Intrinsics Guide: https://www.intel.com/content/www/us/en/docs/intrinsics-guide/

11. Self-Assessment Checklist

Before considering this project complete, verify:

  • Bit_new creates vector with all bits clear
  • Bit_free deallocates and sets pointer to NULL
  • Bit_length returns correct bit count
  • Bit_count returns correct population count
  • Bit_get works for bits 0, 63, 64, and last bit
  • Bit_put sets and clears bits correctly
  • Bit_set works for ranges within one word
  • Bit_set works for ranges spanning multiple words
  • Bit_clear and Bit_not work similarly
  • [ ] Bit_union computes A B correctly
  • Bit_inter computes A & B correctly
  • Bit_minus computes A & ~B correctly
  • Bit_diff computes A ^ B correctly
  • Bit_eq returns true for equal vectors
  • Bounds checking catches out-of-range indices
  • No memory leaks (verified with Valgrind)
  • Works on both 32-bit and 64-bit systems

12. Submission / Completion Criteria

Your Bit module implementation is complete when:

  1. All tests pass: Both your own tests and any provided test suite
  2. Memory-safe: No leaks, no overflows, no undefined behavior
  3. Documented: Header file has clear comments explaining each function
  4. Follows CII conventions: Opaque type, Module_operation naming, checked runtime errors
  5. Demonstrates applications: Bloom filter or other practical use case works

Deliverables:

  • bit.h - Interface with documentation
  • bit.c - Implementation with optimizations
  • bit_test.c - Comprehensive test suite
  • bloom_test.c - Bloom filter demonstration
  • Makefile - Build configuration
  • Brief writeup explaining: (1) word type choice, (2) popcount implementation, (3) how you handle padding bits