The skew binary number system is a non-standard positional numeral system in which the nth digit contributes a value of times the digit instead of times as they do in binary. Each digit has a value of 0, 1, or 2. Notice that a number can have many skew binary representations. For example, a decimalnumber 15 can be written as 1000, 201 and 122. 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. In this case 15 is written canonically as 1000.
Examples
Canonical skew binary representations of the numbers from 0 to 15 are 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
Arithmetical operations
The advantage of skew binary is that each increment operation can be done with at most one carry operation. This exploits the fact that. 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. When numbers are represented using a form of run-length encoding as linked lists of the non-zero digits, incrementation and decrementation can be performed in constant time. Other arithmetic operations may be performed by switching between the skew binary representation and the binary representation.
From skew binary representation to binary representation
Given a skew binary number, its value can be computed by a loop, computing the successive values of and adding it once or twice for each such that the th digit is 1 or 2 respectively. A more efficient method is now given, with only bit representation and one subtraction. The skew binary number of the form without 2 and with 1s is equal to the binary number minus. Let represents the digit repeated times. The skew binary number of the form with 1s is equal to the binary number minus.
From binary representation to skew binary representation
Similarly to the preceding section, the binary number of the form with 1s equals the skew binary number plus. Note that since addition is not defined, adding corresponds to incrementing the number times. However, is bounded by the logarithm of and incrementation takes constant time. Hence transforming a binary number into a skew binary number runs in time linear in the length of the number.
Applications
The skew binary numbers were developed by Eugene Myers in 1983 for a purely functional data structure that allows the operations of the stack abstract data type and also allows efficient indexing into the sequence of stack elements. They were later applied to skew binomial heaps, a variant of binomial heaps that support constant-time worst-case insertion operations.
