Фантазии о Вселенной и мой личный сайт
Двоичное деление столбиком

Двоичное деление столбиком

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

Алгоритм

Вначале, мы берем самый старший разряд и начинаем делить на более младший. Итак, нужно разделить число 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 = 1910, 1012 = 510

Алгоритм для компьютера

Это конечно красиво сверху все, но каков же алгоритм, с которым работает компьютер? Он чрезвычайно прост:

Шаг 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. Все верно.