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

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

${\displaystyle x=\sum _{k=0}^{n-1}a_{k}(-r)^{k}}$,

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

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

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

${\displaystyle 17=2^{4}+2^{0}=(-2)^{4}+(-2)^{0}}$

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

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

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

${\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}}}$

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

// Нега-троичная
static string negaternary(int value)
{
	string result = string.Empty;
	do
	{
		int remainder = value % -3;
		value = value / -3;
		if (remainder < 0)
		{
			remainder += 3;
			value += 1;
		}
		result = remainder.ToString() + result;
	} while (value != 0);
	return result;
}

// Нега-двоичная
#include <iostream>
using namespace std;

int main()
{
	int value,rem;
	string res="";
	cin>>value;
	do
	{
		rem=value%-2;
		value=value/-2;
		if(rem<0)
		{
			rem=rem+2;
			value++;
		}
		if(rem==1) res="1"+res;
		if(rem==0) res="0"+res;
	}
    while(value!=0);
	cout<<res;
}

# Нега-двоичная
res = ""
value = int(input())

while True:
    rem = value % -2
    value = value // -2
    if rem < 0:
        rem = rem + 2
        value = value + 1

    if rem == 1:
        res = "1" + res
    if rem == 0:
        res = "0" + res

    if value == 0:
        break

print(res)

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