Introduction

Every time your computer stores the number 3, it wastes 29 bits: a 32-bit integer spends most of its capacity on leading zeros. That is fine when you know in advance that numbers stay below four billion. But what if you are streaming an endless sequence of integers and most of them are small?

Elias gamma coding, published by Peter Elias in 1975, solves this with a beautifully simple idea: write the binary representation of a number, then prefix it with a unary count of how many bits that representation has. The result is a self-delimiting bitstream — a decoder reading the stream knows exactly where each codeword ends without any length field or separator byte.

The code is universal: it is optimal (up to a constant factor) for any source whose probabilities decrease monotonically, without knowing the distribution in advance. Small integers get short codes; large ones get longer codes; but no integer is ever left out.

Elias gamma is the foundation under a family of related codes — Elias delta, Fibonacci coding, compression algorithms, and the inverted indexes behind every modern search engine.

Try It

Type a positive integer and the encoder will produce its Elias gamma codeword, breaking it down step by step. You can also paste a raw bitstream to decode it back into a sequence of integers.

<!-- Elias gamma coding demo — encode integers or decode a raw bitstream -->
<div class="tabs">
  <button class="tab active" data-tab="encode">Encode</button>
  <button class="tab" data-tab="decode">Decode</button>
</div>

<!-- Encode panel — user types a positive integer -->
<div id="panel-encode" class="panel">
  <label class="field-label" for="num-input">Positive integer (1 – 65535)</label>
  <div class="row">
    <input id="num-input" type="number" min="1" max="65535" value="13" />
    <button id="btn-encode" type="button">Encode</button>
  </div>
  <div id="encode-result" class="result-box hidden"></div>
  <div id="encode-steps" class="steps hidden"></div>
</div>

<!-- Decode panel — user pastes a raw bitstream -->
<div id="panel-decode" class="panel hidden">
  <label class="field-label" for="bits-input">Bitstream (0s and 1s)</label>
  <div class="row">
    <input id="bits-input" type="text" placeholder="e.g. 1 010 00110" />
    <button id="btn-decode" type="button">Decode</button>
  </div>
  <div id="decode-result" class="result-box hidden"></div>
</div>

/* Elias gamma coding demo styles */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #fff; }

/* Tab switcher styles */
.tabs { display: flex; gap: .35rem; margin-bottom: .75rem; }
.tab { font: 600 13px system-ui; padding: .35rem .85rem; border: 1.5px solid #1d3557;
       border-radius: 6px; cursor: pointer; background: #fff; color: #1d3557; transition: all .15s; }
.tab.active { background: #1d3557; color: #fff; }

/* Panel and form styles */
.panel { display: block; }
.panel.hidden { display: none; }
.field-label { display: block; font-size: .82rem; color: #555; margin-bottom: .3rem; }
.row { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
input[type="number"], input[type="text"] {
  font: 14px ui-monospace, monospace; padding: .4rem .6rem; border: 1.5px solid #adb1b8;
  border-radius: 6px; width: 140px; }
input[type="text"] { width: 200px; }
button { font: 600 14px system-ui; padding: .42rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; }

/* Result box styles */
.result-box { background: #f0f4f8; border: 1px solid #cdd9e3; border-radius: 8px;
              padding: .6rem .8rem; margin-bottom: .5rem; font: 14px ui-monospace, monospace; }
.result-box.hidden { display: none; }
.result-box.error { border-color: #c92f3c; background: #fff0f1; color: #c92f3c; }

/* Colored codeword display — red=unary zeros, green=leading 1, blue=payload */
.codeword { font-size: 1.25rem; letter-spacing: .12em; margin-bottom: .3rem; }
.zeros { color: #c92f3c; }
.one-bit { color: #0a7d33; font-weight: 700; }
.payload { color: #1d5597; }

/* Step-by-step breakdown styles */
.steps { background: #f8fafc; border: 1px solid #cdd9e3; border-radius: 8px;
         padding: .55rem .8rem; font-size: .82rem; line-height: 1.7; color: #333; }
.steps.hidden { display: none; }
.steps code { background: #e2eaf2; border-radius: 3px; padding: .05em .3em; font-size: .85rem; }

/* Decoded integer list styles */
.decode-row { display: flex; gap: .6rem; align-items: baseline; padding: .2rem 0;
              border-bottom: 1px solid #e4eaf0; }
.decode-row:last-child { border: none; }
.di { color: #888; min-width: 1.8rem; text-align: right; font-size: .78rem; }
.dbits { color: #1d5597; }
.dval { font-weight: 700; color: #1d3557; min-width: 3rem; text-align: right; }

/* Elias gamma coding — encode and decode logic */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* gammaEncode(n): returns unary prefix zeros, binary body, and full bitstring */
function gammaEncode(n) {
  if (n < 1 || !Number.isInteger(n)) return null;
  const k = Math.floor(Math.log2(n));
  const zeros = '0'.repeat(k);
  const body = n.toString(2).padStart(k + 1, '0');
  return { k, zeros, body, bits: zeros + body };
}

/* gammaDecode(bits): parses a flat bitstream back into an array of {bits, value, k} objects */
function gammaDecode(bits) {
  const results = [];
  let i = 0;
  while (i < bits.length) {
    /* Count leading zeros to find k (the unary prefix) */
    let k = 0;
    while (i < bits.length && bits[i] === '0') { k++; i++; }
    /* Read k+1 bits for the binary body; convert to integer */
    if (i >= bits.length) break;
    const bodyBits = bits.slice(i, i + k + 1);
    if (bodyBits.length < k + 1) break;
    const value = parseInt(bodyBits, 2);
    results.push({ bits: '0'.repeat(k) + bodyBits, value, k });
    i += k + 1;
  }
  return results;
}

/* Tab switching logic */
function switchTab(name) {
  document.querySelectorAll('.tab').forEach(t => t.classList.toggle('active', t.dataset.tab === name));
  document.getElementById('panel-encode').classList.toggle('hidden', name !== 'encode');
  document.getElementById('panel-decode').classList.toggle('hidden', name !== 'decode');
}
document.querySelectorAll('.tab').forEach(t => t.addEventListener('click', () => switchTab(t.dataset.tab)));

/* Encode button handler — validate, encode, render result and steps */
document.getElementById('btn-encode').addEventListener('click', () => {
  const raw = document.getElementById('num-input').value.trim();
  const n = parseInt(raw, 10);
  const resBox = document.getElementById('encode-result');
  const stepsBox = document.getElementById('encode-steps');
  if (!raw || isNaN(n) || n < 1) {
    resBox.className = 'result-box error';
    resBox.textContent = 'Please enter a positive integer between 1 and 65535.';
    resBox.classList.remove('hidden');
    stepsBox.classList.add('hidden');
    return;
  }
  const enc = gammaEncode(n);
  /* Build colored codeword and step-by-step breakdown */
  resBox.className = 'result-box';
  resBox.innerHTML =
    '<div class="codeword">' +
    '<span class="zeros">' + enc.zeros + '</span>' +
    '<span class="one-bit">' + enc.body[0] + '</span>' +
    '<span class="payload">' + enc.body.slice(1) + '</span>' +
    '</div>' +
    '<div>' + i18nFmt('Codeword length: %bits% bit(s)', { bits: enc.bits.length }) + '</div>';
  resBox.classList.remove('hidden');
  stepsBox.innerHTML =
    '<b>Step-by-step breakdown</b><br>' +
    i18nFmt('k = ⌊log₂(%n%)⌋ = %k% (the binary length of %n% minus 1)', { k: enc.k, n: n }) + '<br>' +
    i18nFmt('Unary prefix: %k% zero bit(s)', { k: enc.k }) + '<br>' +
    i18nFmt('Binary body: %body% (the %n% in binary, padded to k+1 bits)', { body: enc.body, n: n }) + '<br>' +
    i18nFmt('Full codeword: %bits%', { bits: enc.bits });
  stepsBox.classList.remove('hidden');
});

/* Decode button handler — validate bits, decode stream, render list */
document.getElementById('btn-decode').addEventListener('click', () => {
  const raw = document.getElementById('bits-input').value.replace(/\s+/g, '');
  const resBox = document.getElementById('decode-result');
  if (!/^[01]+$/.test(raw)) {
    resBox.className = 'result-box error';
    resBox.textContent = 'Bitstream must contain only 0s and 1s.';
    resBox.classList.remove('hidden');
    return;
  }
  const decoded = gammaDecode(raw);
  if (!decoded.length) {
    resBox.className = 'result-box error';
    resBox.textContent = 'Could not decode any integer from the given bits.';
    resBox.classList.remove('hidden');
    return;
  }
  resBox.className = 'result-box';
  resBox.innerHTML = decoded.map((r, i) =>
    '<div class="decode-row">' +
    '<span class="di">' + (i + 1) + '.</span>' +
    '<span class="dbits">' + r.bits + '</span>' +
    '<span>→</span>' +
    '<span class="dval">' + r.value + '</span>' +
    '</div>'
  ).join('');
  resBox.classList.remove('hidden');
});
Result
Console

Notice how the code length grows slowly: the codeword for nn uses 2⌊log⁡2n⌋+12\lfloor \log_2 n \rfloor + 1 bits. Doubling nn adds only two bits — a logarithmic penalty that keeps the code efficient across a huge range of values.

The Real Complexity

How efficient is Elias gamma coding? The answer lives in a single formula.

To encode nn, write k=⌊log⁡2n⌋k = \lfloor \log_2 n \rfloor. The codeword is kk zero bits, then the k+1k+1-bit binary representation of nn. Total length: 2k+1=2⌊log⁡2n⌋+12k + 1 = 2\lfloor \log_2 n \rfloor + 1 bits.

  • For n=1n = 1: k=0k = 0, codeword 1 — just one bit.
  • For n=4n = 4: k=2k = 2, codeword 00 100 — five bits.
  • For n=1000n = 1000: k=9k = 9, nineteen bits — versus 32 for a fixed-width int.

Why "universal"? A code is universal if its expected length is within a constant factor of the optimal (Shannon entropy) length for any monotone decreasing probability distribution over the positive integers. Elias proved that gamma coding achieves this. You never have to know the source statistics in advance.

The prefix-free property is what makes the code self-delimiting. No codeword is a prefix of another, so a decoder can read bit by bit: count the leading zeros to get kk, then read k+1k + 1 more bits — done. This is the same property that makes compression schemes like Huffman coding work.

The tradeoff: for large nn, gamma coding uses roughly 2log⁡2n2 \log_2 n bits. Elias delta coding, a refinement, reduces this to log⁡2n+2log⁡2log⁡2n\log_2 n + 2 \log_2 \log_2 n bits for the same value — better asymptotically, at the cost of a slightly more complex encoder.

Where It Matters

Self-delimiting integer codes are not a textbook curiosity — they sit inside systems you use every day:

  • Inverted indexes for search: every modern search engine stores posting lists — sequences of document IDs — using variable-length codes. Elias gamma and its relatives let those lists consume a fraction of the space that fixed-width integers would.
  • Genomics and bioinformatics: reference genome databases store billions of small integers (position offsets, quality scores). Gamma and delta codes cut storage by 50–80 % compared with naive 32-bit encoding.
  • Universal source coding: when you do not know the distribution of a source in advance, gamma coding gives you a provably near-optimal code without a training pass. This is the key idea behind algorithms like the Lempel-Ziv family and compression in general.
  • Network protocols: length-prefixed messages in binary protocols often use variable-length integer encodings inspired directly by Elias gamma to minimize header overhead.

Anywhere integers cluster near zero and occasionally spike large — log entries, difference lists, run lengths — Elias gamma coding shines. It is the simplest member of a family of codes that trade a tiny amount of encoder complexity for large savings in space.

Conclusion

Elias gamma coding makes a striking promise: give it any positive integer, and it will encode it in 2⌊log⁡2n⌋+12\lfloor \log_2 n \rfloor + 1 bits — no lookup table, no size header, no separator. The decoder reads the stream and stops precisely when the codeword ends.

That self-delimiting property is the key. It turns a sequence of integers into a flat bitstream that can be written, read, and concatenated without any framing overhead. And because the code is universal, you do not need to know the integer distribution in advance — the code adapts automatically.

Peter Elias invented it in 1975 as a theoretical tool for universal source coding. Half a century later it is still inside the indexes that retrieve your web search results. Elegant ideas tend to stick around.

To go deeper, explore how compression algorithms build on prefix-free codes, or see how the same self-delimiting philosophy scales up to the halting problem and Kolmogorov complexity.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/elias-gamma-coding/Content licensed under CC BY-NC 4.0.