我需要优化这个非常微小但很麻烦的函数。
unsigned umod(int a, unsigned b)
{
while(a < 0)
a += b;
return a % b;
}
在你喊出“你不需要进行优化”的之前,请记住这个函数在整个程序生命周期中被调用了50%,因为它在最小的测试用例基准测试中被调用了21495808次。
由于编译器已经将该函数内联,因此请不要建议添加inline
关键字。
我需要优化这个非常微小但很麻烦的函数。
unsigned umod(int a, unsigned b)
{
while(a < 0)
a += b;
return a % b;
}
在你喊出“你不需要进行优化”的之前,请记住这个函数在整个程序生命周期中被调用了50%,因为它在最小的测试用例基准测试中被调用了21495808次。
由于编译器已经将该函数内联,因此请不要建议添加inline
关键字。
这样可以避免循环:
int tmp = a % b;
if (tmp < 0) tmp += b;
请注意,a和b都需要是有符号数。
int tmp = a % b; return tmp + b * (tmp < 0);
更快。 (该代码的作用为对整数a和b进行取模运算,并将结果调整至非负整数范围内) - LiraNunaa=-10
且b=3
时,原帖得到2,但是这个结果是0。 - caf(-10) % 3U
不会得到 -1。 - cafumod(-10, 3) == 2
: return a % (int)b + b * (a < 0);
,尽管这会失去 b 范围的一半。 - cobbalunsigned 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
。
>= INT_MIN
改成了 > INT_MIN
。现在是正确的。 - Alok Singhala >= 0
的情况,它应该至少执行完全相同的指令。顺便问一下,你是如何使用 gprof 来分析内联函数的呢? - caf0 == b
是可以的,所以我将其更改为 return b - (-a % b);
以减少一个分支。 - LiraNunaunsigned 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
a
的否定是一个简单的 -a ;) (结果为return b- (-a%b);
) - LiraNunagcc
在函数末尾创建了一个看似无用的movl
指令 - 我也看到了这个(它可以只执行movl %esi,%eax
)。我想知道是否有一些微妙的架构原因? - cafret
前面的最后两个助记符(第 21
和 22
行)。这些行将最终结果从 %esi
移动到 %edx
,然后从 %edx
移动到 %eax
- 这可以通过仅将 %esi
移动到 %eax
来完成。 - caf由于循环版本似乎相当快,让我们尝试消除除法 :)
unsigned umod(int a, unsigned b){
while(a>0)a-=b;
while(a<0)a+=b;
return a;
}
a
和b
差别不大的情况。但是当a = MAX_INT
,b = 2
时,代码会非常慢。无论如何,非标准方法加1。 - Vladunsigned umod(int a, unsigned b) {
int rem = a % (int) b;
return rem + (-(rem < 0) & b);
}
__asm__ __volatile__
? - asveikaucc
寄存器,因为它与 FLAGS
寄存器有关。有时在使用内联汇编进行原子操作时,这会给我带来麻烦。无论如何,我更喜欢 C 语言版本。 - asveikauunsigned 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 的原始函数匹配。
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的答案,因为它更简单(或者也许不是?!)。这里仅供记录。
b
超出了 int
的范围怎么办? - cafint 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
这是一个适用于整个无符号范围的工作方法,而且不需要分支,但它使用乘法和2次除法。
unsigned umod(int a, unsigned b)
{
return (a>0)*a%b+(a<0)*(b-1-~a%b);
}
unsigned umod(int a, unsigned b)
{
return (unsigned)(a + (int)(b * 256)) % b;
}
a % b
不起作用吗? - Anon.b
始终为正数(非零),并且它可以(而且确实)达到 UINT_MAX(因此不需要有符号转换)。 - LiraNuna