§ Описание алгоритма

Разговор сегодня пойдет про деление столбиком. Да, то самое деление столбиком, которое учили в школе. Я расскажу о технике, о которой знают многие, и которая также применяется для того, чтобы разделить два целых числа в информатике.
Вначале, мы берем самый старший разряд и начинаем делить на более младший. Итак, нужно разделить число 10011₂ на 101₂.

 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. 10011₂ = 19, 101₂ = 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, переносим к следующему

Шаг 5:

1001 | -- сдвиг был последним
 101   Сравниваем, 1001 >= 101, значит 1, 1001 - 101 = 100

Итак, вышло 00011 и остаток 100. Все верно.