# Elias delta coding

Elias delta code is a universal code encoding the positive integers developed by Peter Elias.[1]:200 To code a number X≥1:

1. Let N=⌊log2 X⌋ be the highest power of 2 in X, so 2NX < 2N+1.
2. Let L=⌊log2 N+1⌋ be the highest power of 2 in N+1, so 2LN+1 < 2L+1.
3. Write L zeros, followed by
4. the L+1-bit binary representation of N+1, followed by
5. all but the leading bit (i.e. the last N bits) of X.

An equivalent way to express the same process:

1. Separate X into the highest power of 2 it contains (2N) and the remaining N binary digits.
2. Encode N+1 with Elias gamma coding.
3. Append the remaining N binary digits to this representation of N+1.

To represent a number $x$, Elias delta uses $\lfloor \log_2(x) \rfloor + 2 \lfloor \log_2 (\lfloor \log_2(x) \rfloor +1) \rfloor + 1$ bits.[1]:200

The code begins, using $\gamma'$ instead of $\gamma$:

Number N N+1 Encoding Implied probability
1 = 20 0 1 1 1/2
2 = 21 + 0 1 2 0100 1/16
3 = 21 + 1 1 2 0101
4 = 22 + 0 2 3 01100 1/32
5 = 22 + 1 2 3 01101
6 = 22 + 2 2 3 01110
7 = 22 + 3 2 3 01111
8 = 23 + 0 3 4 00100000 1/256
9 = 23 + 1 3 4 00100001
10 = 23 + 2 3 4 00100010
11 = 23 + 3 3 4 00100011
12 = 23 + 4 3 4 00100100
13 = 23 + 5 3 4 00100101
14 = 23 + 6 3 4 00100110
15 = 23 + 7 3 4 00100111
16 = 24 + 0 4 5 001010000 1/512
17 = 24 + 1 4 5 001010001

To decode an Elias delta-coded integer:

1. Read and count zeros from the stream until you reach the first one. Call this count of zeros L.
2. Considering the one that was reached to be the first digit of an integer, with a value of 2L, read the remaining L digits of the integer. Call this integer N+1, and subtract one to get N.
3. Put a one in the first place of our final output, representing the value 2N.
4. Read and append the following N digits.

Example:

001010011
1. 2 leading zeros in 001
2. read 2 more bits i.e. 00101
3. decode N+1 = 00101 = 5
4. get N = 5 − 1 = 4 remaining bits for the complete code i.e. '0011'
5. encoded number = 24 + 3 = 19


This code can be generalized to zero or negative integers in the same ways described in Elias gamma coding.

## Example code

### Encoding

void eliasDeltaEncode(char* source, char* dest)
{
BitWriter bitwriter(dest);
{
int len = 0;
int lengthOfLen = 0;
for (int temp = num; temp > 0; temp >>= 1)  // calculate 1+floor(log2(num))
len++;
for (int temp = len; temp > 1; temp >>= 1)  // calculate floor(log2(len))
lengthOfLen++;
for (int i = lengthOfLen; i > 0; --i)
bitwriter.outputBit(0);
for (int i = lengthOfLen; i >= 0; --i)
bitwriter.outputBit((len >> i) & 1);
for (int i = len-2; i >= 0; i--)
bitwriter.outputBit((num >> i) & 1);
}
bitwriter.close();
}


### Decoding

void eliasDeltaDecode(char* source, char* dest)
{
IntWriter intwriter(dest);
{
int num = 1;
int len = 1;
int lengthOfLen = 0;
while (!bitreader.inputBit())     // potentially dangerous with malformed files.
lengthOfLen++;
for (int i = 0; i < lengthOfLen; i++)
{
len <<= 1;
len |= 1;
}
for (int i = 0; i < len-1; i++)
{
num <<= 1;
num |= 1;
}
intwriter.putInt(num);            // write out the value
}