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
```

RSS feed available here; new posts are also linked on my twitter.

Unless otherwise specified on individual pages, all posts on this website are licensed under the CC_-1 license.

This site lives at `https://carado.moe`

and `/ipns/k51qzi5uqu5di8qtoflxvwoza3hm88f5osoogsv4ulmhurge2etp9d37gb6qe9`

.