Минусдвоичная система счисления

Что будет, если в качестве основания системы счисления поставить отрицательное число?

Введение

Возьмем целое число a, и представим его в двоичнои представлении

1
a = aₙ⋅2ⁿ + aₙ₋₁⋅2ⁿ⁻¹ + ... + a₁⋅2¹ + a₀⋅2⁰

Все цифры в разложенииaᵢ ∈ {0, 1}, и такое разложение единственно для положительных чисел. Для отрицательных чисел же используется разные способы:

  • прямой код - бит для знака
  • обратный код - все биты инвертируются
  • дополнительный код - инвертируются биты и прибавляется единица

Дополнительный код достаточно удобный, поскольку арифметические операции не требуют проверки для знака числа.

В нем слегка сложным будет операция расширения, т.е. когда число хранится, например, в одном байте, а мы хотим его превратить в четырехбайтовое:

1
2
char a = -2;      //                                  1111 1110
int b = a;        // 1111 1111  1111 1111  1111 1111  1111 1110

Для этого надо сначала определить знак, и все дополнительные биты выставить либо в 1, либо в 0.

Но что, если мы попробуем в качестве основания системы счисления использовать -2?

Тогда представление числа будет таким:

1
a = aₙ⋅(-2)ⁿ + aₙ₋₁⋅(-2)ⁿ⁻¹ + ... + a₁⋅(-2)¹ + a₀⋅(-2)⁰

При этом по-прежнему оставляем цифры aᵢ ∈ {0, 1}

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

Посмотрим, какие значения получаются при разных комбинациях битов и их разных количествах

Диапазоны значений

Для одного бита.

Двоичное Формула Значение
0 0⋅(-2)⁰ = 0 0
1 1⋅(-2)⁰ = 1 1

Покрывает интервал [0, 1].

Добавим еще бит. (-2)¹ = -2

Двоичное Формула Значение
10 1⋅(-2)¹ + 0⋅(-2)⁰ = -2 + 0 -2
11 1⋅(-2)¹ + 1⋅(-2)⁰ = -2 + 1 -1

Интервал значений расширился до [-2, 1], т.е по сравнению с однобитовыми добавились представления отрицательных чисел -2, -1.

Еще бит. (-2)² = 4

Двоичное Формула Значение
100 1⋅(-2)² + 0⋅(-2)¹ + 0⋅(-2)⁰ = 4 - 0 + 0 4
101 1⋅(-2)² + 0⋅(-2)¹ + 1⋅(-2)⁰ = 4 - 0 + 1 5
110 1⋅(-2)² + 1⋅(-2)¹ + 0⋅(-2)⁰ = 4 - 2 + 0 2
111 1⋅(-2)² + 1⋅(-2)¹ + 1⋅(-2)⁰ = 4 - 2 + 1 3

С тремя битами интервал [-2, 1] расширился в положительную сторону, до [-2, 5].

С четырьмя битами: (-2)³ = -8, интервал расширится на 8 отрицательных значений и станет [-10, 5].

Двоичное Формула Значение
1000 1⋅(-2)³ + 0⋅(-2)² + 0⋅(-2)¹ + 0⋅(-2)⁰ = -8 -8
1001 1⋅(-2)³ + 0⋅(-2)² + 0⋅(-2)¹ + 1⋅(-2)⁰ = -7 -7
1010 1⋅(-2)³ + 0⋅(-2)² + 1⋅(-2)¹ + 0⋅(-2)⁰ = -10 -10
1011 1⋅(-2)³ + 0⋅(-2)² + 1⋅(-2)¹ + 1⋅(-2)⁰ = -9 -9
1100 1⋅(-2)³ + 1⋅(-2)² + 0⋅(-2)¹ + 0⋅(-2)⁰ = -4 -4
1101 1⋅(-2)³ + 1⋅(-2)² + 0⋅(-2)¹ + 1⋅(-2)⁰ = -3 -3
1110 1⋅(-2)³ + 1⋅(-2)² + 1⋅(-2)¹ + 0⋅(-2)⁰ = -6 -6
1111 1⋅(-2)³ + 1⋅(-2)² + 1⋅(-2)¹ + 1⋅(-2)⁰ = -5 -5
Количество бит Интервал Длина интервала
1 0 .. 1 2
2 -2 .. 1 4
3 -2 .. 5 8
4 -10 .. 5 16
5 -10 .. 21 31
6 -42 .. 21 64
7 -42 .. 85 128
8 -170 .. 85 256

Профит от такого представления, кажется, только один - легко расширить количество бит хранения, например, с байта до четырех байт. Для этого просто заполняем нулями дополнительные байты.

Отсортированные числа

Если выписать минусдвоичные числа и отсортировать, получится такой список

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1010    -10
1011     -9
1000     -8
1001     -7
1110     -6
1111     -5
1100     -4
1101     -3
  10     -2
  11     -1
   0      0
   1      1
 110      2
 111      3
 100      4
 101      5

Видно как бинарные значения одной длины группируются в непрерывные диапазоны.

Перевод из десятичной и в десятичную

Перевод из минусдвоичной записи в обычное десятичное число устроен ровно так же, как в любой позиционной системе: берем цифры и умножаем их на веса разрядов.

Отличие только в том, что веса идут с чередующимся знаком:

1
2
3
4
5
6
... (-2)⁵ = -32
    (-2)⁴ =  16
    (-2)³ =  -8
    (-2)² =   4
    (-2)¹ =  -2
    (-2)⁰ =   1

Например:

1
11010₋₂ = 1⋅16 + 1⋅(-8) + 0⋅4 + 1⋅(-2) + 0⋅1 = 6

То есть читать число можно слева направо, но проще думать справа налево: младший бит отвечает за 1, следующий за -2, потом 4, потом -8, и так далее.

В обратную сторону работает почти тот же алгоритм, что и для обычной двоичной системы: делим число на основание и выписываем остатки. Только основание теперь -2.

Важный нюанс: цифры у нас все равно только 0 и 1, поэтому остаток тоже должен быть 0 или 1. Если число нечетное, пишем остаток 1 и дальше делим на -2 уже число n - 1. Если четное, пишем 0 и делим само n.

1
2
если n четное:   digit = 0, next = -n / 2
если n нечетное: digit = 1, next = -(n - 1) / 2

Повторяем, пока next не станет нулем. Остатки получаются от младшего разряда к старшему, поэтому в конце их надо прочитать в обратном порядке.

Например, переведем 6:

n digit next
6 0 -3
-3 1 2
2 0 -1
-1 1 1
1 1 0

Остатки снизу вверх дают 11010₋₂.

Небольшой JavaScript с функциями negbinToInt, intToNegbin, cmp, neg, add и mul лежит рядом со статьей: source/assets/negbin/negbin.js.

Сравнение

Сравнивать минусдвоичные числа можно и через перевод в десятичные, но есть правило прямо для записи.

Сначала убираем незначащие нули слева. Для ненулевых чисел знак уже виден по длине записи:

  • нечетное количество бит - число положительное;
  • четное количество бит - число отрицательное.

Это следует из старшего разряда. Если старший вес положительный, он больше суммы всех младших по модулю, и число получается положительным. Если старший вес отрицательный, младшие разряды уже не могут его полностью перекрыть.

Например:

Длина Примеры Диапазон
1 1 1
2 10..11 -2..-1
3 100..111 2..5
4 1000..1111 -10..-3

Отсюда сразу получается первая часть сравнения:

  • отрицательное меньше нуля и положительного;
  • ноль меньше положительного, но больше отрицательного;
  • среди положительных чисел более длинная запись больше;
  • среди отрицательных чисел более длинная запись меньше.

Если длина одинаковая, идем слева направо до первого отличающегося бита. Этот бит и решает сравнение: младшие разряды уже не смогут его перевесить.

Но есть важная поправка: веса разрядов чередуют знак.

  • если отличающийся разряд имеет положительный вес, то 1 больше 0;
  • если отличающийся разряд имеет отрицательный вес, то 1 меньше 0.

Например, сравним 101₋₂ и 111₋₂. Длина одинаковая, первый бит одинаковый, а второй отличается:

1
2
101₋₂ = 5
111₋₂ = 3

Второй слева бит стоит в разряде (-2)¹ = -2, поэтому там 1 делает число меньше. Значит 101₋₂ > 111₋₂.

Противоположное число

Для обычного двоичного числа смена знака - отдельная история: прямой код, обратный код, дополнительный код. В минусдвоичной системе знак уже зашит в сами веса разрядов, поэтому хочется получить такую же запись, но для числа -x.

Главное тождество тут такое:

1
(-2)ⁿ⁺¹ + (-2)ⁿ = (-2)ⁿ⋅(-2 + 1) = -(-2)ⁿ

То есть если в числе есть единица в разряде n, то в противоположном числе вместо нее можно поставить две единицы: одну в том же разряде, и одну в следующем.

Например, единица в младшем разряде означает 1. Противоположное число -1 в минусдвоичной записи равно 11, потому что:

1
11₋₂ = 1⋅(-2)¹ + 1⋅(-2)⁰ = -2 + 1 = -1

Это можно применять как локальное правило. Двигаемся справа налево:

  • встретили 0 - пишем 0;
  • встретили 01 - пишем 11;
  • встретили 11 - пишем 01.

Почему работает последняя пара? Когда мы превращаем единицу в 11, старшая единица как бы попадает в следующий разряд. Если там был 0, он становится 1: получается 01 → 11. Если там уже была 1, то она вместе с переносом сворачивается в 0, и получается 11 → 01.

Можно думать об этом как об очень маленьком автомате, у которого есть один отложенный перенос в следующий разряд.

В конце удаляем незначащие нули слева.

Примеры:

x Значение -x Значение
1 1 11 -1
11 -1 1 1
101 5 1111 -5
11010 6 1110 -6

Сумма

Когда мы суммируем двоичные числа, алгоритм достаточно прямолинеен - складываем побитно, начиная с младшего, и, если произошло переполнение, то учитываем его.

Для минусдвоичного представления все становится чуть более запутанным

1
2
3
4
5
a = aₙ⋅2ⁿ + aₙ₋₁⋅2ⁿ⁻¹ + ... + a₁⋅2¹ + a₀⋅2⁰
b = bₙ⋅2ⁿ + bₙ₋₁⋅2ⁿ⁻¹ + ... + b₁⋅2¹ + b₀⋅2⁰

c = a + b
с = сₙ⋅2ⁿ + сₙ₋₁⋅2ⁿ⁻¹ + ... + с₁⋅2¹ + с₀⋅2⁰

Младший бит просуммируется нормально

1
2
с₀ = a₀ + b₀ + CF₀  (mod 2)
CF₀ = 0

Будем считать, что CFᵢ - это добавка, которую надо учесть именно в текущем столбце. Тогда после сложения 1 + 1 в следующем столбце появляется не +1, а -1: ведь следующий разряд имеет противоположный знак.

1
с₁ = a₁ + b₁ + CF₁  (mod 2), где CF₁ = -1

Если в каком-то столбце сумма получилась 2, пишем 0, а в следующий столбец передаем CF = -1: этот минус в следующем разряде как раз и даст нужные +2 в текущем.

Если сумма получилась -1, пишем 1, а в следующий столбец передаем CF = 1: потому что 1₋₂ + 1⋅(-2) = -1.

Для следующих битов CF может быть и 1, и -1. Так что c₂ = a₂ + b₂ + CF₂ может получиться значение 3 (111₋₂). В этом случае пишем 1, а в следующий столбец снова передаем CF = -1.

В общем, получается что CF может быть 0, 1 или -1.

При сложении в столбик удобно рисовать CF над столбцом, в котором он будет учтен: ◦, если в этом столбце надо добавить -1, и •, если надо добавить 1.

Все варианты можно свести в табличку

Таблица преобразования при сложении

CF aᵢ bᵢ cᵢ следующий CF
0 0 = 0
0 1 = 1
1 1 = 0 ◦
◦ 0 0 = 1 •
◦ 0 1 = 0
◦ 1 1 = 1
• 0 0 = 1
• 0 1 = 0 ◦
• 1 1 = 1 ◦

Примеры суммирования

₊
₊
₊
₊

Умножение

С умножением все неожиданно спокойно. Если у нас уже есть сложение, которое правильно обрабатывает переносы, то умножать можно почти как в обычной двоичной записи.

Идем по цифрам второго множителя справа налево:

  • если очередная цифра 0, ничего не добавляем;
  • если очередная цифра 1, берем первый множитель и сдвигаем его влево на столько разрядов, насколько эта цифра удалена от конца;
  • все получившиеся промежуточные результаты складываем.

Сдвиг влево на один разряд в минусдвоичной системе означает умножение на основание, то есть на -2. Но это не отдельное правило, а просто обычный вес разряда. Поэтому частичные произведения могут быть то положительными, то отрицательными, а итоговая сумма все равно собирается тем же самым add.

Например, 101₋₂ = 5, 110₋₂ = 2:

1
2
3
4
5
6
7
8
      101     ( 5)
×     110     ( 2)
---------
     000      младший 0 пропускаем
    1010      1 во втором разряде: 1010₋₂ = -10
   10100      1 в третьем разряде: 10100₋₂ = 20
---------
   11110      (10)

Примечание. Таблица пятибитных негбинарных

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
    0     0
    1     1
   10    -2
   11    -1
  100     4
  101     5
  110     2
  111     3
 1000    -8
 1001    -7
 1010   -10
 1011    -9
 1100    -4
 1101    -3
 1110    -6
 1111    -5
10000    16
10001    17
10010    14
10011    15
10100    20
10101    21
10110    18
10111    19
11000     8
11001     9
11010     6
11011     7
11100    12
11101    13
11110    10
11111    11