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

Н́ега-позици́онная сист́ема счисл́ения — это позиционная система счисления с отрицательным основанием. Особенностью таких систем является отсутствие знака перед отрицательными числами и, следовательно, отсутствие правил знаков. Всякое число любой из нега-позиционных систем, отличное от $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», опубликованной в 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 = & 2, & ~~~d = 1 \\ 2 & ~/~ -3 = & 0, & ~~~d = 2 \\ \end{align}$

Следовательно, нега-троичным представлением числа 146₍₁₀₎ является 21102_(-3).

См. также

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

---

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Нега-позиционная система счисления. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

---