Skew binary number system

The skew binary number system is a non-standard positional numeral system in which the nth digit has a value of $2^{n+1} - 1$ and each digit has a value of 0, 1, or 2. Each number can be written uniquely in skew binary canonical form where there is only at most one instance of the digit 2, which must be the first non-zero least significant digit, as shown in following table:

Decimal	Skew binary	binary
0	0	0
1	1	1
2	2	10
3	10	11
4	11	100
5	12	101
6	20	110
7	100	111
8	101	1000
9	102	1001
10	110	1010
11	111	1011
12	112	1100
13	120	1101
14	200	1110
15	1000	1111

The advantage of skew binary is that each increment operation can be done with at most one carry operation. This exploits the fact that $2 (2^{n+1} - 1) + 1 = 2^{n+2} - 1$. Incrementing a skew binary number is done by setting the only two to a zero and incrementing the next digit from zero to one or one to two.^[1]

Skew binary numbers find applications in skew binomial heaps, a variant of binomial heaps that support worst-case O(1) insertion, and in skew binary random access lists, a purely functional data structure. They also find use in bootstrapped skew binomial heaps, which have excellent asymptotic guarantees.^[2]

See also

• Three-valued logic
• Redundant binary representation
• n-ary Gray code

Notes

1. skew binary numbers
2. Okasaki, Chris. Purely Functional Data Structures.