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. 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.
Conversion between decimal and skew binary number To convert from decimal to skew binary number, one can use the following formula:
Base case: a(0) = 0
Induction case: a(2^n-1+i) = a(i) + 10^{n-1}
Boundaries: 0 \le i \le 2^n-1,n \ge 1 To convert from skew binary number to decimal, one can use the definition of a skew binary number: S = \sum_{i = 0}^N b_i(2^{i+1}-1) , where b_i \in {0,1,2} , st. only least significant bit (lsb) b_{lsb} is 2.
C++ code to convert decimal number to skew binary number • include • include • include • include using namespace std; long dp[10000]; //Using formula a(0) = 0; for n >= 1, a(2^n-1+i) = a(i) + 10^(n-1) for 0
C++ code to convert skew binary number to decimal number • include • include using namespace std; // Decimal = (0|1|2)*(2^N+1 -1) + (0|1|2)*(2^(N-1)+1 -1) + ... // + (0|1|2)*(2^(1+1) -1) + (0|1|2)*(2^(0+1) -1) // // Expected input: A positive integer/long where digits are 0,1 or 2, s.t only least significant nonzero bit/digit is 2. // long convertToDecimal(long skewBinary){ int k = 0; long decimal = 0; while(skewBinary > 0){ int digit = skewBinary % 10; skewBinary = ceil(skewBinary/10); decimal += (pow(2,k+1)-1)*digit; k++; } return decimal; } int main() { int test[] = {0,1,2,10,11,12,20,100,101,102,110,111,112,120,200,1000}; for(int i = 0; i
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 2^{n+1}-1 and adding it once or twice for each n such that the nth 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 b_0\dots b_n without 2 and with m 1s is equal to the binary number 0b_0\dots b_n minus m. Let d^{c} represents the digit d repeated c times. The skew binary number of the form 0^{c_0}21^{c_1}0b_0\dots b_n with m 1s is equal to the binary number 0^{c_0+c_1+2}1b_0\dots b_n minus m.
From binary representation to skew binary representation Similarly to the preceding section, the binary number b of the form b_0\dots b_n with m 1s equals the skew binary number b_1\dots b_n plus m. Note that since addition is not defined, adding m corresponds to incrementing the number m times. However, m is bounded by the
logarithm of b 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==