skew binary number system

Canonical skew binary representations of the numbers from 0 to 15 are shown in following table:{{cite OEIS|A169683}}

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.{{cite journal|last1=Elmasry|first1=Amr|last2=Jensen|first2=Claus|last3=Katajainen|first3=Jyrki|title=Two Skew-Binary Numeral Systems and One Application|journal=Theory of Computing Systems|date=2012|volume=50|pages=185–211|doi=10.1007/s00224-011-9357-0|s2cid=253736860 |url=http://www.cphstl.dk/Paper/TOCS-2011/journal.pdf}}

To convert from decimal to skew binary number, one can use following formula:{{cite web |author=The Online Encyclopedia of Integer Sequences |title=The canonical skew-binary numbers |url=https://oeis.org/A169683}}

Base case: $a(0)\; =\; 0$

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

Boundaries: $0\; \backslash le\; i\; \backslash le\; 2^n-1,n\; \backslash ge\; 1$

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

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

1. include
2. include
3. include
4. 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 <= 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;

}

1. include
2. 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 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;

}

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\backslash dots\; b\_n$ without 2 and with $m$ 1s is equal to the binary number $0b\_0\backslash 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\backslash dots\; b\_n$ with $m$ 1s is equal to the binary number $0^\{c\_0+c\_1+2\}1b\_0\backslash dots\; b\_n$ minus $m$.

Similarly to the preceding section, the binary number $b$ of the form $b\_0\backslash dots\; b\_n$ with $m$ 1s equals the skew binary number $b\_1\backslash 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.

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.{{cite journal

| last = Myers | first = Eugene W.

| doi = 10.1016/0020-0190(83)90106-0

| issue = 5

| journal = Information Processing Letters

| mr = 741239

| pages = 241–248

| title = An applicative random-access stack

| volume = 17

| year = 1983}} They were later applied to skew binomial heaps, a variant of binomial heaps that support constant-time worst-case insertion operations.{{cite journal

| last1 = Brodal | first1 = Gerth Stølting

| last2 = Okasaki | first2 = Chris

| date = November 1996

| doi = 10.1017/s095679680000201x

| issue = 6

| journal = Journal of Functional Programming

| pages = 839–857

| title = Optimal purely functional priority queues

| volume = 6| doi-access = free

}}

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

{{reflist}}

Category:Number theory

Category:Functional programming

Category:Computer arithmetic

Category:Non-standard positional numeral systems