Беззнаковые модули: альтернативный подход?

Question

Мне нужно оптимизировать эту действительно крошечную, но надоедливую функцию.

unsigned umod(int a, unsigned b)
{
    while(a < 0)
        a += b;

    return a % b;
}

Прежде чем выкрикнуть «Вам не нужно оптимизировать его», имейте в виду, что эта функция вызывается 50% всего времени жизни программы, так как она вызывается 21495808 раз для наименьшего контрольного теста.

Функция уже встроена компилятором, поэтому не предлагайте добавлять ключевое слово inline.

Answer 1

Кроме цикла while, Не уверен, что операция% может быть оптимизирована в целом, но оптимизация может происходить на основе значений для a & b.

Если в эти 21495808 раз выполняется операция.

Если шансы передать значение для a, которое меньше, чем b (a if ( abs(a) < b ) // not specifically the abs function, can be your own implementation. return 0; else return a%b; Если b является степенью 2 для хотя бы 80% случаев, мы можем использовать побитовые операторы, как в

return ( abs(a) & (b-1) );

Если ожидается, что числа будут меньше, чем это, это ухудшит производительность, так как нам нужно проверить, является ли b степенью 2 [даже после использования битовых операторов для одного и того же] для всего.

Даже функциональность для достижения abs (a) может быть оптимизирована с помощью побитовых операторов, со своими собственными ограничениями, но это быстрее, чем проверка того, является ли a <0. </p>

n = (a ^ (a >> 31)) - (a >> 31); // instead of n = a < 0 ? -a : a;

Было бы больше таких вещей, если бы вы могли исследовать.

Answer 2

Если a и b оба намного меньше, чем int, то вы можете просто добавить достаточно большое значение, кратное b, к каждому значению, прежде чем модифицировать.

unsigned umod(int a, unsigned b)
{
    return (unsigned)(a + (int)(b * 256)) % b;
}

Конечно, этот трюк не работает, если a + (b * 256) может переполниться, но для многих случаев, которые я вижу для этого кода, вы можете быть уверены, что он никогда не будет.