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

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

Введение

Возьмем какое-то число 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]

Аналогично будет с четырьмя битами, интервал расширится на 8 отрицательных значений и станет [-10, 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

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

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

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

negbin Значение
1010 -10
1011 -9
1000 -8
1001 -7
1110 -6
1111 -5
1100 -4
1101 -3
0010 -2
0011 -1
0000 0
0001 1
0110 2
0111 3
0100 4
0101 5

Сравнение

TBD

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

TBD

Сумма

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

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

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₀  (mod 2)
CF ∈ {0, 1}

Если оба a₀ и b₀ равны 1, то надо выставить флаг переноса (CF).
И следующий бит должен учитывать этот перенос. Но у следующего бита всегда знак противоположный, поэтому берем CF со знаком минус.

1
с₁ = a₁ + b₁ - CF  (mod 2)

с₁ может получиться -1 или 2.

  • Если 2, просто пишем 0 и выставляем CF в 1.
  • Если -1 (a₁ = 0, b₁ = 0, CF = 1) - результат должен быть 11 (это как раз -1₁₀). Пишем 1, а в CF сохраняем -1.

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

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

При сложении в столбик удобно рисовать CF над следующим столбцом в виде • (если CF = 1) или в виде ◦ (если CF = -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 •

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

1 + -1 = 0

1
2
3
4
5
  •
₊ 01      ( 1)
  11      (-1)
  --
  00      ( 0)

1 + 1 = 2

1
2
3
4
5
 ◦•
₊  1      (1)
   1      (1)
  --
 110      (2)
  • сначала складываем 1 и 1, получаем 0 и CF=•
  • Затем • + 0 + 0 => пишем 1 и CF=◦
  • Старший бит: ◦ + 0 + 0 => пишем 1, CF пустой

5 + 1 = 6

1
2
3
4
5
 ◦•◦•
₊  101     ( 5)
     1     ( 1)
   ---
 11010     ( 6)
  • Складываем 1+1, получаем 0 и CF=•
  • Затем •+0+0 => пишем 1 и CF=◦
  • Затем ◦+1+0 => пишем 0 и CF=•
  • Основные цифры кончились, но остался СF: •+0+0 => пишем 1 и CF=◦
  • Старший бит: ◦+0+0 => пишем 1, CF пустой

5 + 5 = 10

1
2
3
4
5
 ◦•◦•
₊  101     ( 5)
   101     ( 5)
   ---
 11110     (10)

Отличается от предыдущего только во третьем бите, тут ◦+1+1 => пишем 1 и CF=•

Умножение

TBD

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

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