# Bit-Packed Array

# 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:

```id="bit-packed-get"
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:

```id="bit-packed-set"
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

```python id="bit-packed-python"
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
```

```go id="bit-packed-go"
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
    }
}
```