Canonical skew binary representations of the numbers from 0 to 15 are shown in following table:^[1]

The advantage of skew binary is that each increment operation can be done with at most one carry operation. This exploits the fact that ${\displaystyle 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.^[2]

Convertion between decimal and skew binary number edit

To convert from decimal to skew binary number, one can use following formula:^[3]

Base case: ${\displaystyle a(0)=0}$ 

Induction case: ${\displaystyle a(2^{n}-1+i)=a(i)+10^{n-1}}$ 

Boundaries: ${\displaystyle 0\leq i\leq 2^{n}-1,n\geq 1}$ 

To convert from skew binary number to decimal, one can use definition of skew binary number:

${\displaystyle S=\sum _{i=0}^{N}b_{i}(2^{i+1}-1)}$ , where ${\displaystyle b_{i}\in {0,1,2}}$ , st. only least significant bit (lsb) ${\displaystyle b_{lsb}}$  is 2.

C++ code to convert decimal number to skew binary number edit

#include <iostream>
#include <cmath>
#include <algorithm>
#include <iterator>

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 <= i <= 2^n-1,
//taken from The On-Line Encyclopedia of Integer Sequences (https://oeis.org/A169683)

long convertToSkewbinary(long decimal){

 int maksIndex = 0;
 long maks = 1;
 
 while(maks < decimal){
     
     maks *= 2;
     maksIndex++;
 }
   

 for(int j = 1; j <= maksIndex; j++){
     long power = pow(2,j);
  
    for(int i = 0; i <= power-1; i++)
        dp[i + power-1] = pow(10,j-1) + dp[i];
 }

 
  return dp[decimal];
    
}
int main() {
    std::fill(std::begin(dp), std::end(dp), -1);
    dp[0] = 0;
    
    //One can compare with numbers given in
    //https://oeis.org/A169683
    for(int i = 50; i < 125; i++){
        long current = convertToSkewbinary(i);
        cout << current << endl;
    }

    
	return 0;
}

C++ code to convert skew binary number to decimal number edit

#include <iostream>
#include <cmath>


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 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 < sizeof(test)/sizeof(int); i++)
          cout << convertToDecimal(test[i]) << endl;;

    
	return 0;
}

From skew binary representation to binary representation edit

Given a skew binary number, its value can be computed by a loop, computing the successive values of ${\displaystyle 2^{n+1}-1}$  and adding it once or twice for each ${\displaystyle n}$  such that the ${\displaystyle n}$ 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 ${\displaystyle b_{0}\dots b_{n}}$  without 2 and with ${\displaystyle m}$  1s is equal to the binary number ${\displaystyle 0b_{0}\dots b_{n}}$  minus ${\displaystyle m}$ . Let ${\displaystyle d^{c}}$  represents the digit ${\displaystyle d}$  repeated ${\displaystyle c}$  times. The skew binary number of the form ${\displaystyle 0^{c_{0}}21^{c_{1}}0b_{0}\dots b_{n}}$  with ${\displaystyle m}$  1s is equal to the binary number ${\displaystyle 0^{c_{0}+c_{1}+2}1b_{0}\dots b_{n}}$  minus ${\displaystyle m}$ .

From binary representation to skew binary representation edit

Similarly to the preceding section, the binary number ${\displaystyle b}$  of the form ${\displaystyle b_{0}\dots b_{n}}$  with ${\displaystyle m}$  1s equals the skew binary number ${\displaystyle b_{1}\dots b_{n}}$  plus ${\displaystyle m}$ . Note that since addition is not defined, adding ${\displaystyle m}$  corresponds to incrementing the number ${\displaystyle m}$  times. However, ${\displaystyle m}$  is bounded by the logarithm of ${\displaystyle 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.

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.^[4] They were later applied to skew binomial heaps, a variant of binomial heaps that support constant-time worst-case insertion operations.^[5]

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