Skew binary number system

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 could be made by exploiting the fact that 2 (2^{n+1} - 1) + 1 = 2^{n+2} - 1 . This means we can simply increment the skew binary number that contains a two by setting it 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[edit]

Notes[edit]

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