Editing Elias delta coding (section)

== Encoding ==
To code a number ''X''&nbsp;≥ 1:
# Let ''N''&nbsp;= ⌊log<sub>2</sub> ''X''⌋; be the highest power of 2 in ''X'', so 2<sup>''N''</sup> ≤ ''X'' < 2<sup>''N''+1</sup>.
# Let ''L''&nbsp;= ⌊log<sub>2</sub> ''N''+1⌋ be the highest power of 2 in ''N''+1, so 2<sup>''L''</sup> ≤ ''N''+1 < 2<sup>''L''+1</sup>.
# Write ''L'' zeros, followed by
# the ''L''+1-bit binary representation of ''N''+1, followed by
# all but the leading bit (i.e. the last ''N'' bits) of ''X''.

An equivalent way to express the same process:
#Separate ''X'' into the highest power of 2 it contains (2<sup>''N''</sup>) and the remaining ''N'' binary digits.
#Encode ''N''+1 with [[Elias gamma coding]].
#Append the remaining ''N'' binary digits to this representation of ''N''+1.

To represent a number <math>x</math>, Elias delta (δ) uses <math>\lfloor \log_2(x) \rfloor  + 2 \lfloor \log_2 (\lfloor \log_2(x) \rfloor +1) \rfloor + 1</math> bits.<ref name="Elias"/>{{rp|200}}
This is useful for very large integers, where the overall encoded representation's bits end up being fewer [than what one might obtain using [[Elias gamma coding]]] due to the <math>\log_2 (\lfloor \log_2(x) \rfloor +1)</math> portion of the previous expression.

The code begins, using <math>\gamma'</math> instead of <math>\gamma</math>:

{| class="wikitable"
! Number !! N !! N+1 !! δ encoding !! Implied probability
|-
| 1 = 2<sup>0</sup> || 0 || 1 || <code>1</code> || 1/2
|-
|colspan=5|
|-
| 2 = 2<sup>1</sup> + ''0'' || 1 || 2 || <code>0&thinsp;1&thinsp;0 ''0''</code> || 1/16
|-
| 3 = 2<sup>1</sup> + ''1'' || 1 || 2 || <code>0&thinsp;1&thinsp;0 ''1''</code> || 1/16
|-
|colspan=5|
|-
| 4 = 2<sup>2</sup> + ''0'' || 2 || 3 || <code>0&thinsp;1&thinsp;1 ''00''</code> || 1/32
|-
| 5 = 2<sup>2</sup> + ''1'' || 2 || 3 || <code>0&thinsp;1&thinsp;1 ''01''</code> || 1/32
|-
| 6 = 2<sup>2</sup> + ''2'' || 2 || 3 || <code>0&thinsp;1&thinsp;1 ''10''</code> || 1/32
|-
| 7 = 2<sup>2</sup> + ''3'' || 2 || 3 || <code>0&thinsp;1&thinsp;1 ''11''</code> || 1/32
|-
|colspan=5|
|-
| 8 = 2<sup>3</sup> + ''0'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''000''</code> || 1/256
|-
| 9 = 2<sup>3</sup> + ''1'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''001''</code> || 1/256
|-
| 10 = 2<sup>3</sup> + ''2'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''010''</code> || 1/256
|-
| 11 = 2<sup>3</sup> + ''3'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''011''</code> || 1/256
|-
| 12 = 2<sup>3</sup> + ''4'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''100''</code> || 1/256
|-
| 13 = 2<sup>3</sup> + ''5'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''101''</code> || 1/256
|-
| 14 = 2<sup>3</sup> + ''6'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''110''</code> || 1/256
|-
| 15 = 2<sup>3</sup> + ''7'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''111''</code> || 1/256
|-
|colspan=5|
|-
| 16 = 2<sup>4</sup> + ''0'' || 4 || 5 || <code>00&thinsp;1&thinsp;01 ''0000''</code> || 1/512
|-
| 17&nbsp;=&nbsp;2<sup>4</sup>&nbsp;+&nbsp;''1'' || 4 || 5 || {{nowrap|<code>00&thinsp;1&thinsp;01 ''0001''</code>}} || 1/512
|}

To decode an Elias delta-coded integer:
#Read and count zeros from the stream until you reach the first one.  Call this count of zeros ''L''.
#Considering the one that was reached to be the first digit of an integer, with a value of 2<sup>''L''</sup>, read the remaining ''L'' digits of the integer.  Call this integer ''N''+1, and subtract one to get ''N''.
#Put a one in the first place of our final output, representing the value 2<sup>''N''</sup>.
#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 = 2<sup>4</sup> + 3 = 19

This code can be generalized to zero or negative integers in the same ways described in [[Elias gamma coding#Generalizations|Elias gamma coding]].