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

Разделы:

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

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

Содержание

1 Примеры
2 История
3 Использование
4 Перевод в нега-позиционные системы
5 Дроби
6 Арифметические операции
7 См. также

Примеры

Нега-позиционная запись	Позиционная запись	Представление числа
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{displaystyle b=-r}

$b = -r$ представляется в виде линейной комбинации степеней числа −r{displaystyle -r} $-r$ :

x=∑k=0n−1ak(−r)k{displaystyle x=sum _{k=0}^{n-1}a_{k}(-r)^{k}}

x = sum_{k=0}^{n-1} a_k (-r)^k

, где ak{displaystyle a_{k}}

a_{k}

— это целые числа, называемые цифрами и удовлетворяющие неравенству 0≤ak<r{displaystyle 0leq a_{k}<r}

0 leq a_k < r

, k{displaystyle k}

k

— порядковый номер разряда начиная с нулевого, n — число разрядов.

Каждая степень (−r)k{displaystyle (-r)^{k}}

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

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

Некоторые числа обладают одним и тем же представлением в системах счисления с основанием b{displaystyle b}

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

17=24+20=(−2)4+(−2)0{displaystyle 17=2^{4}+2^{0}=(-2)^{4}+(-2)^{0}}

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

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

$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{displaystyle b=-r}

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

146 / −3=−48, d=2−48 / −3=16, d=016 / −3=−5, d=1−5 / −3=2, d=12 / −3=0, d=2{displaystyle {begin{aligned}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{aligned}}}

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+ 491901

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

Вычитание

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

1 52- 39 33

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

2- 913

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

Умножение

Таблица умножения

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

×	0	1
0	0	0
1	0	1

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

х	1	2
2	2	121
1	1	2
0	0	0

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

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

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

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

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