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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Системы счисления в культуре
Индо-арабская
Арабская
Тамильская
Бирманская
Кхмерская
Лаосская
Монгольская
Тайская
Восточноазиатские
Китайская
Японская
Сучжоу
Корейская
Вьетнамская
Счётные палочки
Алфавитные
Абджадия
Армянская
Ариабхата
Кириллическая
Греческая
Эфиопская
Еврейская
Акшара-санкхья
Другие
Вавилонская
Египетская
Этрусская
Римская
Дунайская
Аттическая
Кипу
Майяская
Эгейская
Символы КППУ
Позиционные
2, 3, 4, 5, 6, 8, 10, 12, 16, 20, 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).

Реализация на C#:

static string negaternary(int value)
{
	string result = string.Empty;
	while (value != 0)
	{
		int remainder = value % -3;
		value = value / -3;
		if (remainder < 0)
		{
			remainder += 3;
			value += 1;
		}
		result = remainder.ToString() + result;
	}
	return result;
}

Дроби[править | править вики-текст]

Арифметические операции[править | править вики-текст]

Сложение[править | править вики-текст]

Сложение столбиком надо делать как в обычной системе, например если вы хотите сложить в нега-десятичной системе счисления, то это надо делать как в десятичной системе счисления. Но с одним исключением: если при сложении в каком-либо разряде получается число не менее 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

См. также[править | править вики-текст]