Арифметика по основанию −2: перенос и деление

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

Как думаешь, куда перенести две единицы

В обычном двоичном сложении 1+1=10. Но по основанию −2 запись 10 означает −2, хотя складывали два положительных числа 1. Правильная запись результата - 110: 4−2=2. Значит правило переноса должно быть другим.

В текущем разряде оставляем 0. В соседний переносим −1, потому что его вес в −2 раза больше текущего: −1·(−2)=2. Отрицательный перенос тоже придётся обработать. Он не означает отрицательную цифру в готовом ответе: очередной разряд снова нормализуется в 0 или 1, а остаток уходит дальше.

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

При обмене жетонов следующий стол стоит с обратным знаком и вдвое большим весом. Два положительных жетона первого стола можно заменить одним долгом на следующем: долг от отрицательного веса даёт положительный вклад. Если на столе оказался долг −1, его можно заменить единицей здесь и единицей на соседнем отрицательном весе: 1−2=−1.

Такой обмен сохраняет общую стоимость. Смысл переноса именно в этом равенстве, а не в том, что «лишняя единица всегда идёт налево». Поэтому удобно сначала написать равенство, а затем код. Иначе одинаковые значки >> и + легко скрывают разные числовые операции.

Механизм: нормализация суммы в разряде

Пусть в позиции сложились входные цифры и перенос из младшей: получилось целое s. Младшую цифру выбираем как digit=s%2, то есть по чётности. Остаток переносится по равенству carry=(s−digit)/(−2). Деление точное, поэтому отрицательные значения не создают проблемы округления.

При сложении двух слов перенос остаётся в {−1,0,1}, а s лежит от −1 до 3. Цикл заканчивается после исчезновения обеих входных строк и переноса. Даже когда входные цифры уже кончились, перенос −1 потребует ещё двух шагов: сначала цифра 1 с переносом 1, затем цифра 1 с переносом 0.

Правило

Складывай по разрядам, сохраняя равенство s=digit−2·carry. Продолжай до нулевого переноса, а не только до конца входных слов. Сдвиг цифр влево на одну позицию умножает значение на −2. Для деления здесь используем n=d·q+r, 0≤r<|d|; при делителе 0 операция не определена.

Из правила сдвига следует способ изменить знак значения: сложить исходное слово и сдвинутую копию, потому что x+(−2)x=−x. Умножение можно строить обычным сложением сдвинутых копий: единичная цифра множителя выбирает копию, сдвиг на i позиций умножает её значение на (−2)^i. Само сложение при этом должно быть новым, а не стандартным двоичным.

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

Сложим две единицы. Первая сумма равна 2: пишем 0, перенос −1. Во второй позиции входных цифр нет, сумма −1: пишем 1, перенос 1. Третья сумма 1: пишем 1, перенос 0. Снизу вверх получились 0,1,1, то есть 110.

Другой пример - 11+1. Строка 11 обозначает −1. В младшем разряде сумма 2, цифра 0, перенос −1. Во втором входная единица и перенос уничтожаются: сумма 0. Значение результата 0. Обычное двоичное сложение дало бы 100, то есть уже +4. Такой пример хорошо отличает реализацию нужной арифметики от случайно работающей на одних нулях и единицах.

def value(word):
    total, weight = 0, 1
    while word:
        total += (word & 1) * weight
        weight *= -2
        word >>= 1
    return total


def add(a, b):
    result, place, carry = 0, 1, 0
    while a or b or carry:
        s = (a & 1) + (b & 1) + carry
        digit = s & 1
        result |= digit * place
        carry = (s - digit) // (-2)
        a >>= 1
        b >>= 1
        place <<= 1
    return result


def divide(n, d, width):
    if d == 0:
        raise ZeroDivisionError
    low = [0]
    high = [0]
    for i in range(width):
        weight = (-2) ** i
        low.append(low[-1] + min(weight, 0))
        high.append(high[-1] + max(weight, 0))

    def contains(qlo, qhi):
        a, b = d * qlo, d * qhi
        return min(a, b) <= n <= max(a, b) + abs(d) - 1

    if not contains(low[width], high[width]):
        raise OverflowError("частное не помещается")
    word, prefix = 0, 0
    for i in range(width - 1, -1, -1):
        candidate = prefix + (-2) ** i
        if contains(candidate + low[i], candidate + high[i]):
            prefix = candidate
            word |= 1 << i
    return word, n - d * prefix


pairs = [(3, 1), (1, 1), (2, 2), (15, 1)]
for a, b in pairs:
    c = add(a, b)
    print(f"{a:b} + {b:b} = {c:b}; значение {value(c)}")
for n, d in [(-5, 3), (-5, -3), (17, 3)]:
    q, r = divide(n, d, 8)
    print(n, "/", d, "частное", f"{q:b}", "остаток", r)
checked = 0
for a in range(64):
    for b in range(64):
        assert value(add(a, b)) == value(a) + value(b)
        checked += 1
print("проверены суммы:", checked)

11 + 1 = 0; значение 0
1 + 1 = 110; значение 2
10 + 10 = 1100; значение -4
1111 + 1 = 1100; значение -4
-5 / 3 частное 10 остаток 1
-5 / -3 частное 110 остаток 1
17 / 3 частное 101 остаток 2
проверены суммы: 4096

Первые четыре строки показывают именно битовые записи и их значения. Например, 10+10 - это −2+(−2)=−4, а запись −4 равна 1100. В трёх следующих строках частное тоже напечатано по основанию −2; остаток - обычным десятичным числом. Последняя строка относится ко всем парам шестибитных входов, а не к делению.

Разбор: цифра частного через интервалы

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

Массивы low[i], high[i] содержат минимум и максимум значений младших i разрядов. Их получаем суммой отрицательных и положительных весов. Уже выбранные старшие цифры имеют суммарное значение prefix. Если очередная цифра 1, к этому значению добавится (−2)^i, а оставшаяся часть лежит между low[i] и high[i]. Получается целый интервал возможных частных [qlo,qhi].

При положительном d такой интервал допускает делимые от d·qlo до d·qhi+d−1: для каждого целого частного подходят все остатки. При отрицательном d концы произведений меняются местами. Общая проверка поэтому берёт min(d·qlo,d·qhi) и max(d·qlo,d·qhi)+|d|−1. Если исходное n попало в этот диапазон, выбираем цифру 1; иначе - 0.

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

Например, −5=3·(−2)+1; ответ по основанию −2 равен 10, остаток 1. Для делителя −3 получаем −5=(−3)·2+1, запись частного 110, остаток снова 1. Усечение частного к нулю дало бы другие остатки и нарушило бы выбранный контракт. Алгоритм делает w шагов по битам, но арифметические операции здесь над обычными целыми Python. Это модель построения цифр, а не замер аппаратного делителя.

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

Отбрасывают перенос после старшего входного бита и получают усечённый результат. Или складывают обычным a+b, потому что переменные хранятся в целочисленном типе. Однако этот тип хранит упаковку цифр, а не их значение по основанию −2. В задаче после теории эти две интерпретации специально разведены.

Ещё одна ошибка - называть сдвиг вправо делением с привычным остатком. Удаление младшей цифры соответствует делению на −2 после вычитания этой цифры. Это следует из n=(−2)q+r. Видимая операция над битами сама не задаёт округление обычного частного по произвольному делителю.

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

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

Теперь сам

Сложи 10 и 1 по основанию −2. Затем запиши частное и остаток для −4/3 по договорённости урока. Что должно произойти, если частному не хватает заданных битов?