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 = 0, i must be 0, and no bits of encoding are needed.
- if n = 2
^{k}-1, the range has a power of two number of values, and is simply encoded over k bits. - if n = 2, as a special case, the following mapping applies:
- 0 maps to 0
- 1 maps to 10
- 2 maps to 11

- 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

- let k be the highest integer such that 2

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

Unless otherwise specified on individual pages, all posts on this website are licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.