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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Системы счисления в культуре
Индо-арабская
Арабская
Индийские
Тамильская
Бирманская
Кхмерская
Лаосская
Монгольская
Тайская
Восточноазиатские
Китайская
Японская
Сучжоу
Корейская
Вьетнамская
Счётные палочки
Алфавитные
Абджадия
Армянская
Ариабхата
Кириллическая
Греческая
Эфиопская
Еврейская
Акшара-санкхья
Другие
Вавилонская
Египетская
Этрусская
Римская
Аттическая
Кипу
Майяская
Позиционные
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 = &   2, & ~~~d = 1 \\
   2 & ~/~ -3 = &   0, & ~~~d = 2 \\
\end{align}

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

Дроби[править | править исходный текст]

Арифметические операции[править | править исходный текст]

Сложение[править | править исходный текст]

Сложение столбиком надо делать как в обычной системе, например если вы хотите сложить в нега-десятичной системе счисления, то это надо делать как в десятичной системе счисления. Но с одним исключением: если при сложении в каком-либо разряде получается число не менее 10, то надо в этот разряд записать число единиц из полученного числа а из соседнего слева разряда вычесть единицу. Если слева нет разряда, то приписать слева 19 (для нега-десятичной, для нега-троичной 12, для нега-двоичной 11). Например (нега-десятичная система):

 ·  ·
 18115
+
  5487
  3582

5+7=12, 2 в разряд единиц, из соседнего слева вычитаем единицу. 8+5=13, 3 в разряд минус тысяч, из соседнего слева вычитаем единицу.

  ·
  72
+
  49
1901

2+9=11, 1 в разряд единиц, из соседнего слева вычитаем единицу. 6+4=10, 0 в разряд минус десятков, соседнего слева - нет, приписываем слева 19.

Вычитание[править | править исходный текст]

Вычитание столбиком надо делать как в обычной системе, например если вы хотите вычесть в нега-десятичной системе счисления, то это надо делать как в десятичной системе счисления. Но с одним исключением: если при вычитании в каком-либо разряде надо занять десяток, то вы это и делаете, но из соседнего слева разряда вы не вычитаете единицу, а наоборот прибавляете её туда. Если слева нет разряда, то приписать слева 1. Например (нега-десятичная система):

 1
 52
-
 39
 33

2-9 нельзя, занимаем единицу. 12-9=3, 3 в разряд единиц, в соседний слева разряд прибавляем единицу. 6-3=3.

 2
-
 9
13

2-9 нельзя, занимаем единицу. 12-9=3, 3 в разряд единиц, соседнего слева разряда нет, приписываем слева 1.

Умножение[править | править исходный текст]

Таблица умножения[править | править исходный текст]

Таблица умножения в нега-двоичной системе счисления[править | править исходный текст]

Таблица умножения в нега-двоичной системе счисления

× 0 1
0 0 0
1 0 1
Таблица умножения в нега-троичной системе счисления[править | править исходный текст]

Таблица умножения в нега-троичной системе счисления

2 0 2 121
1 0 1 2
0 0 0 0
х 0 1 2
Таблица умножения в нега-десятичной системе счисления[править | править исходный текст]

Таблица умножения в нега-десятичной системе счисления:

1 2 3 4 5 6 7 8 9
2 4 6 8 190 192 194 196 198
3 6 9 192 195 198 181 184 187
4 8 192 196 180 184 188 172 176
5 190 195 180 185 170 175 160 165
6 192 198 184 170 176 162 168 154
7 194 181 188 175 162 169 156 143
8 196 184 172 160 168 156 144 132
9 198 187 176 165 154 143 132 121

См. также[править | править исходный текст]