Overview
Bit-Packing writes fixed-width or variable-width fields into a compact binary stream instead of storing each value in a full machine word.
ExtendedSource checked
Bit-Packing
Stores small integer values using only the number of bits they need.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Compression
- Difficulty
- Intermediate
- Family
- Binary Encoding
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
bit widthmaskingshiftingpacked buffer
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(ceil(n * bits / word_size))
When to Use
- Use when many values fit in fewer bits than their normal integer type.
- Use when columnar data storage is a central requirement.
When Not to Use
- Avoid when random access or portability is more important than compactness.
- Avoid when the added bit-level complexity is not worth the expected size reduction.
What It Does
- Chooses a bit width
- Writes values into packed fields
- Reads fields back with shifts and masks
Use Cases
- Columnar data storage
- Network protocols
- Index compression
Inputs
- Integer sequence
- Bit width or maximum value
Outputs
- Packed binary buffer
Key Formulas (1)
Required bit width
bits = ⌈log2(maxvalue + 1)⌉
bits = ceil(log2(max_value + 1))Chooses how many bits are needed for unsigned values up to the maximum.
Pseudocode
- 1.Find the required bit width
- 2.For each value, shift it into the current output word
- 3.Flush full words to the buffer
- 4.During decoding, mask and shift fields back out
Canonical Example
- Input
- values = [3, 1, 2], bits = 2
- Output
- packed bits = 11 01 10
- Explanation
- Each value fits in two bits instead of a full byte or word.
Implementation Notes
- Write independent pack and unpack tests for values at the maximum bit width.
- Write round-trip tests that encode and decode small hand-checked inputs.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Signed values and overflow need explicit representation rules.
- Encoder and decoder must make exactly the same modeling and bit-order choices.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow several small integers occupying adjacent bit fields inside machine words.
Input:ABABABCABAB
Window:ABAB
Step 1 of 4: Find the required bit width
encoding-streamNotes
Bit order and alignment must be documented for interoperable encoders.
Sources (1)
What each reference supports for this entry.
Introduction to Data Compression
BookCompression reference for Bit-Packing bit-level representation, packing fields, and entropy-coding support.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborDelta Encoding
Delta-encoded values are often bit-packed when their range is small.
Often paired withVariable-Length Encoding
Bit packing is often used alongside compact integer encodings.
Related Algorithms
Tags
CompressionBit LevelInteger DataEncoding