Перекошенная двоичная система счисления

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

Примеры

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

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

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

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

Преобразование между десятичным и перекошенным двоичным числом

Для преобразования десятичного числа в перекошенное двоичное число можно использовать следующую формулу: ^[3]

Базовый вариант : ${\displaystyle a(0)=0}$

Случай индукции : ${\displaystyle a(2^{n}-1+i)=a(i)+10^{n-1}}$

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

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

${\displaystyle S=\sum _{i=0}^{N}b_{i}(2^{i+1}-1)}$, где , единственный младший бит (lsb) равен 2. ${\displaystyle b_{i}\in {0,1,2}}$ ${\displaystyle b_{lsb}}$

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

#include <iostream> #include <cmath> #include <алгоритм> #include <итератор>    с использованием пространства имен std ;  длинный дп [ 10000 ]; //Используем формулу a(0) = 0; для n >= 1, a(2^n-1+i) = a(i) + 10^(n-1) для 0 <= i <= 2^n-1, //взято из The On-Line Encyclopedia of Integer Sequences (https://oeis.org/A169683)long convertToSkewbinary ( длинное десятичное ){   интервал МаксИндекс = 0 ; длинный макс = 1 ; while ( макс < десятичное число ) { макс *= 2 ; МаксИндекс ++ ; }                   для ( int j = 1 ; j <= maksIndex ; j ++ ) { long power = pow ( 2 , j ); для ( 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 ; //Можно сравнить с числами, приведенными в //https://oeis.org/A169683 for ( int i = 50 ; i < 125 ; i ++ ) { long current = convertToSkewbinary ( i ); cout << current << endl ; }                                вернуть 0 ; } 

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

#include <iostream> #include <cmath>  с использованием пространства имен std ;  // Десятичное число = (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) // // Ожидаемый ввод: положительное целое число/длинное число, где цифры — 0, 1 или 2, единственный младший бит/цифра — 2. // long convertToDecimal ( long skewBinary ){   int k = 0 ; длинное десятичное число = 0 ; while ( skewBinary > 0 ){ int цифра = skewBinary % 10 ; skewBinary = ceil ( skewBinary / 10 ); десятичное число += ( pow ( 2 , k + 1 ) -1 ) * цифра ; k ++ ; } return десятичное число ; } int main () {                              int тест [] = { 0 , 1 , 2 , 10 , 11 , 12 , 20 , 100 , 101 , 102 , 110 , 111 , 112 , 120 , 200 , 1000 };    для ( int i = 0 ; i < sizeof ( test ) / sizeof ( int ); i ++ ) cout << convertToDecimal ( test [ i ]) << endl ;;             вернуть 0 ; } 

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

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

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

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

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

Приложения

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

Смотрите также

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

Примечания

1. Sloane, N. J. A. (ред.). "Последовательность A169683". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
2. Элмасри, Амр; Йенсен, Клаус; Катаяйнен, Юрки (2012). «Две косо-двоичные системы счисления и одно приложение» (PDF) . Теория вычислительных систем . 50 : 185–211. doi :10.1007/s00224-011-9357-0. S2CID  253736860.
3. Онлайн-энциклопедия целочисленных последовательностей. «Канонические косо-двоичные числа».
4. Майерс, Юджин В. (1983). «Аппликативный стек случайного доступа». Information Processing Letters . 17 (5): 241–248. doi :10.1016/0020-0190(83)90106-0. MR  0741239.
5. Бродал, Герт Столтинг; Окасаки, Крис (ноябрь 1996 г.). «Оптимальные чисто функциональные очереди с приоритетами». Журнал функционального программирования . 6 (6): 839–857. doi : 10.1017/s095679680000201x .