Elias Gamma Coding

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.

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.

<!-- {{c_html_intro}} -->
<div class="tabs">
  <button class="tab active" data-tab="encode">{{tab_encode}}</button>
  <button class="tab" data-tab="decode">{{tab_decode}}</button>
</div>

<!-- {{c_encode_panel}} -->
<div id="panel-encode" class="panel">
  <label class="field-label" for="num-input">{{label_number}}</label>
  <div class="row">
    <input id="num-input" type="number" min="1" max="65535" value="13" />
    <button id="btn-encode" type="button">{{btn_encode}}</button>
  </div>
  <div id="encode-result" class="result-box hidden"></div>
  <div id="encode-steps" class="steps hidden"></div>
</div>

<!-- {{c_decode_panel}} -->
<div id="panel-decode" class="panel hidden">
  <label class="field-label" for="bits-input">{{label_bits}}</label>
  <div class="row">
    <input id="bits-input" type="text" placeholder="{{placeholder_bits}}" />
    <button id="btn-decode" type="button">{{btn_decode}}</button>
  </div>
  <div id="decode-result" class="result-box hidden"></div>
</div>

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

/* {{c_tab_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; }

/* {{c_panel_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; }

/* {{c_result_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; }

/* {{c_codeword_styles}} */
.codeword { font-size: 1.25rem; letter-spacing: .12em; margin-bottom: .3rem; }
.zeros { color: #c92f3c; }
.one-bit { color: #0a7d33; font-weight: 700; }
.payload { color: #1d5597; }

/* {{c_steps_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; }

/* {{c_decode_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; }

// Code not found

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

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

To encode $n$, write $k = \lfloor \log_2 n \rfloor$. The codeword is $k$ zero bits, then the $k+1$-bit binary representation of $n$. Total length: $2k + 1 = 2\lfloor \log_2 n \rfloor + 1$ bits.

• For $n = 1$: $k = 0$, codeword 1 — just one bit.
• For $n = 4$: $k = 2$, codeword 00 100 — five bits.
• For $n = 1000$: $k = 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 $k$, then read $k + 1$ more bits — done. This is the same property that makes compression schemes like Huffman coding work.

The tradeoff: for large $n$, gamma coding uses roughly $2 \log_2 n$ bits. Elias delta coding, a refinement, reduces this to $\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.

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.

Elias gamma coding makes a striking promise: give it any positive integer, and it will encode it in $2\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.