Основание −2: знак из чередующихся весов

Если переводишь −3 в основание −2 и можешь вывести диапазон четырёхбитного слова, переходи к «Теперь сам».

Как думаешь, что означает строка 1101

Пусть программа получила четыре бита 1101. В обычной двоичной записи это 13. В четырёхбитном дополнительном коде это −3: из 13 вычитаем 16. Теперь прочтём те же цифры с основанием −2: 1·(−8)+1·4+0·(−2)+1=−3. Значения случайно совпали для этой строки, но совпадение не является правилом формата.

У строки 1010 обычное двоичное значение 10, дополнительный код даёт −6, а новое основание даёт −8−2=−10. До вычисления нужно узнать, какой формат задан. Биты сами не содержат пометки «это такое-то число». Эту договорённость хранит описание файла, команды или типа данных.

На что это похоже

Представь ряд коробок с жетонами. На первой написано «добавить 1», на второй «вычесть 2», на третьей «добавить 4», на четвёртой «вычесть 8». Единица в разряде означает взять соответствующий жетон, ноль - пропустить. Отрицательное значение получается суммой жетонов с отрицательными весами, хотя отрицательных цифр в записи нет.

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

Механизм: деление выбирает очередную цифру

Для обычного основания 2 мы пишем n=2q+r. Для нового основания равенство становится n=(−2)q+r. Цифра r должна равняться 0 или 1. Поэтому она определяется чётностью n: чётному соответствует 0, нечётному 1. После выбора цифры число n−r делится на −2 без остатка, и частное снова целое.

В Python удобно брать r=n%2, то есть остаток от положительного делителя 2. Выражение n%(-2) имеет другую договорённость о знаке остатка и может дать −1, который не является допустимой цифрой. Например, для n=−3 нужный шаг такой: r=1, q=(−3−1)/(−2)=2. Записываем цифру 1 и продолжаем с 2.

Выписываем остатки от младшего разряда к старшему. Чтение готовой строки идёт в обратном направлении: при очередной цифре d накопленное значение заменяется на −2·value+d. Это та же схема Горнера, но множитель отрицателен. Не надо отдельно проверять знак или считать степени для каждой цифры.

Правило

Любое целое имеет конечную запись цифрами 0 и 1 по основанию −2. Для кодирования повторяй r=n%2, n=(n−r)//(-2) до нулевого частного и переверни остатки. Ноль записывается отдельной цифрой 0. Для декодирования умножай накопленное значение на −2 и прибавляй следующую цифру. Ведущие нули значения не меняют.

Почему процесс завершается? При |n|>1 новое частное по модулю меньше прежнего. Остаются три малых состояния: 0 завершает цикл, 1 переходит в 0, а −1 - в 1, затем 0. Почему запись единственна? Младшая цифра однозначно задана чётностью; после её удаления тот же довод применяется к частному. Речь о записи без лишних ведущих нулей.

Разбор: отрицательное число и обратная проверка

Для −3 получаем цепочку −3 → 2 → −1 → 1 → 0. Остатки по пути равны 1,0,1,1; читаем назад и получаем 1101. Теперь проверим значение: −8+4+1=−3. Каждая стрелка сохраняла равенство n=(−2)q+r, поэтому обратная подстановка обязана вернуть исходное число.

Для 2 шаги другие: 2 → −1 → 1 → 0, остатки 0,1,1, запись 110. Уже пример 1+1=110 показывает, почему стандартный двоичный сумматор не подходит: цифры похожи, но переносы должны учитывать знак основания.

def zapis(n):
    if n == 0:
        return "0"
    digits = []
    while n:
        r = n % 2
        digits.append(str(r))
        n = (n - r) // (-2)
    return "".join(reversed(digits))


def znachenie(s):
    n = 0
    for c in s:
        n = -2 * n + int(c)
    return n


for n in [-10, -3, -1, 0, 2, 5]:
    s = zapis(n)
    print(n, s, znachenie(s))

width = 4
mask = sum(1 << i for i in range(1, width, 2))
values = [((w ^ mask) - mask) for w in range(1 << width)]
assert len(set(values)) == 1 << width
print("четыре бита:", min(values), max(values))
for n in range(min(values), max(values) + 1):
    word = (n + mask) ^ mask
    assert znachenie(f"{word:04b}") == n
print("фиксированная ширина: все 16 значений совпали")

-10 1010 -10
-3 1101 -3
-1 11 -1
0 0 0
2 110 2
5 101 5
четыре бита: -10 5
фиксированная ширина: все 16 значений совпали

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

Разбор: диапазон и перевод одной маской

Нумеруем позиции с нуля от младшей. Пусть A - обычное положительное целое, у которого единицы стоят во всех нечётных позициях выбранного слова. Для четырёх битов A=1010₂=10. Минимальное значение нового формата равно −A: включены все отрицательные веса и выключены положительные. Максимальное равно (2^w−1)−A, где w - число битов. При w=4 это 5.

Для битового слова u его значение равно u−2·(u&A): разряды с отрицательным весом сначала были учтены положительно, поэтому вычитаем их дважды. Тождество u XOR A = u+A−2·(u&A) даёт более короткую формулу value=(u XOR A)−A. Отсюда обратный перевод: u=(value+A) XOR A, когда значение лежит в диапазоне.

Добавление A переводит весь допустимый диапазон в числа 0…2^w−1, а XOR с фиксированной маской переставляет эти числа без повторов. Значит диапазон непрерывен и каждое целое в нём представляется ровно одним словом. Для восьми битов A=170, диапазон от −170 до 85. Это не диапазон восьмибитного дополнительного кода.

Что ломается без этого

Код берёт модуль числа, переводит его как обычное двоичное и добавляет слева знак. Получается другой формат. Или вычитает число из 2^w, рассчитывая на дополнительный код. Проверка на 0 и 1 этого не заметит; отрицательные значения и разряд с весом −2 сразу обнаруживают ошибку. Поэтому проверяй обратное чтение, крайние значения и числа по обе стороны нуля.

Зачем это в работе

Такой формат редко выбирают для обычного прикладного хранения. Он полезен как проверка понимания машинного представления: знак, диапазон и операции выводятся из весов, а не из привычного вида строки. Тот же навык нужен, когда читаешь нестандартное поле протокола или сравниваешь арифметическую модель с реализацией. Необычное основание само по себе не обещает ускорения процессора.

Теперь сам

Переведи 6 в основание −2. Затем найди минимальное и максимальное значения шестибитного слова. Объясни, меняет ли добавленный слева ноль значение −3.