Деление можно делать по Евклиду. Итеративно вычитаем, пока есть что (или не надоест). Но получается дороговато для больших чисел, да и за такт всего один бит считается. Неприятно.

В 1957-58 сразу трое додумались, как делить лучше. SRT алгоритм, который де-факто стандарт в процессорах, устроен интереснее: берём два самых значимых бита делителя и делимого и используем, как ключи для лукап-таблицы, в которой лежат коэффициенты (5 чисел {-2, -1, 0, 1, 2}). На полученный "угаданный"* коэффициент умножается делитель, результат произведения вычитается из делимого. Это наш остаток. Коэффициент сохраняем в регистр, сдвигаем его на 2, как и остаток на 2 влево. Повторяем цикл, только теперь используя в качестве индекса для таблицы два наиболее значимых бита у нашего остатка. Графически - берём по 2 бита с числителя и знаменателя, делим с остатком, результат переносим вниз и к нему дописываем следующие два бита числителя, остаток сохраняем.

*угаданный - он может подобраться и неправильно. Просто тогда ошибка скорректируется на последующих шагах, в чём и заключается вся прелесть метода.

Объяснение очень грубое (не потому, что для хорошего нужен интеллект, а потому, что я вас не люблю), но можете почитать от непосредственно интела, что это за вещь такая. Неплохо графически показывают шаги тут. А здесь фундаментально рассказывают, как оное в железо засовывать.

С SRT теперь можно делить не по одному, а по двум битам за такт, что дало очень ощутимый буст в производительности. Но как раз из-за этого и случился фокус жопы у интела с делением. Тогда проблема была в этой самой лукап-таблице - из 1066 вхождений, 5 забыли заполнить, имея в итоге 0 там, где должен был бы быть +2 — а всё потому, что паттерн для принтера херово скомпилировали.

Статистически, ошибка должна была бы всплывать лишь раз в 27000 лет. Но обнаружили её спустя всего 5 лет после релиза. День новый, а статистика брешет, словно в первый.