I once found on Wikipedia a nice technique for encoding $k \in (2^{n-1}, 2^n)$ uniformly distributed integer numbers with less then $\log_2n$ average bits/symbol, thanks to a simple to compute variable length code. Basically it used $\log_2n$ for some symbols and $\log_2n - 1$ for some others.

Unfortunately all my Googling has failed me. I recall something similar to "variable length binary", but I keep ending on VLQ which are a different beast. Since I know your memory better than mine, can you help me?

  • $\begingroup$ Look for prefix code, prefix-free code, uniquely decodable code, or variable-length code. $\endgroup$ Commented Mar 25, 2020 at 16:12
  • $\begingroup$ You are interested in the reverse direction of Kraft's inequality. $\endgroup$ Commented Mar 25, 2020 at 16:13

3 Answers 3


The technique idea is perfectly described in Yuval Filmus answer. Even if slightly different, it is called Truncated binary encoding in Wikipedia. I couldn't find an original source for that, apart from a mention in a patent, in this book, or in this Google API

Another mention can be found in the ACM ICPC 2011–2012, Northeastern European Regional Contest, November 27, 2011.


Suppose $k = 2^{n-1} + t$, where $0 \leq t < 2^{n-1}$. Use the following to encode $z \in \{0,\ldots,k-1\}$:

  • If $z < 2^{n-1}-t$ then encode $z$ as its own $(n-1)$-bit encoding.
  • Otherwise, write $z = 2^{n-1}-t + 2\delta+\epsilon$, where $\delta \in \{0,\ldots,t-1\}$ and $\epsilon \in \{0,1\}$. Encode $z$ at the $(n-1)$-bit encoding of $2^{n-1}-t+\delta$ followed by $\epsilon$.

Here is an example. Let $k = 11 = 2^3+3$. The encoding is as follows:

  • $0 \to 000$.
  • $1 \to 001$.
  • $2 \to 010$.
  • $3 \to 011$.
  • $4 \to 100$.
  • $5 \to 1010$.
  • $6 \to 1011$.
  • $7 \to 1100$.
  • $8 \to 1101$.
  • $9 \to 1110$.
  • $10 \to 1111$.
  • 1
    $\begingroup$ This is exactly the correct reasoning. I was also missing the name of this version of the encoding. It's Truncated binary encoding, according to Wikipedia. $\endgroup$ Commented Mar 25, 2020 at 18:32

Usually (a, b) is an open interval, excluding a and b, and [a, b] is a closed interval, including a and b. So $(2^{n-1}, 2^n)$ is the set of numbers from $2^{n-1} + 1$ to $2^n-1$.

To encode, subtract $2^{n-1}+1$ from a number x, leaving $0 ≤ x < 2^{n-1}-1$. There are $2^{n-1}-1$ possible numbers, each with same probability, so you can use Huffman coding for just under n-1 bits on average. To be precise, you have $2^{n-1} - 2$ numbers encoded in n-1 bits, and one number encoded in n-2 bits, for an average of $n-1-1/(2^{n-1}-1)$ bits.

You could use arithmetic coding, which would be a tiny, tiny bit shorter on average with a very good implementation, but would be much much more complicated. Not worth it in this case; possibly worth it if you had say $1.5 \cdot 2^n$ different numbers to store and storage size is very important to you.

  • $\begingroup$ I think you didn't understand the question correctly. There are $k$ uniformly distributed numbers. These numbers are from $0$ to $k-1$. You cannot use entropy coding, because all of them have the same probability. $\endgroup$ Commented Dec 11, 2020 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.