Косая двоичная система счисления - Skew binary number system - Wikipedia

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

Примеры

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

Десятичный	Искаженный двоичный файл	двоичный
0	0	0
1	1	1
2	2	10
3	10	11
4	11	100
5	12	101
6	20	110
7	100	111
8	101	1000
9	102	1001
10	110	1010
11	111	1011
12	112	1100
13	120	1101
14	200	1110
15	1000	1111

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

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

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

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

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

Косое двоичное число вида ${ displaystyle b_ {0} dots b_ {n}}$ без 2 и с ${ displaystyle m}$ 1s равно двоичному числу ${ 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}$ 1s равно двоичному числу ${ displaystyle 0 ^ {c_ {0} + c_ {1} +2} 1b_ {0} dots b_ {n}}$ минус ${ displaystyle m}$ .

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

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

Приложения

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

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

Примечания

^ Слоан, Н. Дж. А. (ред.). «Последовательность A169683». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
^ Элмасри, Амр; Дженсен, Клаус; Катаянен, Юрки (2012). «Две косо-двоичные системы счисления и одно приложение» (PDF). Теория вычислительных систем. 50: 185–211. Дои:10.1007 / s00224-011-9357-0.
^ Майерс, Юджин В. (1983). «Аппликативный стек произвольного доступа». Письма об обработке информации. 17 (5): 241–248. Дои:10.1016/0020-0190(83)90106-0. МИСТЕР 0741239.
^ Бродал, Герт Стёльтинг; Окасаки, Крис (ноябрь 1996 г.). «Оптимальные чисто функциональные приоритетные очереди». Журнал функционального программирования. 6 (6): 839–857. Дои:10.1017 / s095679680000201x.

[1] Слоан, Н. Дж. А. (ред.). «Последовательность A169683». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.

[2] Элмасри, Амр; Дженсен, Клаус; Катаянен, Юрки (2012). «Две косо-двоичные системы счисления и одно приложение» (PDF). Теория вычислительных систем. 50: 185–211. Дои:10.1007 / s00224-011-9357-0.

[3] Майерс, Юджин В. (1983). «Аппликативный стек произвольного доступа». Письма об обработке информации. 17 (5): 241–248. Дои:10.1016/0020-0190(83)90106-0. МИСТЕР 0741239.

[4] Бродал, Герт Стёльтинг; Окасаки, Крис (ноябрь 1996 г.). «Оптимальные чисто функциональные приоритетные очереди». Журнал функционального программирования. 6 (6): 839–857. Дои:10.1017 / s095679680000201x.

[1]

[2]

[3]

[4]