Data Structures & AlgorithmsWhen to Use Bit Manipulation

When to Use Bit Manipulation

LevelAdvanced

Duration60 mins

TopicWhen to Use Bit Manipulation

2 / 4

Space Optimization with Bits

The Memory Efficiency Imperative

In the age of cloud computing where memory is billed by the gigabyte-hour, space efficiency translates directly to cost. In embedded systems where RAM is measured in kilobytes, space efficiency determines feasibility. In high-performance computing where cache misses destroy throughput, space efficiency defines speed.

Bit manipulation offers the most aggressive space optimization possible: representing data at the fundamental unit of information—the single bit. While modern languages and frameworks often obscure memory concerns behind layers of abstraction, understanding bit-level space optimization remains essential for engineers working on:

Database systems — Bitmap indices, null indicators, compression
Operating systems — Memory management, permission bits, status flags
Networking — Packet headers, protocol flags, routing tables
Machine learning — Quantized models, sparse representations
Competitive programming — Meeting strict memory limits

This page develops deep expertise in using bits to minimize memory footprint, covering bit arrays, bit packing techniques, and real-world case studies of memory optimization in production systems.

What You Will Learn

By the end of this page, you will understand how to implement and use bit arrays for boolean storage, master bit packing techniques for multi-field data, recognize space-time tradeoffs, and apply these techniques to real-world memory optimization challenges.

The Mathematics of Space Savings

Before diving into implementation, let's quantify exactly what bit-level optimization buys us. Understanding these numbers helps you make informed decisions about when bit manipulation is worth the added complexity.

Boolean Storage: The Fundamental Win

A boolean value requires only 1 bit of information: true or false. However, programming languages typically use much more:

C/C++ bool: Usually 1 byte (8 bits) — 8× waste
Java boolean: 1 byte in arrays, often 4 bytes on stack — 8-32× waste
JavaScript boolean: Part of value representation, ~8 bytes typical — 64× waste
Python bool: Object overhead, typically 28 bytes on 64-bit — 224× waste

When storing large arrays of booleans, bit packing eliminates this waste completely.

Memory Usage: Boolean Array vs Bit Array
Number of Flags	Native Boolean Array	Bit Array	Space Saved
64	64 - 512 bytes	8 bytes	87.5% - 98.4%
1,000	1 - 8 KB	125 bytes	87.5% - 98.4%
1,000,000	1 - 8 MB	125 KB	87.5% - 98.4%
1,000,000,000	1 - 8 GB	125 MB	87.5% - 98.4%

The Cache Effect Multiplier

Space savings compound when considering cache behavior. Modern CPUs access memory in cache lines (typically 64 bytes). Smaller data structures mean:

More data per cache line — A 64-byte cache line holds 512 bits versus 64 booleans
Fewer cache misses — 8× less data means 8× fewer main memory accesses
Better prefetching — Sequential bit access has predictable patterns

Real impact: Operations on bit arrays can be 10-100× faster than boolean arrays for cache-sensitive workloads, even though individual bit operations are slightly more complex than byte operations.

When Space Becomes Speed

The counterintuitive insight: using bits can be faster despite the bit extraction overhead. When data fits in cache versus spilling to RAM, you see 10-100× speedups. When working set fits in L1 cache versus L2, you see 3-10× speedups. Space optimization often delivers performance benefits.

Implementing Bit Arrays

A bit array (also called bitset or bit vector) stores a sequence of bits efficiently packed into integer words. This is the foundational data structure for bit-based space optimization.

Core Operations

A bit array needs to support:

Get bit at index i — Is bit i set?
Set bit at index i — Turn bit i on
Clear bit at index i — Turn bit i off
Toggle bit at index i — Flip bit i

Each operation involves:

Computing which word contains the bit: wordIndex = i / wordSize
Computing position within the word: bitPos = i % wordSize
Applying the appropriate bitwise operation

BitArray
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
/**
 * Efficient bit array implementation using 32-bit integers.
 * Each integer stores 32 boolean values.
 */
class BitArray {
    private data: Uint32Array;
    private readonly size: number;
    
    // Constants for 32-bit words
    private static readonly WORD_SIZE = 32;
    private static readonly WORD_MASK = 31; // For i % 32 = i & 31
    private static readonly WORD_SHIFT = 5;  // For i / 32 = i >> 5
    
    constructor(size: number) {
        this.size = size;
        // Calculate number of words needed, rounding up
        const wordCount = (size + BitArray.WORD_SIZE - 1) >> BitArray.WORD_SHIFT;
        this.data = new Uint32Array(wordCount);
    }
    
    /**
     * Get the bit at the specified index.
     * Time: O(1)
     */
    get(index: number): boolean {
        if (index < 0 || index >= this.size) {
            throw new RangeError(`Index ${index} out of bounds [0, ${this.size})`);
        }
        
        const wordIndex = index >> BitArray.WORD_SHIFT;
        const bitPos = index & BitArray.WORD_MASK;
        
        return (this.data[wordIndex] & (1 << bitPos)) !== 0;
    }
    
    /**
     * Set the bit at the specified index to 1.
     * Time: O(1)
     */
    set(index: number): void {
        if (index < 0 || index >= this.size) {
            throw new RangeError(`Index ${index} out of bounds [0, ${this.size})`);
        }
        
        const wordIndex = index >> BitArray.WORD_SHIFT;
        const bitPos = index & BitArray.WORD_MASK;
        
        this.data[wordIndex] |= (1 << bitPos);
    }
    
    /**
     * Clear the bit at the specified index (set to 0).
     * Time: O(1)
     */
    clear(index: number): void {
        if (index < 0 || index >= this.size) {
            throw new RangeError(`Index ${index} out of bounds [0, ${this.size})`);
        }
        
        const wordIndex = index >> BitArray.WORD_SHIFT;
        const bitPos = index & BitArray.WORD_MASK;
        
        this.data[wordIndex] &= ~(1 << bitPos);
    }
    
    /**
     * Toggle the bit at the specified index.
     * Time: O(1)
     */
    toggle(index: number): void {
        if (index < 0 || index >= this.size) {
            throw new RangeError(`Index ${index} out of bounds [0, ${this.size})`);
        }
        
        const wordIndex = index >> BitArray.WORD_SHIFT;
        const bitPos = index & BitArray.WORD_MASK;
        
        this.data[wordIndex] ^= (1 << bitPos);
    }
    
    /**
     * Count the number of set bits (popcount).
     * Time: O(n/32)
     */
    popcount(): number {
        let count = 0;
        for (const word of this.data) {
            count += this.popcountWord(word);
        }
        return count;
    }
    
    /**
     * Count set bits in a single word using Brian Kernighan's algorithm.
     */
    private popcountWord(n: number): number {
        let count = 0;
        while (n) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
    
    /**
     * Set all bits to 0.
     * Time: O(n/32)
     */
    clearAll(): void {
        this.data.fill(0);
    }
    
    /**
     * Set all bits to 1.
     * Time: O(n/32)
     */
    setAll(): void {
        this.data.fill(0xFFFFFFFF);
        
        // Clear unused bits in the last word
        const remainder = this.size & BitArray.WORD_MASK;
        if (remainder !== 0) {
            const lastWordIndex = this.data.length - 1;
            this.data[lastWordIndex] &= (1 << remainder) - 1;
        }
    }
    
    /**
     * Perform bitwise AND with another BitArray.
     * Time: O(n/32)
     */
    and(other: BitArray): void {
        const len = Math.min(this.data.length, other.data.length);
        for (let i = 0; i < len; i++) {
            this.data[i] &= other.data[i];
        }
        // Clear remaining words if this is longer
        for (let i = len; i < this.data.length; i++) {
            this.data[i] = 0;
        }
    }
    
    /**
     * Perform bitwise OR with another BitArray.
     * Time: O(n/32)
     */
    or(other: BitArray): void {
        const len = Math.min(this.data.length, other.data.length);
        for (let i = 0; i < len; i++) {
            this.data[i] |= other.data[i];
        }
    }
    
    /**
     * Perform bitwise XOR with another BitArray.
     * Time: O(n/32)
     */
    xor(other: BitArray): void {
        const len = Math.min(this.data.length, other.data.length);
        for (let i = 0; i < len; i++) {
            this.data[i] ^= other.data[i];
        }
    }
    
    /**
     * Get the memory usage in bytes.
     */
    memoryUsage(): number {
        return this.data.byteLength;
    }
    
    /**
     * Get array-like representation of all set bit indices.
     */
    getSetBits(): number[] {
        const result: number[] = [];
        
        for (let wordIndex = 0; wordIndex < this.data.length; wordIndex++) {
            let word = this.data[wordIndex];
            let baseIndex = wordIndex << BitArray.WORD_SHIFT;
            
            while (word) {
                // Find lowest set bit position
                const lowest = word & (-word);
                const bitPos = Math.log2(lowest) | 0;
                result.push(baseIndex + bitPos);
                
                // Clear lowest set bit
                word &= (word - 1);
            }
        }
        
        return result;
    }
}
 
// Usage example
const bits = new BitArray(1000000); // 1 million bits
console.log(`Memory usage: ${bits.memoryUsage()} bytes`); // ~125KB
 
bits.set(12345);
bits.set(67890);
console.log(bits.get(12345)); // true
console.log(bits.get(12346)); // false
console.log(bits.popcount()); // 2

Built-in Alternatives

Many languages provide built-in bit array support: C++: std::bitset (fixed size) and std::vector<bool> (dynamic). Java: BitSet. Python: bitarray library or native int (arbitrary precision). JavaScript/TypeScript: Typed arrays (Uint32Array) as shown above. Use built-ins when available, but understand the underlying mechanics.

Bit Packing Techniques

Bit packing extends beyond boolean arrays to efficiently store multiple small values in a single integer. This technique is fundamental in compression, serialization, and memory-constrained systems.

Packing Multiple Fields

When storing multiple small values, each requiring fewer bits than standard integer types provide, bit packing can dramatically reduce memory usage.

Example scenario: Store 1 million points where:

x-coordinate: 0-999 (needs 10 bits)
y-coordinate: 0-999 (needs 10 bits)
color: 0-7 (needs 3 bits)
flags: 4 boolean values (needs 4 bits)

Total: 27 bits, fits in a 32-bit integer.

Memory comparison:

Naive struct (with padding): ~16-24 bytes per point = 16-24 MB
Bit-packed: 4 bytes per point = 4 MB
Savings: 75-83%

bit_packing_example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 * Bit-packed point structure.
 * Layout (32 bits total):
 * - Bits 0-9:   x-coordinate (0-1023)
 * - Bits 10-19: y-coordinate (0-1023)
 * - Bits 20-22: color (0-7)
 * - Bits 23-26: flags (4 booleans)
 * - Bits 27-31: unused
 */
 
// Bit field definitions
const X_BITS = 10;
const X_MASK = (1 << X_BITS) - 1;        // 0x3FF
const X_SHIFT = 0;
 
const Y_BITS = 10;
const Y_MASK = (1 << Y_BITS) - 1;        // 0x3FF
const Y_SHIFT = X_SHIFT + X_BITS;        // 10
 
const COLOR_BITS = 3;
const COLOR_MASK = (1 << COLOR_BITS) - 1; // 0x7
const COLOR_SHIFT = Y_SHIFT + Y_BITS;     // 20
 
const FLAGS_BITS = 4;
const FLAGS_MASK = (1 << FLAGS_BITS) - 1; // 0xF
const FLAGS_SHIFT = COLOR_SHIFT + COLOR_BITS; // 23
 
// Pack individual values into a single integer
function packPoint(x: number, y: number, color: number, flags: number): number {
    return ((x & X_MASK) << X_SHIFT) |
           ((y & Y_MASK) << Y_SHIFT) |
           ((color & COLOR_MASK) << COLOR_SHIFT) |
           ((flags & FLAGS_MASK) << FLAGS_SHIFT);
}
 
// Unpack x-coordinate
function getX(packed: number): number {
    return (packed >> X_SHIFT) & X_MASK;
}
 
// Unpack y-coordinate
function getY(packed: number): number {
    return (packed >> Y_SHIFT) & Y_MASK;
}
 
// Unpack color
function getColor(packed: number): number {
    return (packed >> COLOR_SHIFT) & COLOR_MASK;
}
 
// Unpack flags
function getFlags(packed: number): number {
    return (packed >> FLAGS_SHIFT) & FLAGS_MASK;
}
 
// Check specific flag
function hasFlag(packed: number, flagIndex: number): boolean {
    const flagBit = 1 << (FLAGS_SHIFT + flagIndex);
    return (packed & flagBit) !== 0;
}
 
// Set specific flag
function setFlag(packed: number, flagIndex: number): number {
    return packed | (1 << (FLAGS_SHIFT + flagIndex));
}
 
// Clear specific flag
function clearFlag(packed: number, flagIndex: number): number {
    return packed & ~(1 << (FLAGS_SHIFT + flagIndex));
}
 
// Modify a field while preserving others
function setX(packed: number, newX: number): number {
    const cleared = packed & ~(X_MASK << X_SHIFT);
    return cleared | ((newX & X_MASK) << X_SHIFT);
}
 
// Usage
const point = packPoint(512, 768, 3, 0b1010);
console.log(`X: ${getX(point)}`);        // 512
console.log(`Y: ${getY(point)}`);        // 768
console.log(`Color: ${getColor(point)}`); // 3
console.log(`Flags: ${getFlags(point).toString(2)}`); // 1010
console.log(`Has flag 1: ${hasFlag(point, 1)}`); // true
console.log(`Has flag 0: ${hasFlag(point, 0)}`); // false
 
// Store million points in ~4MB instead of 16-24MB
const points = new Uint32Array(1000000);
points[0] = packPoint(100, 200, 5, 0b0011);

Variable-Length Encoding

For even greater compression when values have non-uniform distributions, variable-length encoding stores common values in fewer bits. This is the principle behind:

Varint encoding (Protocol Buffers, LEB128) — small integers use fewer bytes
Huffman coding — frequent symbols get shorter codes
Delta encoding — store differences instead of absolute values

These techniques operate at the bit level to achieve optimal compression.

varint_encoding
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Simple varint encoding (similar to Protocol Buffers).
 * Each byte uses 7 bits for data, 1 bit as continuation flag.
 * 
 * Small numbers (0-127): 1 byte
 * Medium numbers (128-16383): 2 bytes
 * And so on...
 */
 
function encodeVarint(value: number): number[] {
    const bytes: number[] = [];
    
    while (value > 127) {
        // Take low 7 bits, set high bit to indicate more bytes follow
        bytes.push((value & 0x7F) | 0x80);
        value >>>= 7;
    }
    
    // Last byte: high bit is 0
    bytes.push(value & 0x7F);
    
    return bytes;
}
 
function decodeVarint(bytes: number[]): number {
    let value = 0;
    let shift = 0;
    
    for (const byte of bytes) {
        // Extract 7 data bits
        value |= (byte & 0x7F) << shift;
        shift += 7;
        
        // Check if this is the last byte
        if ((byte & 0x80) === 0) {
            break;
        }
    }
    
    return value;
}
 
// Examples showing space efficiency for small values
console.log(encodeVarint(1));      // [1]       - 1 byte
console.log(encodeVarint(127));    // [127]     - 1 byte
console.log(encodeVarint(128));    // [128, 1]  - 2 bytes
console.log(encodeVarint(16383));  // [255, 127] - 2 bytes
console.log(encodeVarint(16384));  // [128, 128, 1] - 3 bytes
 
// Compared to fixed 4-byte encoding, saves 3 bytes per small number
// For datasets with many small values, this compounds significantly

Real-World Case Studies

Bit-based space optimization isn't academic—it's deployed in production systems serving billions of users. Understanding these real-world applications illustrates when and how to apply these techniques.

Case Study 1: Bloom Filters in Databases

The problem: When querying a database, checking if a key exists requires disk access, which is slow.

The solution: Bloom filters use a bit array to probabilistically answer "definitely not present" or "possibly present."

How it works:

A bit array of size m (typically millions of bits)
k hash functions map keys to bit positions
To add: set all k bit positions for the key
To check: if all k positions are set, "possibly present"; if any is 0, "definitely not present"

Space efficiency:

10 bits per element gives ~1% false positive rate
For 1 million entries: only 1.25 MB
Eliminates disk access for most negative lookups

bloom_filter
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Simplified Bloom Filter implementation.
 * Production versions would use better hash functions.
 */
class BloomFilter {
    private bits: BitArray;
    private readonly size: number;
    private readonly hashCount: number;
    
    constructor(expectedElements: number, falsePositiveRate: number = 0.01) {
        // Calculate optimal size: m = -n * ln(p) / (ln(2)^2)
        this.size = Math.ceil(
            -expectedElements * Math.log(falsePositiveRate) / (Math.log(2) ** 2)
        );
        
        // Calculate optimal hash count: k = (m/n) * ln(2)
        this.hashCount = Math.round((this.size / expectedElements) * Math.log(2));
        
        this.bits = new BitArray(this.size);
    }
    
    /**
     * Add an element to the filter.
     */
    add(element: string): void {
        for (let i = 0; i < this.hashCount; i++) {
            const index = this.hash(element, i);
            this.bits.set(index);
        }
    }
    
    /**
     * Check if element might be in the filter.
     * false = definitely not present
     * true = possibly present (may be false positive)
     */
    mightContain(element: string): boolean {
        for (let i = 0; i < this.hashCount; i++) {
            const index = this.hash(element, i);
            if (!this.bits.get(index)) {
                return false; // Definitely not present
            }
        }
        return true; // Possibly present
    }
    
    /**
     * Simple hash function (use better ones in production).
     */
    private hash(element: string, seed: number): number {
        let hash = seed;
        for (let i = 0; i < element.length; i++) {
            hash = ((hash << 5) - hash + element.charCodeAt(i)) | 0;
        }
        return Math.abs(hash) % this.size;
    }
    
    memoryUsage(): number {
        return this.bits.memoryUsage();
    }
}
 
// Usage: Check if URL has been visited (web crawler)
const visited = new BloomFilter(1000000, 0.01); // 1M URLs, 1% FP rate
console.log(`Memory: ${(visited.memoryUsage() / 1024 / 1024).toFixed(2)} MB`);
 
visited.add("https://example.com");
console.log(visited.mightContain("https://example.com")); // true
console.log(visited.mightContain("https://other.com"));    // false (probably)

Case Study 2: Bitmap Indexes in Databases

The problem: Traditional B-tree indexes are inefficient for low-cardinality columns (e.g., gender, status, boolean flags).

The solution: Bitmap indexes use one bit array per distinct value. Each bit indicates whether that row has that value.

How it works:

Column "status" with values {active, pending, closed}
Three bit arrays, each with one bit per row
To find all "active" rows: return positions of set bits in active bitmap
To find "active" AND "premium": bitwise AND of two bitmaps

Space and speed benefits:

Storage: 1 bit per row per value (vs. 4+ bytes in B-tree)
Queries: Parallel bitwise operations process 64 rows at once
Complex filters: AND/OR/NOT become single CPU instructions

Case Study 3: Chess Engine Move Representation

The problem: Chess engines evaluate millions of positions per second. Each board has 64 squares and 12 piece types. Naive representation is too slow.

The solution: Bitboards use twelve 64-bit integers, one per piece type per color. Each bit represents presence on one of 64 squares.

How it works:

One 64-bit integer for white pawns: bits set where white pawns exist
Attack generation: bitwise operations compute all attacks simultaneously
Move validation: intersection and complement operations

Performance benefits:

96 bytes to represent entire board (12 × 8 bytes)
Parallel attack computation: one AND operation checks 64 squares
Modern engines achieve 50-100 million positions per second

Common Thread

These case studies share a pattern: domains with naturally boolean or low-cardinality data where operations can be parallelized across elements. Recognize these characteristics in your own problems to identify bit optimization opportunities.

Understanding Space-Time Tradeoffs

Bit manipulation for space optimization isn't free—it involves tradeoffs that must be carefully evaluated.

The Extraction Cost

Accessing a bit-packed field requires more CPU instructions than accessing a native type:

Native access (1 instruction):

mov eax, [address]    ; Load entire value

Bit-packed access (3-4 instructions):

mov eax, [address]    ; Load container
sar eax, shift        ; Shift to position
and eax, mask         ; Extract bits

When this matters:

Millions of accesses per second to individual fields
Fields accessed independently (not as a group)
No benefit from parallel bit operations

Space-Time Tradeoff Analysis
Factor	Favors Bit Packing	Favors Native Types
Memory per element	Limited memory, large N	Plenty of memory, small N
Access pattern	Sequential scans, batch ops	Random access to individual fields
Cache pressure	Hot data competing for cache	Working set fits in cache anyway
Operation type	Set operations (AND/OR)	Field modifications
Code clarity	Encapsulated in library	Ad-hoc throughout codebase
Portability	Fixed-size types available	Cross-platform with varying sizes

The Cache Compensation

The extraction cost is often compensated by cache benefits. Consider processing 1 million records:

Scenario A: Native structs (16 bytes each)

Total size: 16 MB
Likely spills from L3 cache
Memory bandwidth limited
Cache miss penalty: ~100 cycles per miss

Scenario B: Bit-packed (4 bytes each)

Total size: 4 MB
Fits in L3 cache for most systems
Extraction overhead: ~3-5 cycles
Net gain: avoiding cache misses saves ~95 cycles per access

Rule of thumb: If bit packing keeps your working set in cache when it otherwise wouldn't, bit packing wins despite the extraction overhead.

When to Measure

Don't assume—profile. The cache behavior depends on access patterns, hardware, and concurrent workloads. What wins on one system may lose on another. Use bit packing when analysis strongly suggests benefits, then validate with benchmarks.

Implementation Guidelines

When implementing bit-based space optimizations, following best practices prevents bugs and maintains code quality.

Guideline 1: Document Bit Layouts Explicitly

Bit layouts should be documented in a single location, with diagrams if helpful. Any engineer modifying the code should immediately understand the structure.

documented_layout
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Game Entity State (packed into 32 bits)
 * 
 * Bit Layout:
 * ┌──────────────────────────────────────────────────────────────┐
 * │ 31-28 │ 27-24 │ 23-16 │ 15-8  │ 7-4   │ 3-0   │
 * ├───────┼───────┼───────┼───────┼───────┼───────┤
 * │ Type  │ State │ HP    │ MP    │ Buffs │ Flags │
 * └──────────────────────────────────────────────────────────────┘
 * 
 * Fields:
 * - Type (4 bits):   Entity type enumeration (0-15)
 * - State (4 bits):  Current state (idle, moving, attacking, etc.)
 * - HP (8 bits):     Health points percentage (0-255 maps to 0-100%)
 * - MP (8 bits):     Mana points percentage (0-255 maps to 0-100%)
 * - Buffs (4 bits):  Active buff flags
 * - Flags (4 bits):  Status flags (visible, invulnerable, etc.)
 */
 
const enum EntityField {
    FLAGS_SHIFT = 0,   FLAGS_BITS = 4,
    BUFFS_SHIFT = 4,   BUFFS_BITS = 4,
    MP_SHIFT = 8,      MP_BITS = 8,
    HP_SHIFT = 16,     HP_BITS = 8,
    STATE_SHIFT = 24,  STATE_BITS = 4,
    TYPE_SHIFT = 28,   TYPE_BITS = 4,
}
 
// Always define masks from bits
const FLAGS_MASK = (1 << EntityField.FLAGS_BITS) - 1;
const BUFFS_MASK = (1 << EntityField.BUFFS_BITS) - 1;
const MP_MASK = (1 << EntityField.MP_BITS) - 1;
const HP_MASK = (1 << EntityField.HP_BITS) - 1;
const STATE_MASK = (1 << EntityField.STATE_BITS) - 1;
const TYPE_MASK = (1 << EntityField.TYPE_BITS) - 1;

Guideline 2: Encapsulate Access in Functions

Never perform raw bit manipulation at call sites. Create accessor functions that handle the bit operations, making changes to layout require only one modification.

Guideline 3: Use Type-Safe Wrappers When Possible

Languages like C++ and Rust offer bit field syntax or libraries that provide type safety. Use these when available:

// C++ bit fields (compiler-managed layout)
struct EntityState {
    unsigned type : 4;
    unsigned state : 4;
    unsigned hp : 8;
    unsigned mp : 8;
    unsigned buffs : 4;
    unsigned flags : 4;
};

Note: Standard C/C++ bit fields have implementation-defined layout order and padding. For portable binary formats, use explicit bit manipulation.

Guideline 4: Validate on Pack, Not on Unpack

Validate that values fit in their bit ranges at packing time. This catches errors early and ensures unpacking can assume valid data.

validation_example
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function packValidated(
    hp: number, 
    mp: number, 
    type: number
): number {
    // Validate ranges at pack time
    if (hp < 0 || hp > 255) {
        throw new RangeError(`HP must be 0-255, got ${hp}`);
    }
    if (mp < 0 || mp > 255) {
        throw new RangeError(`MP must be 0-255, got ${mp}`);
    }
    if (type < 0 || type > 15) {
        throw new RangeError(`Type must be 0-15, got ${type}`);
    }
    
    // Pack without masking (values are validated)
    return (hp << HP_SHIFT) | 
           (mp << MP_SHIFT) | 
           (type << TYPE_SHIFT);
}
 
// In performance-critical code, use debug-only validation
function packFast(hp: number, mp: number, type: number): number {
    if (process.env.NODE_ENV === 'development') {
        // Validation only in development
        console.assert(hp >= 0 && hp <= 255);
        console.assert(mp >= 0 && mp <= 255);
        console.assert(type >= 0 && type <= 15);
    }
    
    return (hp << HP_SHIFT) | 
           (mp << MP_SHIFT) | 
           (type << TYPE_SHIFT);
}

Guideline 5: Consider Endianness for Cross-Platform

If bit-packed data will be serialized or shared between systems with different endianness, handle byte order explicitly:

Use consistent byte order (typically network byte order / big-endian)
Document the wire format separately from in-memory format
Use helper functions for serialization/deserialization

Summary

Space optimization through bit manipulation is a powerful technique that produces tangible benefits in production systems. We've covered:

Key Space Optimization Concepts

•Quantified savings — Bit arrays provide 8-64× space reduction over native boolean types, with additional cache benefits
•Bit array implementation — Core operations (get/set/clear/toggle) using word-level storage with O(1) access
•Bit packing techniques — Storing multiple fields in single integers for compound data structures
•Real-world applications — Bloom filters, bitmap indexes, and chess engines demonstrate production use cases
•Space-time tradeoffs — Understanding when extraction overhead is compensated by cache benefits
•Implementation guidelines — Documentation, encapsulation, validation, and portability best practices

What's next:

Having covered space optimization, the next page examines performance considerations—understanding when bit manipulation provides speed benefits, CPU-level optimization techniques, and how to measure and validate performance improvements.

Page Complete

You now have practical skills for implementing space-efficient data structures using bit manipulation. These techniques are directly applicable to production systems where memory efficiency impacts cost, performance, and scalability.

2 / 4

Loading learning content...

Data Structures & AlgorithmsWhen to Use Bit Manipulation

When to Use Bit Manipulation

LevelAdvanced

Duration60 mins

TopicWhen to Use Bit Manipulation

2 / 4

Space Optimization with Bits

The Memory Efficiency Imperative

Database systems — Bitmap indices, null indicators, compression
Operating systems — Memory management, permission bits, status flags
Networking — Packet headers, protocol flags, routing tables
Machine learning — Quantized models, sparse representations
Competitive programming — Meeting strict memory limits

This page develops deep expertise in using bits to minimize memory footprint, covering bit arrays, bit packing techniques, and real-world case studies of memory optimization in production systems.

What You Will Learn

The Mathematics of Space Savings

Boolean Storage: The Fundamental Win

A boolean value requires only 1 bit of information: true or false. However, programming languages typically use much more:

C/C++ bool: Usually 1 byte (8 bits) — 8× waste
Java boolean: 1 byte in arrays, often 4 bytes on stack — 8-32× waste
JavaScript boolean: Part of value representation, ~8 bytes typical — 64× waste
Python bool: Object overhead, typically 28 bytes on 64-bit — 224× waste

When storing large arrays of booleans, bit packing eliminates this waste completely.

Memory Usage: Boolean Array vs Bit Array
Number of Flags	Native Boolean Array	Bit Array	Space Saved
64	64 - 512 bytes	8 bytes	87.5% - 98.4%
1,000	1 - 8 KB	125 bytes	87.5% - 98.4%
1,000,000	1 - 8 MB	125 KB	87.5% - 98.4%
1,000,000,000	1 - 8 GB	125 MB	87.5% - 98.4%

The Cache Effect Multiplier

Space savings compound when considering cache behavior. Modern CPUs access memory in cache lines (typically 64 bytes). Smaller data structures mean:

More data per cache line — A 64-byte cache line holds 512 bits versus 64 booleans
Fewer cache misses — 8× less data means 8× fewer main memory accesses
Better prefetching — Sequential bit access has predictable patterns

When Space Becomes Speed

Implementing Bit Arrays

A bit array (also called bitset or bit vector) stores a sequence of bits efficiently packed into integer words. This is the foundational data structure for bit-based space optimization.

Core Operations

A bit array needs to support:

Get bit at index i — Is bit i set?
Set bit at index i — Turn bit i on
Clear bit at index i — Turn bit i off
Toggle bit at index i — Flip bit i

Each operation involves:

Computing which word contains the bit: wordIndex = i / wordSize
Computing position within the word: bitPos = i % wordSize
Applying the appropriate bitwise operation

BitArray
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
/**
 * Efficient bit array implementation using 32-bit integers.
 * Each integer stores 32 boolean values.
 */
class BitArray {
    private data: Uint32Array;
    private readonly size: number;
    
    // Constants for 32-bit words
    private static readonly WORD_SIZE = 32;
    private static readonly WORD_MASK = 31; // For i % 32 = i & 31
    private static readonly WORD_SHIFT = 5;  // For i / 32 = i >> 5
    
    constructor(size: number) {
        this.size = size;
        // Calculate number of words needed, rounding up
        const wordCount = (size + BitArray.WORD_SIZE - 1) >> BitArray.WORD_SHIFT;
        this.data = new Uint32Array(wordCount);
    }
    
    /**
     * Get the bit at the specified index.
     * Time: O(1)
     */
    get(index: number): boolean {
        if (index < 0 || index >= this.size) {
            throw new RangeError(`Index ${index} out of bounds [0, ${this.size})`);
        }
        
        const wordIndex = index >> BitArray.WORD_SHIFT;
        const bitPos = index & BitArray.WORD_MASK;
        
        return (this.data[wordIndex] & (1 << bitPos)) !== 0;
    }
    
    /**
     * Set the bit at the specified index to 1.
     * Time: O(1)
     */
    set(index: number): void {
        if (index < 0 || index >= this.size) {
            throw new RangeError(`Index ${index} out of bounds [0, ${this.size})`);
        }
        
        const wordIndex = index >> BitArray.WORD_SHIFT;
        const bitPos = index & BitArray.WORD_MASK;
        
        this.data[wordIndex] |= (1 << bitPos);
    }
    
    /**
     * Clear the bit at the specified index (set to 0).
     * Time: O(1)
     */
    clear(index: number): void {
        if (index < 0 || index >= this.size) {
            throw new RangeError(`Index ${index} out of bounds [0, ${this.size})`);
        }
        
        const wordIndex = index >> BitArray.WORD_SHIFT;
        const bitPos = index & BitArray.WORD_MASK;
        
        this.data[wordIndex] &= ~(1 << bitPos);
    }
    
    /**
     * Toggle the bit at the specified index.
     * Time: O(1)
     */
    toggle(index: number): void {
        if (index < 0 || index >= this.size) {
            throw new RangeError(`Index ${index} out of bounds [0, ${this.size})`);
        }
        
        const wordIndex = index >> BitArray.WORD_SHIFT;
        const bitPos = index & BitArray.WORD_MASK;
        
        this.data[wordIndex] ^= (1 << bitPos);
    }
    
    /**
     * Count the number of set bits (popcount).
     * Time: O(n/32)
     */
    popcount(): number {
        let count = 0;
        for (const word of this.data) {
            count += this.popcountWord(word);
        }
        return count;
    }
    
    /**
     * Count set bits in a single word using Brian Kernighan's algorithm.
     */
    private popcountWord(n: number): number {
        let count = 0;
        while (n) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
    
    /**
     * Set all bits to 0.
     * Time: O(n/32)
     */
    clearAll(): void {
        this.data.fill(0);
    }
    
    /**
     * Set all bits to 1.
     * Time: O(n/32)
     */
    setAll(): void {
        this.data.fill(0xFFFFFFFF);
        
        // Clear unused bits in the last word
        const remainder = this.size & BitArray.WORD_MASK;
        if (remainder !== 0) {
            const lastWordIndex = this.data.length - 1;
            this.data[lastWordIndex] &= (1 << remainder) - 1;
        }
    }
    
    /**
     * Perform bitwise AND with another BitArray.
     * Time: O(n/32)
     */
    and(other: BitArray): void {
        const len = Math.min(this.data.length, other.data.length);
        for (let i = 0; i < len; i++) {
            this.data[i] &= other.data[i];
        }
        // Clear remaining words if this is longer
        for (let i = len; i < this.data.length; i++) {
            this.data[i] = 0;
        }
    }
    
    /**
     * Perform bitwise OR with another BitArray.
     * Time: O(n/32)
     */
    or(other: BitArray): void {
        const len = Math.min(this.data.length, other.data.length);
        for (let i = 0; i < len; i++) {
            this.data[i] |= other.data[i];
        }
    }
    
    /**
     * Perform bitwise XOR with another BitArray.
     * Time: O(n/32)
     */
    xor(other: BitArray): void {
        const len = Math.min(this.data.length, other.data.length);
        for (let i = 0; i < len; i++) {
            this.data[i] ^= other.data[i];
        }
    }
    
    /**
     * Get the memory usage in bytes.
     */
    memoryUsage(): number {
        return this.data.byteLength;
    }
    
    /**
     * Get array-like representation of all set bit indices.
     */
    getSetBits(): number[] {
        const result: number[] = [];
        
        for (let wordIndex = 0; wordIndex < this.data.length; wordIndex++) {
            let word = this.data[wordIndex];
            let baseIndex = wordIndex << BitArray.WORD_SHIFT;
            
            while (word) {
                // Find lowest set bit position
                const lowest = word & (-word);
                const bitPos = Math.log2(lowest) | 0;
                result.push(baseIndex + bitPos);
                
                // Clear lowest set bit
                word &= (word - 1);
            }
        }
        
        return result;
    }
}
 
// Usage example
const bits = new BitArray(1000000); // 1 million bits
console.log(`Memory usage: ${bits.memoryUsage()} bytes`); // ~125KB
 
bits.set(12345);
bits.set(67890);
console.log(bits.get(12345)); // true
console.log(bits.get(12346)); // false
console.log(bits.popcount()); // 2

Built-in Alternatives

Bit Packing Techniques

Bit packing extends beyond boolean arrays to efficiently store multiple small values in a single integer. This technique is fundamental in compression, serialization, and memory-constrained systems.

Packing Multiple Fields

When storing multiple small values, each requiring fewer bits than standard integer types provide, bit packing can dramatically reduce memory usage.

Example scenario: Store 1 million points where:

x-coordinate: 0-999 (needs 10 bits)
y-coordinate: 0-999 (needs 10 bits)
color: 0-7 (needs 3 bits)
flags: 4 boolean values (needs 4 bits)

Total: 27 bits, fits in a 32-bit integer.

Memory comparison:

Naive struct (with padding): ~16-24 bytes per point = 16-24 MB
Bit-packed: 4 bytes per point = 4 MB
Savings: 75-83%

bit_packing_example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 * Bit-packed point structure.
 * Layout (32 bits total):
 * - Bits 0-9:   x-coordinate (0-1023)
 * - Bits 10-19: y-coordinate (0-1023)
 * - Bits 20-22: color (0-7)
 * - Bits 23-26: flags (4 booleans)
 * - Bits 27-31: unused
 */
 
// Bit field definitions
const X_BITS = 10;
const X_MASK = (1 << X_BITS) - 1;        // 0x3FF
const X_SHIFT = 0;
 
const Y_BITS = 10;
const Y_MASK = (1 << Y_BITS) - 1;        // 0x3FF
const Y_SHIFT = X_SHIFT + X_BITS;        // 10
 
const COLOR_BITS = 3;
const COLOR_MASK = (1 << COLOR_BITS) - 1; // 0x7
const COLOR_SHIFT = Y_SHIFT + Y_BITS;     // 20
 
const FLAGS_BITS = 4;
const FLAGS_MASK = (1 << FLAGS_BITS) - 1; // 0xF
const FLAGS_SHIFT = COLOR_SHIFT + COLOR_BITS; // 23
 
// Pack individual values into a single integer
function packPoint(x: number, y: number, color: number, flags: number): number {
    return ((x & X_MASK) << X_SHIFT) |
           ((y & Y_MASK) << Y_SHIFT) |
           ((color & COLOR_MASK) << COLOR_SHIFT) |
           ((flags & FLAGS_MASK) << FLAGS_SHIFT);
}
 
// Unpack x-coordinate
function getX(packed: number): number {
    return (packed >> X_SHIFT) & X_MASK;
}
 
// Unpack y-coordinate
function getY(packed: number): number {
    return (packed >> Y_SHIFT) & Y_MASK;
}
 
// Unpack color
function getColor(packed: number): number {
    return (packed >> COLOR_SHIFT) & COLOR_MASK;
}
 
// Unpack flags
function getFlags(packed: number): number {
    return (packed >> FLAGS_SHIFT) & FLAGS_MASK;
}
 
// Check specific flag
function hasFlag(packed: number, flagIndex: number): boolean {
    const flagBit = 1 << (FLAGS_SHIFT + flagIndex);
    return (packed & flagBit) !== 0;
}
 
// Set specific flag
function setFlag(packed: number, flagIndex: number): number {
    return packed | (1 << (FLAGS_SHIFT + flagIndex));
}
 
// Clear specific flag
function clearFlag(packed: number, flagIndex: number): number {
    return packed & ~(1 << (FLAGS_SHIFT + flagIndex));
}
 
// Modify a field while preserving others
function setX(packed: number, newX: number): number {
    const cleared = packed & ~(X_MASK << X_SHIFT);
    return cleared | ((newX & X_MASK) << X_SHIFT);
}
 
// Usage
const point = packPoint(512, 768, 3, 0b1010);
console.log(`X: ${getX(point)}`);        // 512
console.log(`Y: ${getY(point)}`);        // 768
console.log(`Color: ${getColor(point)}`); // 3
console.log(`Flags: ${getFlags(point).toString(2)}`); // 1010
console.log(`Has flag 1: ${hasFlag(point, 1)}`); // true
console.log(`Has flag 0: ${hasFlag(point, 0)}`); // false
 
// Store million points in ~4MB instead of 16-24MB
const points = new Uint32Array(1000000);
points[0] = packPoint(100, 200, 5, 0b0011);

Variable-Length Encoding

For even greater compression when values have non-uniform distributions, variable-length encoding stores common values in fewer bits. This is the principle behind:

Varint encoding (Protocol Buffers, LEB128) — small integers use fewer bytes
Huffman coding — frequent symbols get shorter codes
Delta encoding — store differences instead of absolute values

These techniques operate at the bit level to achieve optimal compression.

varint_encoding
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Simple varint encoding (similar to Protocol Buffers).
 * Each byte uses 7 bits for data, 1 bit as continuation flag.
 * 
 * Small numbers (0-127): 1 byte
 * Medium numbers (128-16383): 2 bytes
 * And so on...
 */
 
function encodeVarint(value: number): number[] {
    const bytes: number[] = [];
    
    while (value > 127) {
        // Take low 7 bits, set high bit to indicate more bytes follow
        bytes.push((value & 0x7F) | 0x80);
        value >>>= 7;
    }
    
    // Last byte: high bit is 0
    bytes.push(value & 0x7F);
    
    return bytes;
}
 
function decodeVarint(bytes: number[]): number {
    let value = 0;
    let shift = 0;
    
    for (const byte of bytes) {
        // Extract 7 data bits
        value |= (byte & 0x7F) << shift;
        shift += 7;
        
        // Check if this is the last byte
        if ((byte & 0x80) === 0) {
            break;
        }
    }
    
    return value;
}
 
// Examples showing space efficiency for small values
console.log(encodeVarint(1));      // [1]       - 1 byte
console.log(encodeVarint(127));    // [127]     - 1 byte
console.log(encodeVarint(128));    // [128, 1]  - 2 bytes
console.log(encodeVarint(16383));  // [255, 127] - 2 bytes
console.log(encodeVarint(16384));  // [128, 128, 1] - 3 bytes
 
// Compared to fixed 4-byte encoding, saves 3 bytes per small number
// For datasets with many small values, this compounds significantly

Real-World Case Studies

Case Study 1: Bloom Filters in Databases

The problem: When querying a database, checking if a key exists requires disk access, which is slow.

The solution: Bloom filters use a bit array to probabilistically answer "definitely not present" or "possibly present."

How it works:

A bit array of size m (typically millions of bits)
k hash functions map keys to bit positions
To add: set all k bit positions for the key
To check: if all k positions are set, "possibly present"; if any is 0, "definitely not present"

Space efficiency:

10 bits per element gives ~1% false positive rate
For 1 million entries: only 1.25 MB
Eliminates disk access for most negative lookups

bloom_filter
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Simplified Bloom Filter implementation.
 * Production versions would use better hash functions.
 */
class BloomFilter {
    private bits: BitArray;
    private readonly size: number;
    private readonly hashCount: number;
    
    constructor(expectedElements: number, falsePositiveRate: number = 0.01) {
        // Calculate optimal size: m = -n * ln(p) / (ln(2)^2)
        this.size = Math.ceil(
            -expectedElements * Math.log(falsePositiveRate) / (Math.log(2) ** 2)
        );
        
        // Calculate optimal hash count: k = (m/n) * ln(2)
        this.hashCount = Math.round((this.size / expectedElements) * Math.log(2));
        
        this.bits = new BitArray(this.size);
    }
    
    /**
     * Add an element to the filter.
     */
    add(element: string): void {
        for (let i = 0; i < this.hashCount; i++) {
            const index = this.hash(element, i);
            this.bits.set(index);
        }
    }
    
    /**
     * Check if element might be in the filter.
     * false = definitely not present
     * true = possibly present (may be false positive)
     */
    mightContain(element: string): boolean {
        for (let i = 0; i < this.hashCount; i++) {
            const index = this.hash(element, i);
            if (!this.bits.get(index)) {
                return false; // Definitely not present
            }
        }
        return true; // Possibly present
    }
    
    /**
     * Simple hash function (use better ones in production).
     */
    private hash(element: string, seed: number): number {
        let hash = seed;
        for (let i = 0; i < element.length; i++) {
            hash = ((hash << 5) - hash + element.charCodeAt(i)) | 0;
        }
        return Math.abs(hash) % this.size;
    }
    
    memoryUsage(): number {
        return this.bits.memoryUsage();
    }
}
 
// Usage: Check if URL has been visited (web crawler)
const visited = new BloomFilter(1000000, 0.01); // 1M URLs, 1% FP rate
console.log(`Memory: ${(visited.memoryUsage() / 1024 / 1024).toFixed(2)} MB`);
 
visited.add("https://example.com");
console.log(visited.mightContain("https://example.com")); // true
console.log(visited.mightContain("https://other.com"));    // false (probably)

Case Study 2: Bitmap Indexes in Databases

The problem: Traditional B-tree indexes are inefficient for low-cardinality columns (e.g., gender, status, boolean flags).

The solution: Bitmap indexes use one bit array per distinct value. Each bit indicates whether that row has that value.

How it works:

Column "status" with values {active, pending, closed}
Three bit arrays, each with one bit per row
To find all "active" rows: return positions of set bits in active bitmap
To find "active" AND "premium": bitwise AND of two bitmaps

Space and speed benefits:

Storage: 1 bit per row per value (vs. 4+ bytes in B-tree)
Queries: Parallel bitwise operations process 64 rows at once
Complex filters: AND/OR/NOT become single CPU instructions

Case Study 3: Chess Engine Move Representation

The problem: Chess engines evaluate millions of positions per second. Each board has 64 squares and 12 piece types. Naive representation is too slow.

The solution: Bitboards use twelve 64-bit integers, one per piece type per color. Each bit represents presence on one of 64 squares.

How it works:

One 64-bit integer for white pawns: bits set where white pawns exist
Attack generation: bitwise operations compute all attacks simultaneously
Move validation: intersection and complement operations

Performance benefits:

96 bytes to represent entire board (12 × 8 bytes)
Parallel attack computation: one AND operation checks 64 squares
Modern engines achieve 50-100 million positions per second

Common Thread

Understanding Space-Time Tradeoffs

Bit manipulation for space optimization isn't free—it involves tradeoffs that must be carefully evaluated.

The Extraction Cost

Accessing a bit-packed field requires more CPU instructions than accessing a native type:

Native access (1 instruction):

mov eax, [address]    ; Load entire value

Bit-packed access (3-4 instructions):

mov eax, [address]    ; Load container
sar eax, shift        ; Shift to position
and eax, mask         ; Extract bits

When this matters:

Millions of accesses per second to individual fields
Fields accessed independently (not as a group)
No benefit from parallel bit operations

Space-Time Tradeoff Analysis
Factor	Favors Bit Packing	Favors Native Types
Memory per element	Limited memory, large N	Plenty of memory, small N
Access pattern	Sequential scans, batch ops	Random access to individual fields
Cache pressure	Hot data competing for cache	Working set fits in cache anyway
Operation type	Set operations (AND/OR)	Field modifications
Code clarity	Encapsulated in library	Ad-hoc throughout codebase
Portability	Fixed-size types available	Cross-platform with varying sizes

The Cache Compensation

The extraction cost is often compensated by cache benefits. Consider processing 1 million records:

Scenario A: Native structs (16 bytes each)

Total size: 16 MB
Likely spills from L3 cache
Memory bandwidth limited
Cache miss penalty: ~100 cycles per miss

Scenario B: Bit-packed (4 bytes each)

Total size: 4 MB
Fits in L3 cache for most systems
Extraction overhead: ~3-5 cycles
Net gain: avoiding cache misses saves ~95 cycles per access

Rule of thumb: If bit packing keeps your working set in cache when it otherwise wouldn't, bit packing wins despite the extraction overhead.

When to Measure

Implementation Guidelines

When implementing bit-based space optimizations, following best practices prevents bugs and maintains code quality.

Guideline 1: Document Bit Layouts Explicitly

Bit layouts should be documented in a single location, with diagrams if helpful. Any engineer modifying the code should immediately understand the structure.

documented_layout
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Game Entity State (packed into 32 bits)
 * 
 * Bit Layout:
 * ┌──────────────────────────────────────────────────────────────┐
 * │ 31-28 │ 27-24 │ 23-16 │ 15-8  │ 7-4   │ 3-0   │
 * ├───────┼───────┼───────┼───────┼───────┼───────┤
 * │ Type  │ State │ HP    │ MP    │ Buffs │ Flags │
 * └──────────────────────────────────────────────────────────────┘
 * 
 * Fields:
 * - Type (4 bits):   Entity type enumeration (0-15)
 * - State (4 bits):  Current state (idle, moving, attacking, etc.)
 * - HP (8 bits):     Health points percentage (0-255 maps to 0-100%)
 * - MP (8 bits):     Mana points percentage (0-255 maps to 0-100%)
 * - Buffs (4 bits):  Active buff flags
 * - Flags (4 bits):  Status flags (visible, invulnerable, etc.)
 */
 
const enum EntityField {
    FLAGS_SHIFT = 0,   FLAGS_BITS = 4,
    BUFFS_SHIFT = 4,   BUFFS_BITS = 4,
    MP_SHIFT = 8,      MP_BITS = 8,
    HP_SHIFT = 16,     HP_BITS = 8,
    STATE_SHIFT = 24,  STATE_BITS = 4,
    TYPE_SHIFT = 28,   TYPE_BITS = 4,
}
 
// Always define masks from bits
const FLAGS_MASK = (1 << EntityField.FLAGS_BITS) - 1;
const BUFFS_MASK = (1 << EntityField.BUFFS_BITS) - 1;
const MP_MASK = (1 << EntityField.MP_BITS) - 1;
const HP_MASK = (1 << EntityField.HP_BITS) - 1;
const STATE_MASK = (1 << EntityField.STATE_BITS) - 1;
const TYPE_MASK = (1 << EntityField.TYPE_BITS) - 1;

Guideline 2: Encapsulate Access in Functions

Never perform raw bit manipulation at call sites. Create accessor functions that handle the bit operations, making changes to layout require only one modification.

Guideline 3: Use Type-Safe Wrappers When Possible

Languages like C++ and Rust offer bit field syntax or libraries that provide type safety. Use these when available:

// C++ bit fields (compiler-managed layout)
struct EntityState {
    unsigned type : 4;
    unsigned state : 4;
    unsigned hp : 8;
    unsigned mp : 8;
    unsigned buffs : 4;
    unsigned flags : 4;
};

Note: Standard C/C++ bit fields have implementation-defined layout order and padding. For portable binary formats, use explicit bit manipulation.

Guideline 4: Validate on Pack, Not on Unpack

Validate that values fit in their bit ranges at packing time. This catches errors early and ensures unpacking can assume valid data.

validation_example
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function packValidated(
    hp: number, 
    mp: number, 
    type: number
): number {
    // Validate ranges at pack time
    if (hp < 0 || hp > 255) {
        throw new RangeError(`HP must be 0-255, got ${hp}`);
    }
    if (mp < 0 || mp > 255) {
        throw new RangeError(`MP must be 0-255, got ${mp}`);
    }
    if (type < 0 || type > 15) {
        throw new RangeError(`Type must be 0-15, got ${type}`);
    }
    
    // Pack without masking (values are validated)
    return (hp << HP_SHIFT) | 
           (mp << MP_SHIFT) | 
           (type << TYPE_SHIFT);
}
 
// In performance-critical code, use debug-only validation
function packFast(hp: number, mp: number, type: number): number {
    if (process.env.NODE_ENV === 'development') {
        // Validation only in development
        console.assert(hp >= 0 && hp <= 255);
        console.assert(mp >= 0 && mp <= 255);
        console.assert(type >= 0 && type <= 15);
    }
    
    return (hp << HP_SHIFT) | 
           (mp << MP_SHIFT) | 
           (type << TYPE_SHIFT);
}

Guideline 5: Consider Endianness for Cross-Platform

If bit-packed data will be serialized or shared between systems with different endianness, handle byte order explicitly:

Use consistent byte order (typically network byte order / big-endian)
Document the wire format separately from in-memory format
Use helper functions for serialization/deserialization

Summary

Space optimization through bit manipulation is a powerful technique that produces tangible benefits in production systems. We've covered:

Key Space Optimization Concepts

•Quantified savings — Bit arrays provide 8-64× space reduction over native boolean types, with additional cache benefits
•Bit array implementation — Core operations (get/set/clear/toggle) using word-level storage with O(1) access
•Bit packing techniques — Storing multiple fields in single integers for compound data structures
•Real-world applications — Bloom filters, bitmap indexes, and chess engines demonstrate production use cases
•Space-time tradeoffs — Understanding when extraction overhead is compensated by cache benefits
•Implementation guidelines — Documentation, encapsulation, validation, and portability best practices

What's next:

Page Complete

2 / 4