Остаток, делимость и двоичная запись

Коротко

Разделить a на b с остатком - значит найти частное q и остаток r, такие что a = b · q + r и 0 ≤ r < b. Остаток - это «сколько осталось после целых групп», и он всегда меньше делителя: на этом держатся и быстрый Евклид, и хеш-таблицы, и счёт «по кругу». a делится на b, когда остаток ноль. Последняя цифра неотрицательного числа - n % 10, а n // 10 её отрезает. Двоичная запись числа - разложение по степеням двойки: 13 = 8 + 4 + 1 = 1101₂. Цифр в ней ⌊log₂ n⌋ + 1 (при n ≥ 1), и это тот же счёт делений пополам из прошлого урока.

Если ты переводишь число в двоичную запись делением на 2 и знаешь, почему остаток от деления на 8 - это три последних бита, листай до «Теперь сам» в конце.

Как думаешь, какой будет день недели

Сегодня среда. Какой день недели будет через 100 дней? А какой был 100 дней назад? Ответь себе до того, как читать дальше, и обрати внимание, как именно ты считаешь. Перебирать сто дней никто не станет: все отбрасывают целые недели и смотрят, сколько дней осталось. Это «сколько осталось» и есть остаток, а урок - о том, почему он такой полезный.

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

Раскладка яиц по коробкам по десять штук. 137 яиц - это 13 полных коробок и 7 яиц россыпью. Частное - число полных коробок, остаток - россыпь, и россыпи всегда меньше десяти: иначе из неё собралась бы ещё одна коробка. Десятичная запись числа - это та же раскладка, повторённая на каждом уровне: коробки по десять, ящики по десять коробок, поддоны по десять ящиков. Двоичная запись - то же самое, только коробки по две штуки.

Механизм: деление с остатком и позиционная запись

Остаток от деления a на положительное b - единственное число r из 0..b-1, для которого a - r делится на b нацело. Частное q = a // b, остаток r = a % b, и a = b · q + r. В Python это верно и для отрицательных a: -3 % 7 = 4, потому что -3 = 7 · (-1) + 4. Поэтому «три дня назад» от дня номер d - это (d - 3) % 7, без особого случая для начала недели.

Три свойства остатка понадобятся в курсе постоянно:

свойство	пример	где пригодится
`0 ≤ r < b`	`100 % 7 = 2`	Евклид: остаток строго меньше делителя, числа убывают
остаток суммы - сумма остатков, снова по остатку	`(a + b) % m = (a % m + b % m) % m`	хеши, счёт с огромными числами
то же для произведения	`(a · b) % m = ((a % m) · (b % m)) % m`	возведение в степень по модулю

Позиционная запись - разложение числа по степеням основания: 4096 = 4 · 10³ + 0 · 10² + 9 · 10 + 6. Цифры неотрицательного числа добывают остатками: n % 10 - последняя цифра, n // 10 - число без неё (для отрицательных так нельзя: -3 % 10 равно 7). Для основания 2 всё то же: n % 2 - последний бит (он же признак нечётности), n // 2 - число без последнего бита. Деление пополам и есть сдвиг двоичной записи на одну позицию вправо, поэтому цифр в двоичной записи столько, сколько делений пополам до единицы, плюс одна: ⌊log₂ n⌋ + 1 при n ≥ 1. Ноль - особый случай: log₂ 0 не определён, а записывают его одной цифрой 0.

Правило

a = b · q + r, 0 ≤ r < b; в Python q = a // b, r = a % b, и для отрицательных a остаток тоже неотрицателен. b делит a ровно тогда, когда a % b == 0. Остаток суммы и произведения можно брать по ходу вычислений. Цифры числа в любой системе - это остатки при последовательном делении на основание, читаемые с конца.

Разбор: перевод в двоичную запись

Делим на два и записываем остатки. Таблица трассировки для 13:

`n`	`n % 2`	`n // 2`
13	1	6
6	0	3
3	1	1
1	1	0

Остатки сверху вниз - 1, 0, 1, 1, а читать их надо снизу вверх: 1101. Первый остаток - младшая цифра, потому что именно она отрезается первой. Проверка: 1 · 8 + 1 · 4 + 0 · 2 + 1 · 1 = 13. Программа:

dvoichnaya.py

def v_dvoichnuyu(n):
    if n == 0:
        return "0"
    cifry = []
    while n > 0:
        cifry.append(str(n % 2))
        n = n // 2
    cifry.reverse()
    return "".join(cifry)


for n in [0, 1, 6, 13, 255, 1000]:
    print(n, v_dvoichnuyu(n), bin(n), len(v_dvoichnuyu(n)))
print(int("1101", 2), 0b1101)

↳ выводpython3 dvoichnaya.py

0 0 0b0 1
1 1 0b1 1
6 110 0b110 3
13 1101 0b1101 4
255 11111111 0b11111111 8
1000 1111101000 0b1111101000 10
13 13

"".join(cifry) склеивает строки списка без разделителя. Встроенные bin(n) и int(s, 2) делают то же в обе стороны. Приставка 0b означает «дальше двоичные цифры»: bin печатает с ней, и в программе 0b1101 - то же число 13. У тысячи 10 двоичных цифр: ⌊log₂ 1000⌋ + 1 = 9 + 1. У 255 - восемь единиц: это наибольшее число, которое помещается в восемь бит, 2^8 - 1.

Разбор: быстрый Евклид и остаток вместо вычитания

В первой главе алгоритм Евклида вычитал меньшее из большего, и на паре (1000000, 1) ему нужен миллион кругов. Подряд идущие вычитания одного и того же b из a - это и есть деление с остатком: сколько раз вычлось - частное, что осталось - остаток. Значит, всю серию вычитаний можно заменить одним a % b, и НОД не изменится: a % b - это a минус несколько b, а вычитание, как показал первый урок, общих делителей не меняет. Строка a, b = b, a % b сначала вычисляет обе правые части по старым a и b и только потом присваивает - как обмен из урока про имена:

evklid_bystryj.py

def nod(a, b):
    krugov = 0
    while b != 0:
        a, b = b, a % b
        krugov = krugov + 1
    return a, krugov


print(nod(84, 36), nod(1000000, 1), nod(0, 5), nod(9, 0))
print(nod(832040, 514229))

↳ выводpython3 evklid_bystryj.py

(12, 2) (1, 1) (5, 1) (9, 0)
(1, 28)

Остаток строго меньше делителя, поэтому b убывает на каждом круге и цикл кончается. Пары с нулём обрабатываются без особых случаев: nod(9, 0) не входит в цикл вовсе. Самый неудобный вход - соседние числа Фибоначчи (ряд 0, 1, 1, 2, 3, 5, 8, ..., где каждое - сумма двух предыдущих): частное у них почти на каждом круге равно 1, и пара сдвигается по ряду вниз всего на одну ступень. 832040 и 514229 - тридцатое и двадцать девятое числа ряда, и для этой пары около миллиона кругов 28, а не сотни тысяч. Ряд растёт примерно в 1.6 раза за ступень, поэтому кругов Евклида всегда порядка логарифма от чисел.

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

Остаток от деления на ноль не определён: a % 0 - ошибка ZeroDivisionError, и условие while b != 0 стоит в Евклиде именно ради этого. Хеш вида h % m с отрицательным h в C даёт отрицательный номер ячейки и пишет мимо массива; в Python номер неотрицателен, но перенос кода в обратную сторону ломается. Признак нечётности n % 2 == 1 верен в Python и неверен в C для отрицательных n - там -3 % 2 равно -1. И при счёте с огромными числами остаток берут на каждом шаге: произведение тысячи чисел целиком, а потом % m - это число из тысяч цифр, которое Python посчитает, но медленно.

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

Распределение по шардам и корзинам - hash(key) % N. Номер дня недели, часа на циферблате, позиции в кольцевом буфере - остаток. Проверочные цифры номеров карт и ИНН - остатки от деления на 10 и 11. Права доступа в Linux 755 - три восьмеричные цифры, то есть по три бита на владельца, группу и остальных, и chmod читается, только если двоичная запись не пугает. Маски подсетей, флаги в битовом поле, размер файла в «круглых» 4096 - всё это степени двойки и их двоичная запись.

Теперь сам

Переведи 37 в двоичную запись. Чему равно 37 % 8 и как его увидеть прямо в двоичной записи?

Ответ. 37 = 32 + 4 + 1 = 100101₂ (деления: 37, 18, 9, 4, 2, 1 с остатками 1, 0, 1, 0, 0, 1 - читаем снизу вверх). 37 % 8 = 5, а 5 = 101₂ - это ровно три последних бита. Так бывает всегда: остаток от деления на 2^k - это последние k бит, а частное - всё, что левее: левые биты стоят на местах 2^k и старше, то есть вместе дают кратное 2^k (100101₂ = 100₂ · 2³ + 101₂). Деление на 10 в десятичной записи отрезает цифру точно так же.

Главное

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