Неподписанный modulos: альтернативный подход?

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

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

В a% b , если какой-либо из операндов беззнаковый , оба преобразуются в беззнаковый . Это означает, что если 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, как это проще (а может и нет ?!). Это здесь для протокола.

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

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

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

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

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

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

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

В вашей оригинальной функции вы могли возвращаться после завершения цикла 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.

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

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

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

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

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

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

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

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

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

Кроме цикла 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.

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

Если вы сможете изучить, таких вещей будет больше.

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

((a % b) + b) % b

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