Elias Gamma Coding

An Elias-Gamma code is a type of universal code. To encode any non-negative, non-zero integer x using the Elias-Gamma code:

1. Write down x in binary
2. Count the bits written, and write that number of starting zero bits preceding the previous bit string.

In essence, its a Unary Coding of how many bits, followed by the bits.

The first few values of the code are:

 1 ⇒ 1 ⇒ 1
 2 ⇒ 10 ⇒ 010
 3 ⇒ 11 ⇒ 011
 4 ⇒ 100 ⇒ 00100
 5 ⇒ 101 ⇒ 00101
 6 ⇒ 110 ⇒ 00110
 7 ⇒ 111 ⇒ 00111
 8 ⇒ 1000 ⇒ 0001000
 9 ⇒ 1001 ⇒ 0001001
...

Example Code

void write_EliasGamma(unsigned val) 
{
    unsigned highest_bit_set = 32 - IntegerLog2(val);
    write_bits(0, highest_bit_set-1);
    if(highest_bit_set > 0) {
        write_bits(val, highest_bit_set);
    }
}

unsigned read_EliasGamma() 
{
    int highest_bit_set = 0;
    do {
        ++highest_bit_set;
    } while(!read_bits(1));
    unsigned val = read_bits(highest_bit_set) | (1<<highest_bit_set);
    return val;
}

See Finding integer log base 2 of an integer (aka the position of the highest bit set) for how to compute IntegerLog2().