Косая двоичная система счисления

Косая двоичная система счисления — это нестандартная позиционная система счисления , в которой n -я цифра имеет значение $2^{n+1}-1$ умножить цифру (цифры индексируются с 0) вместо $2^{n}$ раз, как в двоичном формате . Каждая цифра имеет значение 0, 1 или 2. Число может иметь множество искаженных двоичных представлений. Например, десятичное число 15 может быть записано как 1000, 201 и 122. Каждое число может быть записано однозначно в косой двоичной канонической форме, где существует не более одного экземпляра цифры 2, которая должна быть младшей значащей ненулевой цифрой. В данном случае 15 канонически записывается как 1000.

Примеры

Канонические асимметричные двоичные представления чисел от 0 до 15 показаны в следующей таблице:

Десятичный	Двоичный	Перекос двоичного файла	тройной
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

Арифметические операции

Преимущество асимметричного двоичного кода заключается в том, что каждую операцию приращения можно выполнить не более чем с одной операцией переноса . Это использует тот факт, что $2(2^{n+1}-1)+1=2^{n+2}-1$. Увеличение асимметричного двоичного числа осуществляется путем установки только двух цифр на ноль и увеличения следующей цифры от нуля до единицы или от единицы до двух. Когда числа представлены с использованием формы кодирования длин серий в виде связанных списков ненулевых цифр, приращение и уменьшение могут выполняться за постоянное время.

Другие арифметические операции могут выполняться путем переключения между асимметричным двоичным представлением и двоичным представлением.

Преобразование десятичных и асимметричных двоичных чисел

Чтобы преобразовать десятичное число в асимметричное двоичное число, можно использовать следующую формулу:

Базовый случай : $a(0)=0$

Индукционный случай : $a(2^{n}-1+i)=a(i)+10^{n-1}$

Границы : $0\leq i\leq 2^{n}-1,n\geq 1$

Чтобы преобразовать асимметричное двоичное число в десятичное, можно использовать определение асимметричного двоичного числа:

$S=\sum _{i=0}^{N}b_{i}(2^{i+1}-1)$, где $b_{i}\in {0,1,2}$, ул. только младший бит (LSB) $b_{lsb}$ это 2.

Код C++ для преобразования десятичного числа в искаженное двоичное число

#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++ для преобразования асимметричного двоичного числа в десятичное число

#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;
}

От асимметричного двоичного представления к двоичному представлению

Учитывая асимметричное двоичное число, его значение можно вычислить с помощью цикла, вычисляя последовательные значения $2^{n+1}-1$ и добавляя его один или два раза для каждого $n$ такой, что $n$1-я цифра — 1 или 2 соответственно. Теперь дан более эффективный метод, использующий только битовое представление и одно вычитание.

Косое двоичное число вида $b_{0}\dots b_{n}$ без 2 и с $m$ 1с равно двоичному числу $0b_{0}\dots b_{n}$ минус $m$. Позволять $d^{c}$ представляет цифру $d$ повторенный $c$ раз. Косое двоичное число вида $0^{c_{0}}21^{c_{1}}0b_{0}\dots b_{n}$ с $m$ 1с равно двоичному числу $0^{c_{0}+c_{1}+2}1b_{0}\dots b_{n}$ минус $m$.

От двоичного представления к искаженному двоичному представлению

Как и в предыдущем разделе, двоичное число $b$ формы $b_{0}\dots b_{n}$ с $m$ 1 с соответствует асимметричному двоичному числу $b_{1}\dots b_{n}$ плюс $m$. Обратите внимание: поскольку сложение не определено, добавление $m$ соответствует увеличению числа $m$ раз. Однако, $m$ ограничен логарифмом $b$ и приращение занимает постоянное время. Следовательно, преобразование двоичного числа в косое двоичное число происходит во времени, линейном по длине числа.

Приложения

Асимметричные двоичные числа были разработаны Юджином Майерсом в 1983 году для чисто функциональной структуры данных , которая позволяет выполнять операции абстрактного типа данных стека , а также обеспечивает эффективную индексацию последовательности элементов стека. Позже они были применены для перекоса биномиальных куч — варианта биномиальных куч , который поддерживает операции вставки в худшем случае с постоянным временем.

См. также

• Трехзначная логика
• Избыточное двоичное представление
• n-арный код Грея