carado.moe

tammy's blog about
AI alignment, utopia, anthropics, and more;

also on twitter, lesswrong, rss, and at

A canonical bit-encoding for ranged integers

in an earlier post i describe a scheme to canonically and efficient encode integers that span over a power-of-two range. in this post i'll be describing a scheme to encode (positive) integers within a non-power-of-two range; but in bits rather than bytes.

this problem cannot in general be solved for byte-encoding: one by definition cannot make a bijection between the 256 possible values of 1 byte and a set of under 256 values.

here is the scheme to encode a number i in the range between 0 and n:

• if n = 2^k-1, the range has a power of two number of values, and is simply encoded over k bits.
• otherwise,
  • let k be the highest integer such that 2^k < n.
  • the first n - 2^k values are mapped to 0 followed by the encoding of i over the range from 0 to n := n - 2^k
  • the last 2^k values are mapped to 1 followed by k bits

as an example, here's the encoding of all numbers within some ranges (with spaces inserted merely for readability)

• numbers between 0 and 3

0: 00
1: 01
2: 10
3: 11

• numbers between 0 and 4

0: 0
1: 1 00
2: 1 01
3: 1 10
4: 1 11

• numbers between 0 and 5

0: 0 0
1: 0 1
2: 1 00
3: 1 01
4: 1 10
5: 1 11

• numbers between 0 and 6

0: 0 0
1: 0 10
2: 0 11
3: 1 00
4: 1 01
5: 1 10
6: 1 11

• numbers between 0 and 7

0: 000
1: 001
2: 010
3: 011
4: 100
5: 101
6: 110
7: 111

• numbers between 0 and 14

 0: 0 0 0
 1: 0 0 10
 2: 0 0 11
 3: 0 1 00
 4: 0 1 01
 5: 0 1 10
 6: 0 1 11
 7: 1 000
 8: 1 001
 9: 1 010
10: 1 011
11: 1 100
12: 1 101
13: 1 110
14: 1 111