Разговор сегодня пойдет про деление столбиком. Да, то самое деление столбиком, которое учили в школе. Я расскажу о технике, о которой знают многие, и которая также применяется для того, чтобы разделить два целых числа в информатике.
Вначале, мы берем самый старший разряд и начинаем делить на более младший. Итак, нужно разделить число 100112 на 1012.
10011 | 101
-101 | (0) Как видим, тут 100 < 101, не вычитаем, считаем что это 0
--------
1001 Добавляем новый разряд
- 101 (1) А тут 1001 > 101, вычтем 1001 - 101 = 100
--------
1001 Добавляем новый разряд
- 101 (1) Тут тоже 1001 > 101, 1001 - 101 = 100
--------
100 Остаток (4)
Результатом у нас будет число 011, то есть, 3, и остаток 3. 100112 = 19, 1012 = 5.
§ Алгоритм для компьютера
Это конечно красиво сверху все, но каков же алгоритм, с которым работает компьютер? Он чрезвычайно прост:
Шаг 0:
0000 | 10011 -- скрытый слой
101
Шаг 1:
0001 | 0011 -- сдвиг на 1 влево
101 Сравниваем, 001 < 101, значит 0
Шаг 2:
010 | 011 -- сдвиг на 1 влево
101 Сравниваем, 010 < 101, значит 0
Шаг 3:
100 | 11 -- сдвиг на 1 влево
101 Сравниваем, 100 < 101, значит 0
Шаг 4:
1001 | 1 -- сдвиг на 1 влево
101 Сравниваем, 1001 >= 101, значит 1 и 1001 - 101 = 100, переносим к следующему