Elias gamma coding

Elias gamma code is a universal code encoding the positive integers. To code a number:

1. Write it in binary.
2. Subtract 1 from the number of bits written in step 1 and prepend that many zeros.

An equivalent way to express the same process:

1. Separate the integer into the highest power of 2 it contains (2^N) and the remaining N binary digits of the integer.
2. Encode N in unary; that is, as N zeroes followed by a one.
3. Append the remaining N binary digits to this representation of N.

The code begins:

 1 1
  2 010
  3 011
  4 00100
  5 00101
  6 00110
  7 00111
  8 0001000
  9 0001001
 10 0001010
 11 0001011
 12 0001100
 13 0001101
 14 0001110
 15 0001111
 16 000010000
 17 000010001
 

To decode an Elias gamma-coded integer:

1. Read and count zeroes from the stream until you reach the first one. Call this count of zeroes N.
2. Considering the one that was reached to be the first digit of the integer, with a value of 2^N, read the remaining N digits of the integer.

Gamma coding is used in applications where the largest encoded value is not known ahead of time, or to compress data in which small values are much more frequent than large values.

See also Elias delta coding, Elias omega coding

See also: Elias gamma coding, Binary numeral system, Data compression, Elias delta coding, Elias omega coding, Number, Unary, Universal code