Перекос система двоичного числа является нестандартной позиционной системой счисления , в которой п й разряд способствует значению умножить на цифру (цифры индексируются от 0) вместо раз, как в двоичном формате . Каждая цифра имеет значение 0, 1 или 2. Число может иметь много искаженных двоичных представлений. Например, десятичное число 15 может быть записано как 1000, 201 и 122. Каждое число может быть записано однозначно в косой двоичной канонической форме, где имеется не более одного экземпляра цифры 2, которая должна быть наименьшей значащей ненулевой цифрой. В этом случае 15 канонически записывается как 1000.
Примеры
Канонические косые двоичные представления чисел от 0 до 15 показаны в следующей таблице: [1]
Десятичный | Двоичный | Искаженный двоичный файл | Тернарный |
---|---|---|---|
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]
От перекоса двоичного представления к двоичному представлению
Учитывая перекос двоичного числа, его значение может быть вычислено с помощью цикла, вычисляя последовательные значения и добавляя один или два раза для каждого так что -я цифра - 1 или 2 соответственно. Теперь дается более эффективный метод, только с битовым представлением и одним вычитанием.
Косое двоичное число вида без 2 и с 1s равно двоичному числу минус . Позволять представляет цифру повторяется раз. Косое двоичное число вида с участием 1s равно двоичному числу минус .
От двоичного представления к перекосу двоичного представления
Как и в предыдущем разделе, двоичное число формы с участием 1s равно наклонному двоичному числу плюс . Обратите внимание: поскольку сложение не определено, добавление соответствует увеличению числа раз. Тем не мение, ограничено логарифмом и приращение занимает постоянное время. Следовательно, преобразование двоичного числа в искаженное двоичное число происходит во времени линейно по длине числа.
Приложения
Косые двоичные числа были разработаны Юджином Майерсом в 1983 году для чисто функциональной структуры данных, которая позволяет выполнять операции с абстрактным типом данных стека, а также позволяет эффективно индексировать последовательность элементов стека. [3] Позже они были применены для косой биномиальной кучи , разновидности биномиальной кучи, которая поддерживает операции вставки в наихудшем случае с постоянным временем. [4]
Смотрите также
Заметки
- ^ Слоан, Н. Дж. А. (ред.). «Последовательность A169683» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS.
- ^ Элмасри, Амр; Дженсен, Клаус; Катаянен, Юрки (2012). «Две косо-двоичные системы счисления и одно приложение» (PDF) . Теория вычислительных систем . 50 : 185–211. DOI : 10.1007 / s00224-011-9357-0 .
- ^ Майерс, Юджин В. (1983). «Аппликативный стек произвольного доступа». Письма об обработке информации . 17 (5): 241–248. DOI : 10.1016 / 0020-0190 (83) 90106-0 . Руководство по ремонту 0741239 .
- ^ Бродал, Герт Стёльтинг; Окасаки, Крис (ноябрь 1996 г.). «Оптимальные чисто функциональные приоритетные очереди». Журнал функционального программирования . 6 (6): 839–857. DOI : 10,1017 / s095679680000201x .