Нега-позиционная система счисления

Системы счисления в культуре
Индо-арабская
Арабская Индийские Тамильская Бирманская	Кхмерская Лаосская Монгольская Тайская
Восточноазиатские
Китайская Японская Сучжоу Корейская	Вьетнамская Счётные палочки
Алфавитные
Абджадия Армянская Ариабхата Кириллическая	Греческая Эфиопская Еврейская Акшара-санкхья
Другие
Вавилонская Египетская Этрусская Римская	Аттическая Кипу Майская
Позиционные
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 24, 26, 27, 32, 36, 60
Нега-позиционная
Симметричная
Смешанные системы
Фибоначчиева
Непозиционные
Единичная (унарная)
Список систем счисления

Не́га-позицио́нная систе́ма счисле́ния — это позиционная система счисления с отрицательным основанием. Особенностью таких систем является отсутствие знака перед отрицательными числами и, следовательно, отсутствие правил знаков. Всякое число любой из нега-позиционных систем, отличное от $0$, с нечётным числом цифр — положительно, а с чётным числом цифр — отрицательно. Часто число в нега-позиционной системе требует для записи на одну цифру больше, чем то же число в системе с положительным основанием. Обычно название нега-позиционной системы состоит из префикса нега- и названия соответствующей системы счисления с положительным основанием; например, нега-десятичная (b = −10), нега-троичная (b = −3), нега-двоичная (b = −2) и другие.

Примеры

Нега-позиционная запись	Позиционная запись	Представление числа
174(-10)	34(10)	1·(-10)2 + 7·(-10)1 + 4·(-10)0 = 100 − 70 + 4 = 34
46(-10)	−34(10)	4·(-10)1 + 6·(-10)0 = −40 + 6 = −34
11001(-2)	1001(2)	1·(-2)4 + 1·(-2)3 + 0·(-2)2 + 0·(-2)1 + 1·(-2)0 = 16 − 8 + 1 = 9

История

Нега-позиционные системы счисления были впервые предложены Витторио Грюнвальдом в его работе «Giornale di Matematiche di Battaglini» 23 (стр 203-221), опубликованной в 1885 году. Грюнвальд описал алгоритмы сложения, вычитания, умножения, деления, извлечения корня, признаков делимости и преобразования систем счисления.

Использование

Число x в нега-позиционной системе счисления с основанием $b = -r$ представляется в виде линейной комбинации степеней числа $-r$:

$x = \sum_{k=0}^{n-1} a_k (-r)^k$, где $a_k$ — это целые числа, называемые цифрами и удовлетворяющие неравенству $0 \leq a_k < r$, $k$ - порядковый номер разряда начиная с нулевого, n - число разрядов.

Каждая степень $(-r)^k$ в такой записи называется разрядом, старшинство разрядов и соответствующих им цифр определяется значением показателя $k$. Обычно для ненулевого числа $x$ требуют, чтобы старшая цифра $a_{n-1}$ в b-ричном представлении $x$ была также ненулевой.

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

Некоторые числа обладают одним и тем же представлением в системах счисления с основанием $b$ и $-b$ (позиционных и соответствующим им нега-позиционных). К примеру, числа от 100 до 109 одинаково записываются в десятичной и нега-десятичных системах счисления. Аналогично:

$17 = 2^4+2^0 = (-2)^4+(-2)^0$

То есть число 17 имеет одинаковое представление в двоичной и нега-двоичной системах счисления — $10001$.

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

Десятичное	Нега-десятичное	Двоичное	Нега-двоичное	Троичное	Нега-троичное
-12	28	-1100	110100	-110	1210
-11	29	-1011	110101	-102	1211
-10	10	-1010	1010	-101	1212
-9	11	-1001	1011	-100	1200
-8	12	-1000	1000	-22	1201
-7	13	-111	1001	-21	1202
-6	14	-110	1110	-20	20
-5	15	-101	1111	-12	21
-4	16	-100	1100	-11	22
-3	17	-11	1101	-10	10
-2	18	-10	10	-2	11
-1	19	-1	11	-1	12
0	0	0	0	0	0
1	1	1	1	1	1
2	2	10	110	2	2
3	3	11	111	10	120
4	4	100	100	11	121
5	5	101	101	12	122
6	6	110	11010	20	110
7	7	111	11011	21	111
8	8	1000	11000	22	112
9	9	1001	11001	100	100
10	190	1010	11110	101	101
11	191	1011	11111	102	102
12	192	1100	11100	110	220

Перевод в нега-позиционные системы

Нега-позиционное представление числа может быть получено последовательными делениями с остатком исходного числа на $b = -r$ (то есть на основание нега-позиционной системы) и записью подряд остатков начиная с последнего. Заметим, что если $a / b = c$, с остатком $d$, то $bc + d = a$. Пример перевода в нега-троичную систему:

$\begin{align} 146 & ~/~ -3 = & -48, & ~~~d = 2 \\ -48 & ~/~ -3 = & 16, & ~~~d = 0 \\ 16 & ~/~ -3 = & -5, & ~~~d = 1 \\ -5 & ~/~ -3 = & 1, & ~~~d = 2 \\ 1 & ~/~ -3 = & 0, & ~~~d = 1 \\ \end{align}$

Следовательно, нега-троичным представлением числа 146₍₁₀₎ является 12102_(-3). На самом деле всё это магия, когда перевод касается переводу из десятичной в нега-десятичную. Тем не менее предлагаю метод Ящика, который, в частности, известен в ИТМО: Допустим, есть число 34 в десятичной, нам нужно его перевести. Сперва делим число, пока его частное не станет меньше по модулю основания.

$\begin{align} 34 & ~/~ -10 = & -3, & ~~~d = 4 \\ \end{align}$

Далее суммируем частное и число ИКС, которое и записываем как остаток.

$\begin{align} -3 & ~+~ -7 = &-10,& ~~~d = 7\\ -10& ~/~ -10 = & 1,& ~~~d = 1\\ \end{align}$

Тут и прекращаем дурацкую магию. При этой магии мы и получили вроде как ответ - 174. Вверху есть таблица -> мы не ошиблись! Магия дружбы нас спасла!

См. также

• Нега-двоичная система счисления
• Знако-разрядная система счисления
• Симметричная система счисления