Какой эффективный способ получить наименьший неотрицательный остаток по модулю n в C? - PullRequest
Новая
       12

Какой эффективный способ получить наименьший неотрицательный остаток по модулю n в C?

4 голосов
/ 25 апреля 2010

Есть ли эффективный способ получить наименьший неотрицательный остаток по модулю n, где n положительно, в C?

Это довольно легко, если число неотрицательное, тогда это просто% n (где a - неотрицательное целое число).

Однако, когда a отрицательно, кажется, что поведение в C89 определяется реализацией (спасибо kennyTM). То есть -2% 11 = -2 или 9.

Ответы [ 4 ]

9 голосов
/ 25 апреля 2010

Вы можете просто проверить, является ли результат отрицательным, и затем действовать соответствующим образом: 

int mod(int n, int m) {
   int r = n % m;
   if (r < 0)
      return r + m;
   else
      return r;
}

Или без if-then-else и в виде одного выражения: 

r = ((n % m) + m) % m;
8 голосов
/ 25 апреля 2010

Кроме того, в C99 поведение определяется как раздражающее: -2% 11 = -2.

В целом (т. Е. n % m, когда m не является постоянным, а диапазон n не ограничен), вы, вероятно, не можете добиться большего успеха, чем обычный 

res = ((n % m) + m) % m

Может быть интересно сравнить это со следующим на вашей платформе; одна ветка может выиграть против дополнительного модуля: 

res = n % m;
if (res < 0)  res += m;
0 голосов
/ 25 апреля 2010

Немногие процессоры реализуют остаток в оборудовании, скорее он синтезируется из деления и умножения. Так что это на самом деле не громоздкое повторное воплощение с точки зрения машины: 

int qm = n / m * m; // a positive or negative multiple of m, rounded up or down
if ( qm <= n ) return n - qm; // usual definition of %
else return n - qm + m; // most common definition of -%, with adjustment

Микро-оптимизация условного + также может быть полезной. Это может быть быстрее или медленнее на вашей машине, но это будет работать: 

int rem = n - n / m * m;
return rem + m & -( rem < 0 );

Общая стоимость: один обычный по модулю плюс один сдвиг вправо (для генерации -(rem<0)), один бит и, и одно добавление.

0 голосов
/ 25 апреля 2010

Как насчет 

if (a > 0)
    return a % n;
if (a < 0)
{
    r = n - (-a % n);
    if (r == n)
        return 0;
    return r;
}

Если a <0, то <code>r = -a % n - это значение в [0, n), такое что k * n + r = -a для некоторого целого числа k. Тогда n - r является значением в (0, n], и, поскольку -r = a + k * n, мы имеем n - r = a + (k + 1) * n или a = (n - r) + (-k - 1) * n. Из этого вы можете видеть, что n - r является модулем a, и поскольку оно находится в (0, n], оно неотрицательно.

Наконец, вы хотите, чтобы результат был в диапазоне [0, n), а не в (0, n]. Чтобы убедиться в этом, мы проверяем, если r равно n, и если да, возвращаем 0. (который имеет модуль курса-n-эквивалентный n)

...