The skew binary number system is a non-standard positional numeral system in which the nth digit contributes a value of
Contents
Examples
Skew binary representations of the numbers from 0 to 15 are shown in following table:
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
Other arithmetic operations are 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
The skew binary number of the form
From binary representation to skew binary representation
Similarly to the preceding section, the binary number
Applications
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.
If smoothsort is implemented using perfect binary trees (rather than the more common Leonardo trees), the heap is divided into trees which correspond to the digits of the skew binary representation of the heap size.