Взятие остатка
Вычисление остатка происходит ничуть не быстрее деления (что и не удивительно, т.к. на машинном уровне она посредством деления и осуществляется), поэтому было бы неплохо ускорить этот процесс. Если делитель представляет собой степень двойки (2N = b), а делимое – беззнаковое число, то остаток будет равен N младшим битам делимого числа. Если же делимое – знаковое, необходимо установить все биты, кроме первых N, равными знаковому биту для сохранения знака числа. Причем, если N первых битов равно нулю, все биты результата должны быть сброшены независимо от значения знакового бита.
Таким образом, если делимое – беззнаковое число, то выражение (a % 2N) транслируется в конструкцию: (AND a, 2n-1N), в противном случае трансляция становится неоднозначна – компилятор может вставлять явную проверку на равенство нулю с ветвлением, а может использовать хитрые математические алгоритмы, самый популярный из которых выглядит так: DEC x\ OR x, -N\ INC x. Весь фокус в том, что если первые N бит числа x равны нулю, то все биты результата кроме старшего, знакового бита, будут гарантированно равны одному, а (OR x, - N) принудительно установит в единицу и старший бит, т.е. получится значение, равное, –1. А (INC –1) даст ноль! Напротив, если хотя бы один из N младших битов равен одному, заема из старших битов не происходит и (INC x) возвращает значению первоначальный результат.
А можно ли вычислять остаток посредством умножения и битовых сдвигов? Теоретически возможно, но не для всех делителей. Делитель обязательно должен быть кратен , где k и t – некоторые целые числа. Тогда остаток будет можно вычислить по следующей формуле:
К сожалению, ни один из трех рассматриваемых компиляторов не использует этот трюк для оптимизации кода, но выполнять быстрый поиск остатка для делителей, кратных степени двойки, умеет каждый из них (невелика премудрость).
