无符号模数:替代方法？

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_MIN2s补充机器.

Answer 3

使用〜:)

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

该%优先级高于-

如果在-a是b的倍数时可以返回b而不是0,则可以保存一些操作

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