Bit-Packed Array

A bit-packed array stores values using a fixed number of bits per element. Instead of allocating a full machine word for each entry, it packs multiple elements into a single word.

You use it when values have small ranges and memory footprint matters.

Problem

Given an array $A$ of length $n$ where each value fits in $b$ bits, support:

read element at index $i$
write element at index $i$

with compact storage.

Structure

Let each element use $b$ bits. The total storage uses:

n \cdot b \text{ bits}

Values are stored in a contiguous bit sequence. For index $i$ :

bit position:

p = i \cdot b

word index:

w = \left\lfloor \frac{p}{W} \right\rfloor

bit offset inside word:

o = p \bmod W

where $W$ is the word size, typically $32$ or $64$ bits.

Algorithm

Read an element:

get(A, i):
    p = i * b
    w = p // W
    o = p % W

    value = (A[w] >> o) & ((1 << b) - 1)

    if o + b > W:
        next = A[w + 1] << (W - o)
        value |= next & ((1 << b) - 1)

    return value

Write an element:

set(A, i, x):
    p = i * b
    w = p // W
    o = p % W

    mask = ((1 << b) - 1) << o
    A[w] = (A[w] & ~mask) | (x << o)

    if o + b > W:
        spill = (x >> (W - o))
        mask2 = (1 << (o + b - W)) - 1
        A[w + 1] = (A[w + 1] & ~mask2) | spill

Example

Let each element use $b = 3$ bits and store:

A = [3, 5, 1, 6]

Binary values:

value	bits
3	011
5	101
1	001
6	110

Packed sequence:

011\ 101\ 001\ 110

Reading index $2$ extracts bits:

001 = 1

Correctness

Each element occupies exactly $b$ consecutive bits starting at position $i \cdot b$ . The mask isolates those bits. When the element spans two words, the algorithm combines bits from both words to reconstruct the value.

Writing clears the target bits and inserts the new value without affecting neighboring elements.

Complexity

operation	time
get	$O(1)$
set	$O(1)$

Space usage:

O\left(\frac{n \cdot b}{W}\right)

which is significantly smaller than storing full-width integers.

When to Use

Bit-packed arrays are appropriate when:

values have small fixed ranges
memory footprint is critical
large datasets must fit in cache or memory

They are less suitable when:

frequent updates require simplicity
values require full machine word precision
code clarity is more important than compression

Implementation

class BitPackedArray:
    def __init__(self, n, bits):
        self.n = n
        self.b = bits
        self.W = 64
        size = (n * bits + self.W - 1) // self.W
        self.data = [0] * size

    def get(self, i):
        p = i * self.b
        w = p // self.W
        o = p % self.W

        value = (self.data[w] >> o) & ((1 << self.b) - 1)

        if o + self.b > self.W:
            next_part = self.data[w + 1] << (self.W - o)
            value |= next_part & ((1 << self.b) - 1)

        return value

    def set(self, i, x):
        p = i * self.b
        w = p // self.W
        o = p % self.W

        mask = ((1 << self.b) - 1) << o
        self.data[w] = (self.data[w] & ~mask) | (x << o)

        if o + self.b > self.W:
            spill = x >> (self.W - o)
            mask2 = (1 << (o + self.b - self.W)) - 1
            self.data[w + 1] = (self.data[w + 1] & ~mask2) | spill

type BitPackedArray struct {
    data []uint64
    n    int
    b    uint
}

func NewBitPackedArray(n int, bits uint) *BitPackedArray {
    W := uint(64)
    size := (uint(n)*bits + W - 1) / W
    return &BitPackedArray{
        data: make([]uint64, size),
        n:    n,
        b:    bits,
    }
}

func (a *BitPackedArray) Get(i int) uint64 {
    W := uint(64)
    p := uint(i) * a.b
    w := p / W
    o := p % W

    value := (a.data[w] >> o) & ((1 << a.b) - 1)

    if o+a.b > W {
        next := a.data[w+1] << (W - o)
        value |= next & ((1 << a.b) - 1)
    }

    return value
}

func (a *BitPackedArray) Set(i int, x uint64) {
    W := uint(64)
    p := uint(i) * a.b
    w := p / W
    o := p % W

    mask := ((uint64(1)<<a.b)-1) << o
    a.data[w] = (a.data[w] & ^mask) | (x << o)

    if o+a.b > W {
        spill := x >> (W - o)
        mask2 := (uint64(1) << (o + a.b - W)) - 1
        a.data[w+1] = (a.data[w+1] & ^mask2) | spill
    }
}