Basic
We want to store a list of positive integers using not too much memory.
An int is usually strored in 32 bits, but small values have a lot of zeros on the left
Decimal => Binary
5 => 0000 0000 0000 0000 0000 0000 0000 0101
1895 => 0000 0000 0000 0000 0000 0111 0110 0111
Since we don't know in advance the biggest value of our list, we can't set a maximum value and use instead of 32bits, X bits where X is the number of bits used for that maximum value. eg, if our values would be between 0 and 255, we knew we could encode our values on 8 bits instead of 32.
Elias gamma will allow us to encode our values on a variable number of bits. For the biggest numbers we will use more than 32 bits (worse then that the classic encoding) but for the smallest ones, we will use considerably less bits.
Elias gamma is thus used to encode lists of relatively small positive integers when we don't know in advance the maximum value.
We can also generalize and encode positive and negatives integer.
3 steps encoding
We want to encode X > 0
1/ Write the binary form : B
2/ Count the number of bits : N
3 / Append N-1 zeros to the left of B
Examples
X=8
1) B = 1000
2) N = 4
3) Gamma code = 000 1000
X=3
1) B = 11
2) N = 2
3) Gamma code = 011