Skew binary number system

<h2 id="examples">Examples</h2>
<p>Canonical skew binary representations of the numbers from 0 to 15 are shown in following table:<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
</p>
<table><tbody><tr><th>Decimal</th><th>Binary</th><th>Skew Binary</th><th>Ternary</th></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>2</td><td>10</td><td>2</td><td>2</td></tr><tr><td>3</td><td>11</td><td>10</td><td>10</td></tr><tr><td>4</td><td>100</td><td>11</td><td>11</td></tr><tr><td>5</td><td>101</td><td>12</td><td>12</td></tr><tr><td>6</td><td>110</td><td>20</td><td>20</td></tr><tr><td>7</td><td>111</td><td>100</td><td>21</td></tr><tr><td>8</td><td>1000</td><td>101</td><td>22</td></tr><tr><td>9</td><td>1001</td><td>102</td><td>100</td></tr><tr><td>10</td><td>1010</td><td>110</td><td>101</td></tr><tr><td>11</td><td>1011</td><td>111</td><td>102</td></tr><tr><td>12</td><td>1100</td><td>112</td><td>110</td></tr><tr><td>13</td><td>1101</td><td>120</td><td>111</td></tr><tr><td>14</td><td>1110</td><td>200</td><td>112</td></tr><tr><td>15</td><td>1111</td><td>1000</td><td>120</td></tr></tbody></table>
<h2 id="arithmetical-operations">Arithmetical operations</h2>
<p>The advantage of skew binary is that each increment operation can be done with at most one <a href="/facts/Carry_(arithmetic)/W5K5D2ju">carry</a> operation. This exploits the fact that 
  
    
      
        2
        (
        
          2
          
            n
            +
            1
          
        
        −
        1
        )
        +
        1
        =
        
          2
          
            n
            +
            2
          
        
        −
        1
      
    
    {\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 <a href="/facts/Run-length_encoding/3k6x9afM">run-length encoding</a> as linked lists of the non-zero digits, incrementation and decrementation can be performed in constant time.
</p><p>Other arithmetic operations may be performed by switching between the skew binary representation and the binary representation.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p>
<h3>Conversion between decimal and skew binary number</h3>
<p>To convert from decimal to skew binary number, one can use following formula:<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p><p>Base case: 
  
    
      
        a
        (
        0
        )
        =
        0
      
    
    {\displaystyle a(0)=0}
  
 
</p><p>Induction case: 
  
    
      
        a
        (
        
          2
          
            n
          
        
        −
        1
        +
        i
        )
        =
        a
        (
        i
        )
        +
        
          10
          
            n
            −
            1
          
        
      
    
    {\displaystyle a(2^{n}-1+i)=a(i)+10^{n-1}}
  
 
</p><p>Boundaries: 
  
    
      
        0
        ≤
        i
        ≤
        
          2
          
            n
          
        
        −
        1
        ,
        n
        ≥
        1
      
    
    {\displaystyle 0\leq i\leq 2^{n}-1,n\geq 1}

</p><p>
To convert from skew binary number to decimal, one can use definition of skew binary number:
</p><p>
  
    
      
        S
        =
        
          ∑
          
            i
            =
            0
          
          
            N
          
        
        
          b
          
            i
          
        
        (
        
          2
          
            i
            +
            1
          
        
        −
        1
        )
      
    
    {\displaystyle S=\sum _{i=0}^{N}b_{i}(2^{i+1}-1)}
  
, where 
  
    
      
        
          b
          
            i
          
        
        ∈
        
          0
          ,
          1
          ,
          2
        
      
    
    {\displaystyle b_{i}\in {0,1,2}}
  
, st. only least significant bit (lsb)  
  
    
      
        
          b
          
            l
            s
            b
          
        
      
    
    {\displaystyle b_{lsb}}
  
 is 2.
</p>
<h4>C++ code to convert decimal number to skew binary number</h4>
#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;
}

<h4>C++ code to convert skew binary number to decimal number</h4>
#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;
}

<h3>From skew binary representation to binary representation</h3>
<p>Given a skew binary number, its value can be computed by a loop, computing the successive values of 
  
    
      
        
          2
          
            n
            +
            1
          
        
        −
        1
      
    
    {\displaystyle 2^{n+1}-1}
  
 and adding it once or twice for each 
  
    
      
        n
      
    
    {\displaystyle n}
  
 such that the 
  
    
      
        n
      
    
    {\displaystyle n}
  
th digit is 1 or 2 respectively. A more efficient method is now given, with only bit representation and one subtraction.
</p><p>The skew binary number of the form 
  
    
      
        
          b
          
            0
          
        
        …
        
          b
          
            n
          
        
      
    
    {\displaystyle b_{0}\dots b_{n}}
  
 without 2 and with 
  
    
      
        m
      
    
    {\displaystyle m}
  
 1s is equal to the binary number 
  
    
      
        0
        
          b
          
            0
          
        
        …
        
          b
          
            n
          
        
      
    
    {\displaystyle 0b_{0}\dots b_{n}}
  
 minus 
  
    
      
        m
      
    
    {\displaystyle m}
  
. Let 
  
    
      
        
          d
          
            c
          
        
      
    
    {\displaystyle d^{c}}
  
 represents the digit 
  
    
      
        d
      
    
    {\displaystyle d}
  
 repeated 
  
    
      
        c
      
    
    {\displaystyle c}
  
 times. The skew binary number of the form 
  
    
      
        
          0
          
            
              c
              
                0
              
            
          
        
        
          21
          
            
              c
              
                1
              
            
          
        
        0
        
          b
          
            0
          
        
        …
        
          b
          
            n
          
        
      
    
    {\displaystyle 0^{c_{0}}21^{c_{1}}0b_{0}\dots b_{n}}
  
 with 
  
    
      
        m
      
    
    {\displaystyle m}
  
 1s is equal to the binary number 
  
    
      
        
          0
          
            
              c
              
                0
              
            
            +
            
              c
              
                1
              
            
            +
            2
          
        
        1
        
          b
          
            0
          
        
        …
        
          b
          
            n
          
        
      
    
    {\displaystyle 0^{c_{0}+c_{1}+2}1b_{0}\dots b_{n}}
  
 minus 
  
    
      
        m
      
    
    {\displaystyle m}
  
.
</p>
<h3>From binary representation to skew binary representation</h3>
<p>Similarly to the preceding section, the binary number 
  
    
      
        b
      
    
    {\displaystyle b}
  
 of the form 
  
    
      
        
          b
          
            0
          
        
        …
        
          b
          
            n
          
        
      
    
    {\displaystyle b_{0}\dots b_{n}}
  
 with 
  
    
      
        m
      
    
    {\displaystyle m}
  
 1s equals the skew binary number 
  
    
      
        
          b
          
            1
          
        
        …
        
          b
          
            n
          
        
      
    
    {\displaystyle b_{1}\dots b_{n}}
  
 plus 
  
    
      
        m
      
    
    {\displaystyle m}
  
. Note that since addition is not defined, adding 
  
    
      
        m
      
    
    {\displaystyle m}
  
 corresponds to incrementing the number 
  
    
      
        m
      
    
    {\displaystyle m}
  
 times. However, 
  
    
      
        m
      
    
    {\displaystyle m}
  
 is bounded by the logarithm of 
  
    
      
        b
      
    
    {\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.
</p>
<h2 id="applications">Applications</h2>
<p>The skew binary numbers were developed by <a href="/facts/Eugene_Myers/pEx2R23d">Eugene Myers</a> in 1983 for a <a href="/facts/Purely_functional_data_structure/sV5TBGqB">purely functional data structure</a> that allows the operations of the <a href="/facts/Stack_(abstract_data_type)/bj7l94v1">stack abstract data type</a> and also allows efficient indexing into the sequence of stack elements.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> They were later applied to <a href="/facts/Skew_binomial_heap/EyPN11JM">skew binomial heaps</a>, a variant of <a href="/facts/Binomial_heap/SE1G15Ao">binomial heaps</a> that support constant-time worst-case insertion operations.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Three-valued_logic/k4vMkwRL">Three-valued logic</a></li>
<li><a href="/facts/Redundant_binary_representation/R6kcefzo">Redundant binary representation</a></li>
<li><a href="/facts/Gray_code/HtbVlM7T">n-ary Gray code</a></li></ul>
<h2 id="notes">Notes</h2>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Sloane, N. J. A. (ed.). "Sequence A169683". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. <a href="/wiki/Neil_Sloane" target="_blank">/wiki/Neil_Sloane</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>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. <a href="http://www.cphstl.dk/Paper/TOCS-2011/journal.pdf" target="_blank">http://www.cphstl.dk/Paper/TOCS-2011/journal.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>The Online Encyclopedia of Integer Sequences. "The canonical skew-binary numbers". <a href="https://oeis.org/A169683" target="_blank">https://oeis.org/A169683</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>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. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>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. <a href="https://doi.org/10.1017%2Fs095679680000201x" target="_blank">https://doi.org/10.1017%2Fs095679680000201x</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
</ol>

Skew binary number system open-in-new

Skew binary number system