Беседы о программировании 004 :: Остаток от деления на степень двойки ± 1

Рассматривается алгоритмический трюк, позволяющий выполнить быстрый поиск остатка от деления на числа вида 2n-1 и 2n+1. Показана общая идея, рассмотрены частные случаи деления 32-битовых и 64-битовых чисел, выполнено сравнение с обычной процедурой нахождения остатка.

Читать далее «Беседы о программировании 004 :: Остаток от деления на степень двойки ± 1»

Беседы о программировании 002 :: Замена целочисленного деления на умножение и сдвиг (теория)

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

Читать далее «Беседы о программировании 002 :: Замена целочисленного деления на умножение и сдвиг (теория)»