Calculate Variable Byte Code
Estimate how many bytes a non-negative integer needs under variable-byte encoding, compare it with fixed-width storage, and visualize the storage savings instantly.
Expert Guide: How to Calculate Variable Byte Code Correctly
Variable-byte coding is a compact integer encoding technique used in search engines, inverted indexes, analytics systems, and compressed storage formats. If you need to calculate variable byte code, the central idea is simple: instead of storing every integer in a fixed number of bytes such as 4 bytes for a 32-bit integer, you store small numbers in fewer bytes and larger numbers in more bytes. That means the encoded size depends on the actual value being stored, not just on the maximum size of the data type.
In the most common form of variable-byte encoding, each byte contributes 7 bits of payload data and reserves 1 bit as a continuation or stop indicator. This design allows compact representation of small values while still supporting much larger numbers by chaining multiple bytes together. For workloads dominated by small integers, or by small gaps between sorted values, variable-byte encoding can reduce storage substantially.
What variable-byte code means in practice
Each encoded byte is 8 bits long. However, only 7 bits are available for the numeric payload. The remaining bit tells the decoder whether this is the last byte in the sequence or whether another byte follows. In many descriptions, the high bit acts as the control bit. Depending on the convention, a value of 1 may indicate the last byte, or a value of 1 may indicate continuation. The exact marker scheme can vary across implementations, but the storage math stays the same: every encoded byte carries 7 useful bits of the integer.
Because each byte contributes 7 data bits, the number of bytes needed for a non-negative integer is based on how many bits are necessary to represent that value in binary. The formula is:
- If the value is 0, it still takes 1 byte.
- For values greater than 0, determine the binary bit length.
- Divide the bit length by 7.
- Round up to the next whole number.
Mathematically, for a positive integer n, the encoded length in bytes is ceil(bit_length(n) / 7). This is the core rule our calculator uses.
Why 7 bits per byte matters
Many developers first assume that byte-oriented compression gains come from bit-packing or Huffman-style coding. Variable-byte coding is different. It works at the byte level, so it remains easier to implement and decode quickly in software. The trade-off is that each byte sacrifices one bit for control. As a result, there are natural value ranges for each encoded length:
- 1 byte stores values from 0 to 127
- 2 bytes store values from 128 to 16,383
- 3 bytes store values from 16,384 to 2,097,151
- 4 bytes store values from 2,097,152 to 268,435,455
- 5 bytes store values from 268,435,456 to 34,359,738,367
These boundaries come directly from powers of two. One variable-byte block stores 7 payload bits, so its maximum value range is 27 minus 1, which is 127. Two bytes store 14 payload bits, so the maximum is 214 minus 1, or 16,383. This pattern is why powers of 128 appear frequently in variable-byte encoding examples.
| Encoded bytes | Payload bits | Value range | Max value |
|---|---|---|---|
| 1 | 7 | 0 to 127 | 127 |
| 2 | 14 | 128 to 16,383 | 16,383 |
| 3 | 21 | 16,384 to 2,097,151 | 2,097,151 |
| 4 | 28 | 2,097,152 to 268,435,455 | 268,435,455 |
| 5 | 35 | 268,435,456 to 34,359,738,367 | 34,359,738,367 |
Step-by-step example of calculating variable byte code
Suppose you want to encode the integer 824. First convert it to binary. The binary representation of 824 is 1100111000, which uses 10 bits. Since each variable-byte unit can carry only 7 bits of payload, you need:
ceil(10 / 7) = 2 bytes
That means 824 takes 2 bytes in variable-byte coding. If you had stored the same value in a 32-bit integer, it would consume 4 bytes. For one value, that is a reduction from 4 bytes to 2 bytes, which is a 50% savings. For 1,000 values of similar magnitude, that becomes a reduction from 4,000 bytes to 2,000 bytes.
This is the main reason variable-byte coding is popular in indexing systems. Posting lists often store gaps between sorted document IDs rather than raw IDs themselves. Those gaps are usually much smaller than the original document IDs, so many of them fall into the 1-byte or 2-byte range.
How to compare variable-byte code with fixed-width storage
When evaluating storage, the most useful comparison is against a fixed-width integer type, usually 32 bits or 64 bits. Fixed-width storage has one big advantage: every value uses the same amount of memory, which simplifies indexing, alignment, and direct random access. Variable-byte coding, on the other hand, improves space efficiency when values are small but can slow random access because lengths vary.
Here is a practical comparison of encoded size for representative values:
| Integer value | Binary bit length | Variable-byte size | 32-bit storage | Savings vs 32-bit |
|---|---|---|---|---|
| 12 | 4 bits | 1 byte | 4 bytes | 75% |
| 127 | 7 bits | 1 byte | 4 bytes | 75% |
| 128 | 8 bits | 2 bytes | 4 bytes | 50% |
| 16,383 | 14 bits | 2 bytes | 4 bytes | 50% |
| 1,000,000 | 20 bits | 3 bytes | 4 bytes | 25% |
| 300,000,000 | 29 bits | 5 bytes | 4 bytes | -25% |
This table reveals an important truth: variable-byte code is not automatically smaller than fixed-width encoding for every input. Once values become large enough, the control-bit overhead can exceed the savings. For example, a 29-bit value fits inside a 32-bit integer in 4 bytes, but variable-byte coding needs 5 bytes because it can only carry 7 payload bits per byte. That is why distribution matters more than worst-case size.
Where the biggest savings usually come from
The strongest use case for variable-byte coding is a sequence of small integers. Search engines are the classic example. Instead of storing a postings list as absolute document identifiers, systems often store the difference between neighboring IDs. If the sequence is sorted and fairly dense, these gaps can be tiny. Tiny gaps frequently fit inside one variable byte, which dramatically reduces total index size.
- Telemetry counters with small increments
- Sorted identifier gaps in inverted indexes
- Compact storage for event offsets
- Log deltas and sparse matrix coordinates
- Columnar data where many values stay within small ranges
If your dataset has mostly values below 128, then variable-byte coding gives you a fixed 1-byte representation for most entries. Compared with 32-bit integers, that is a 75% reduction. If values mostly remain below 16,384, they usually take 2 bytes, still yielding 50% savings versus 32-bit storage.
Common mistakes when calculating variable-byte code
Many storage estimates are wrong because they skip one of these details:
- Ignoring the zero case. The value 0 still requires one encoded byte.
- Using decimal digits instead of binary bits. Variable-byte boundaries are based on powers of two, not on the number of decimal digits.
- Confusing encoding conventions. Different implementations may mark the last byte differently, but each byte still carries only 7 payload bits.
- Forgetting sequence overhead. In a real format, metadata, block headers, or alignment can affect total storage.
- Comparing a best-case sample against a worst-case baseline. Use the actual value distribution when estimating savings.
How to estimate storage for large datasets
If you want to estimate total encoded size for many numbers, the best method is to calculate the byte count per value and sum the results. For a quick approximation, you can use a representative average value or a histogram. For example, if 70% of values fit in 1 byte, 25% fit in 2 bytes, and 5% fit in 3 bytes, then the average storage is:
(0.70 x 1) + (0.25 x 2) + (0.05 x 3) = 1.35 bytes per value
Compared with 4 bytes per value for 32-bit storage, that is approximately 66.25% savings. This kind of weighted estimate is often more realistic than relying on a single test value.
Performance and compression trade-offs
Variable-byte coding is attractive because it is relatively easy to encode and decode, and it compresses small integers well. However, it is not always the fastest or smallest method available. More advanced integer compression schemes such as gamma coding, delta coding, Simple-9 variants, Frame of Reference, SIMD-BP128, or PForDelta can outperform variable-byte coding in either speed or compression ratio depending on the workload. Still, variable-byte code remains a common baseline because it is easy to reason about and simple to implement.
When you use this calculator, remember that it estimates the raw variable-byte encoded payload for a repeated value. It does not include application-specific framing, collection headers, or transport-level overhead. In practical systems, those extra bytes may matter when records are very small.
Rule-of-thumb thresholds you can memorize
- Up to 127: 1 byte
- Up to 16,383: 2 bytes
- Up to 2,097,151: 3 bytes
- Up to 268,435,455: 4 bytes
- Above that and up to 35 payload bits: 5 bytes
These thresholds make mental estimation easy. If your values usually sit in the hundreds, expect 2 bytes. If they sit in the tens of thousands, expect 3 bytes only when they exceed 16,383. If they sit in the low millions, 3 bytes is often enough. Once values consistently exceed roughly 268 million, the variable-byte representation often becomes larger than a 32-bit fixed integer.
Authoritative references and further reading
For deeper technical reading, these sources are useful:
- Stanford University: Variable-byte codes in information retrieval
- National Institute of Standards and Technology (NIST)
- San Jose State University lecture notes on index compression
Bottom line
If you need to calculate variable byte code, focus on one fact: each encoded byte contributes 7 bits of actual integer payload. Find the binary bit length of the number, divide by 7, and round up. Then compare that result with your fixed-width baseline such as 16-bit, 32-bit, or 64-bit storage. For small values and gap-encoded sequences, variable-byte coding can save significant space. For very large values, the benefit may shrink or even reverse. The calculator above helps you measure that trade-off immediately.