Uses floor(log2(x)) + 2*floor(log2(floor(log2(x))+1))+1 bits to store an integer.

Does not encode zeroes or negative numbers. You need ZigZag encoding for that.

Encoding

Find the highest power of two in X as floor(log2(x)), assign as N

Encode N+1 with Gamma encoding

Append remaining N bits

Decoding

Decode Gamma encoded integer, assign to N.

Read N-1 remaining bits.

Add 2^(N-1) and the remaining bits together.

• Elias Gamma Encoding