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

Question

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

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

    return a % b;
}

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

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

Answer 1

Это позволяет избежать зацикливания:

int tmp = a % b;
if (tmp < 0) tmp += b;

Обратите внимание, что и a, и b должны быть подписаны.

Answer 2

Это должно сделать это:

unsigned umod(int a, unsigned b)
{
    if (a < 0)
    {
        unsigned r = (-a % b);
        if (r)
            return b - r;
        else
            return 0;
    }
    else
        return a % b;
}

Проверено на соответствие оригиналу. Ограничение состоит в том, что a > INT_MIN на машинах с дополнением 2s.

Answer 3

Использование ~:)

unsigned umod(int a, unsigned b)
{
    if (a<0) return b-1-~a%b;
    return a%b;
}

% имеет более высокий приоритет, чем -

Если можно вернуть b вместо 0, когда -a кратно b, вы можете сохранить некоторые операции

unsigned umod(int a, unsigned b)
{
    if (a<0) return b - (-a % b);
    return a%b;
}

слегка игра в гольф:)

unsigned umod(int a, unsigned b)
{
return(a<0)?b-(-a%b):a%b;
}

Вот итоговая сборка

1    .globl umod3
2       .type   umod3, @function
3    umod3:
4    .LFB3:
5       .cfi_startproc
6       testl   %edi, %edi
7       js      .L18
8       movl    %edi, %eax
9       xorl    %edx, %edx
10      divl    %esi
11      movl    %edx, %eax
12      ret
13      .p2align 4,,10
14      .p2align 3
15   .L18:
16      movl    %edi, %eax
17      xorl    %edx, %edx
18      negl    %eax
19      divl    %esi
20      subl    %edx, %esi
21      movl    %esi, %edx
22      movl    %edx, %eax
23      ret

Answer 4

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

unsigned umod(int a, unsigned b){
    while(a>0)a-=b;
    while(a<0)a+=b;
    return a;
}

Answer 5

Портативное издание, все еще с одним делением, без ветвления и без умножения:

unsigned umod(int a, unsigned b) {
    int rem = a % (int) b;
    return rem + (-(rem < 0) & b);
}

Answer 6

Вот тот, который работает во всем диапазоне без знака без ветвления, но использует умножения и 2 деления

unsigned umod(int a, unsigned b)
{
    return (a>0)*a%b+(a<0)*(b-1-~a%b);
}

Answer 7

int temp;

temp= (a > 0)? ( a % b ) :   b -( (-a) % b ) ;

код ниже:

int main()
{
int a;
unsigned b;
int temp;
printf("please enter an int and a unsigned number\n");
scanf("%d",&a);
scanf("%u",&b);
modulus(a,b);
temp= (a > 0)? ( a % b ) :   b -( (-a) % b ) ;
printf("\n temp is %d", temp);
return 0;
}
void modulus(int x,unsigned y)
{
int c;
if(x>0)
{
c=x%y;
printf("\n%d\n",c);}
else
{
while(x<0)
x+=y;
printf("\n%d\n",x);}
}


./a.out
please enter an int and a unsigned number
-8 3

1

 temp is 1

Answer 8

В a % b, если любой из операндов равен unsigned, оба преобразуются в unsigned. Это означает, что если a отрицательно, вы получите значение по модулю UINT_MAX + 1 вместо a. Если UINT_MAX+1 делится поровну на b, то все в порядке, и вы можете просто вернуть a % b. Если нет, вы должны сделать по модулю int тип.

unsigned int umod(int a, unsigned int b)
{
    int ret;
    if (a >= 0) return a % b;
    if (b > INT_MAX) return a + b;
    ret = a % (int)b;
    if (ret < 0) ret += b;
    return ret;
}

Редактировать : обновлено, но вы должны использовать ответ caf, поскольку это проще (а может и нет ?!). Это здесь для записи.

Answer 9

В исходной функции вы могли вернуться после завершения цикла while для отрицательных чисел, пропустив мод. Это в том же духе, заменив цикл с умножением - хотя это может быть сделано, чтобы иметь меньше символов ...

unsigned int umod2(int a, unsigned int b)
{
    return (a < 0) ? a + ((-a/b)+1)*b : a % b;
}

Вот версия цикла:

unsigned int umod2_works(int a, unsigned int b)
{
    if (a < 0)
    {
        while (a < 0)
            a += b;
        return a;
    } else {
        return a % b;
    }
}

Оба были протестированы на соответствие исходной функции OP.

Answer 10

Мое предпочтительное решение - мод дважды. Я не пробовал это в C / C ++ или с unsigned, но мои тесты работают на Java:

((a % b) + b) % b

Преимущество не в ветвлении, а в простоте. Недостатком является двойной мод. Я не сравнивал производительность, но, насколько я понимаю, в наши дни производительность ухудшается.