Skew binary number system

The skew binary number system is a non-standard positional numeral system in which the nth digit contributes a value of $2^{n+1}-1$ times the digit (digits are indexed from 0) instead of $2^{n}$ times as they do in binary. Each digit has a value of 0, 1, or 2. A number can have many skew binary representations. For example, a decimal number 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 least significant nonzero 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:[1]

Decimal	Binary	Skew Binary	Ternary
0	0	0	0
1	1	1	1
2	10	2	2
3	11	10	10
4	100	11	11
5	101	12	12
6	110	20	20
7	111	100	21
8	1000	101	22
9	1001	102	100
10	1010	110	101
11	1011	111	102
12	1100	112	110
13	1101	120	111
14	1110	200	112
15	1111	1000	120

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 $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

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

Base case: $a(0)=0$

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

Boundaries: $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:

$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 <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

#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

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 $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 $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

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]

Notes

Sloane, N. J. A. (ed.). "Sequence A169683". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
Elmasry, Amr; Jensen, Claus; Katajainen, Jyrki (2012). "Two Skew-Binary Numeral Systems and One Application" (PDF). Theory of Computing Systems. 50: 185–211. doi:10.1007/s00224-011-9357-0. S2CID 253736860.
The Online Encyclopedia of Integer Sequences. "The canonical skew-binary numbers".
Myers, Eugene W. (1983). "An applicative random-access stack". Information Processing Letters. 17 (5): 241–248. doi:10.1016/0020-0190(83)90106-0. MR 0741239.
Brodal, Gerth Stølting; Okasaki, Chris (November 1996). "Optimal purely functional priority queues". Journal of Functional Programming. 6 (6): 839–857. doi:10.1017/s095679680000201x.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Sloane, N. J. A. (ed.). "Sequence A169683". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[2] Elmasry, Amr; Jensen, Claus; Katajainen, Jyrki (2012). "Two Skew-Binary Numeral Systems and One Application" (PDF). Theory of Computing Systems. 50: 185–211. doi:10.1007/s00224-011-9357-0. S2CID 253736860.

[3] The Online Encyclopedia of Integer Sequences. "The canonical skew-binary numbers".

[4] Myers, Eugene W. (1983). "An applicative random-access stack". Information Processing Letters. 17 (5): 241–248. doi:10.1016/0020-0190(83)90106-0. MR 0741239.

[5] Brodal, Gerth Stølting; Okasaki, Chris (November 1996). "Optimal purely functional priority queues". Journal of Functional Programming. 6 (6): 839–857. doi:10.1017/s095679680000201x.