avatar

posted on 2021-01-14

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:

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

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

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

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

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

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

 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

posted on 2021-01-14

CC_ -1 License unless otherwise specified on individual pages, all posts on this website are licensed under the CC_-1 license.
unless explicitely mentioned, all content on this site was created by me; not by others nor AI.