Поскольку большинство современных процессоров могут выполнять умножение намного, намного быстрее, чем деление, часто можно ускорить операции деления и модуля, где дивиденд является известной малой константой, заменяя деление одним или двумя умножениями и несколькими другими быстрыми операции (такие как сдвиг и сложение).
Для этого требуется вычислить во время компиляции некоторые числа волхвов c, зависящие от дивиденда; К счастью, большинство современных компиляторов знают, как это сделать, поэтому вам не нужно ничего делать, чтобы воспользоваться этим. Просто позвольте вашему компилятору сделать тяжелую работу за вас, как @ chux предлагает в отличный ответ .
Вы можете помочь компилятору, используя неподписанные типы; для некоторых дивидендов сложнее заменить подписанное деление и модуль.
Базовый c план оптимизации модуля выглядит следующим образом:
Если у вас была точная арифметика c, вы может заменить x % p на p * ((x * (1/p)) % 1). Для константы p, 1/p может быть предварительно вычислено во время компиляции. Операция %1 просто состоит в отбрасывании дробной части, которая представляет собой просто сдвиг вправо. Таким образом, это заменяет деление на два умножения, и если p имеет только несколько установленных битов, умножение на p может быть дополнительно оптимизировано в несколько сдвигов влево.
Мы можем сделать это вычисление с арифметика с фиксированной точкой c, использующая преимущество того факта, что большинство процессоров выдают результат двойного размера для целочисленного умножения. Поскольку нам не важна целочисленная часть внутреннего умножения, и мы знаем, что результат внешнего умножения должен быть меньше p, нам нужно только зарезервировать биты ceil (log2 p) для целочисленной части вычисления. оставляя остальные биты для дроби. И это может дать нам достаточную точность для правильной обработки возможного диапазона значений x, особенно если x имеет ограниченный диапазон (например, uint8_t или даже uint16_t). Ключ находит позицию фиксированной точки, которая минимизирует ошибку в представлении 1/p.
Для многих небольших значений p это работает. Для других есть альтернативное (но более медленное) решение, которое включает в себя оценку q = x/p с использованием умножения на обратное, а затем вычисление x - q * p. Если оценка q может быть гарантирована как правильная или отклоненная на единицу в известном направлении, нам нужно только исправить окончательное вычисление путем условного прибавления или вычитания p; это может быть достигнуто без ветки на многих современных процессорах. (Направление ошибки известно, поскольку оно будет зависеть только от того, было ли выбранное нами приближение для обратного делимого слишком маленьким или слишком большим.)
В очень конкретном случае c из x % 10, где x - это uint_8, вы можете добиться большего успеха, чем выше, используя 256-байтовую таблицу поиска. Это было бы целесообразно, если бы вы выполняли операцию модуля в узком l oop для большого числа значений, и даже тогда вы захотите тщательно профилировать, чтобы убедиться, что это улучшение.
Я сомневаюсь, что это лучшая трата вашего времени; возможно, в вашем приложении гораздо более полезные возможности оптимизации.