无符号取模运算：另一种方法？

Question

我需要优化这个非常微小但很麻烦的函数。

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

    return a % b;
}

在你喊出“你不需要进行优化”的之前，请记住这个函数在整个程序生命周期中被调用了50％，因为它在最小的测试用例基准测试中被调用了21495808次。

由于编译器已经将该函数内联，因此请不要建议添加inline关键字。

- LiraNuna

---

只是 a % b 不起作用吗？ - Anon.

@Anon：因为答案必须是正数，但如果a是负数，a % b也是负数。 - Jonathan Leffler

如果您的程序调用函数来处理大量相关值，您可以考虑优化计算，以便根本不需要执行除法。 - Tronic

将来，这个网站可能会派上用场：http://refactormycode.com/ - 它专门为这些问题而制作。 - Ponkadoodle

我可以保证 b 始终为正数（非零），并且它可以（而且确实）达到 UINT_MAX（因此不需要有符号转换）。 - LiraNuna

Answer 1

这样可以避免循环：

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

请注意，a和b都需要是有符号数。

- Tronic

---

这段代码 int tmp = a % b; return tmp + b * (tmp < 0); 更快。 （该代码的作用为对整数a和b进行取模运算，并将结果调整至非负整数范围内） - LiraNuna

这个结果和原帖的不一样。例如，当a=-10且b=3时，原帖得到2，但是这个结果是0。 - caf

(-10) % 3U 不会得到 -1。 - caf

更新版本 umod(-10, 3) == 2: return a % (int)b + b * (a < 0);，尽管这会失去 b 范围的一半。 - cobbal

+1 表示这将失去 b 的一半范围，这将违背声明 b 为无符号的目的。 - legends2k

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。

- caf

---

@wallacoloo：他把代码中的 >= INT_MIN 改成了 > INT_MIN。现在是正确的。 - Alok Singhal

糟糕，错过了一个边缘情况 - 已更新以修复，但现在它不再那么干净了。 - caf

这真的很奇怪 - 因为对于 a >= 0 的情况，它应该至少执行完全相同的指令。顺便问一下，你是如何使用 gprof 来分析内联函数的呢？ - caf

就我测试而言（gcc 4.3.2，-O3），我的版本比循环版本快6到7倍，即使在-1073741823和1073741824之间的“a”值均匀分布的情况下也是如此。当所有“a”值都为正数时，它运行相同。 - caf

在我的情况下，0 == b 是可以的，所以我将其更改为 return b - (-a % b); 以减少一个分支。 - LiraNuna

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

- John La Rooy

---

嗯，你似乎非常关注这个高尔夫球的事情...明白了吗...钉住了...;) - Filip Ekberg

这个操作比咖啡厅答案少，特别是如果 a 的否定是一个简单的 -a ;) （结果为return b- (-a％b);） - LiraNuna

是的，那也是我的原始答案，在添加额外条件以使其精确匹配问题中的代码行为之前。顺便说一下，有趣的是，gcc在函数末尾创建了一个看似无用的movl指令 - 我也看到了这个（它可以只执行movl %esi，%eax）。我想知道是否有一些微妙的架构原因？ - caf

@caf，显然divl将模数的结果放入edx中（除非为零）。调用约定要求将其移位到eax。 - John La Rooy

它确实有作用，但我说的是 ret 前面的最后两个助记符（第 21 和 22 行）。这些行将最终结果从 %esi 移动到 %edx，然后从 %edx 移动到 %eax - 这可以通过仅将 %esi 移动到 %eax 来完成。 - caf

Answer 4

由于循环版本似乎相当快，让我们尝试消除除法 :)

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

- John La Rooy

---

这是一个很好的优化，适用于a和b差别不大的情况。但是当a = MAX_INT，b = 2时，代码会非常慢。无论如何，非标准方法加1。 - Vlad

@Vlad，由于LiraNuna表示原始循环版本在实际测试中表现良好，我想知道是否值得尝试，因为我们不知道a和b的分布情况。 - John La Rooy

仅仅因为你不理解除法吗？ - President James K. Polk

Answer 5

便携版仍然只有一次除法，没有分支和乘法：

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

- C. K. Young

---

这种方法比在C代码中进行除法和条件判断更好吗？此外，可能需要使用clobber args吗？也许需要使用__asm__ __volatile__？ - asveikau

@asveikau：不，由于限制，不会有任何覆盖。此外，不需要volatile，因为编译器的排序将保证正确的结果。如果您可以确保没有分支，则可以在C代码中执行条件操作。（我的便携式版本就是这样做的。） - C. K. Young

我在想你可能需要破坏 cc 寄存器，因为它与 FLAGS 寄存器有关。有时在使用内联汇编进行原子操作时，这会给我带来麻烦。无论如何，我更喜欢 C 语言版本。 - asveikau

当然你可以使用#ifdef指令来编写汇编版本。 - John La Rooy

@gnibbler：你可以这样做，但为什么要这样呢？在gcc下，C版本生成的代码甚至比我写的汇编版本还要好。 - C. K. Young

Answer 6

在您的原始函数中，对于负数，您可以在 while 循环完成后返回，从而跳过 mod。这是在相同的精神下，用乘法替换循环 - 尽管它可以使字符更少...

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 的原始函数匹配。

- mtrw

---

抱歉，我的意思是“用除法和乘法代替循环”。我不确定哪个更快，但这至少是正确的。 - mtrw

不会让它更快，你正在添加另一个分支，从而减慢例程的速度。我得到了均匀分布的数字作为输入。 - LiraNuna

我很惊讶另一个分支比模块慢。无论如何，Alok的答案看起来是迄今为止最好的。 - mtrw

如果写得正确，那就不是另一个分支。 - Stephen Canon

Answer 7

在`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的答案，因为它更简单（或者也许不是？！）。这里仅供记录。

- Alok Singhal

---

如果 b 超出了 int 的范围怎么办？ - caf

Answer 8

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

- Vijay

---

我不太明白……你能告诉我，我在这里表现出了哪些良好的礼仪吗？ - Vijay

Answer 9

这是一个适用于整个无符号范围的工作方法，而且不需要分支，但它使用乘法和2次除法。

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

- John La Rooy

Answer 10

如果a和b都比int小得多，那么在取模之前，您可以将足够大的倍数b添加到每个值上。

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

当然，如果a +（b * 256）可能会溢出，这个技巧就不起作用了，但对于我可以看到的这段代码的许多用途，您可以确信它永远不会发生。

- John Knoeller