在C中有一个符号函数:
int sign(int x)
{
if(x > 0) return 1;
if(x < 0) return -1;
return 0;
}
不幸的是,比较成本非常高,所以我需要修改函数以减少比较的次数。
我尝试了以下方法:
int sign(int x)
{
int result;
result = (-1)*(((unsigned int)x)>>31);
if (x > 0) return 1;
return result;
}
在这种情况下,我只得到一个比较。
有没有办法避免比较呢?
EDITpossible duplicate不给予问题的答案,因为所有答案都是C++,使用比较(我应该避免)或不返回-1
,+1
,0
。
5条答案
按热度按时间xzlaal3s1#
首先,整数比较非常便宜。它的 * 分支 * 可能是昂贵的(由于分支预测错误的风险)。
我已经用gcc 4.7.2在桑迪Bridge上对你的函数进行了基准测试,每次调用大约需要1.2ns。
以下是大约25%的速度,每次调用大约0.9ns:
上面的机器码是完全无分支的:
有两件事值得指出:
1.业绩的基础水平非常高。
1.消除分支确实提高了这里的性能,但并不显著。
yruzcnhs2#
第一部分(
x>>32
)为负数提供-1,为0或正数提供0。如果x > 0或等于INT_MIN,则第二部分给出1,否则为0。或者给你正确的最终答案。还有规范的
return (x > 0) - (x < 0);
,但不幸的是,大多数编译器将使用分支来生成代码,即使没有可见的分支。您可以尝试手动将其转换为无分支代码:它可以说比上面的更好,因为它不依赖于实现定义的行为,但有一个微妙的错误,它将返回0的INT_MIN。
yzxexxkh3#
piztneat4#
如果
s(x)
是一个返回x
的符号位的函数(您通过((unsigned int)x)>>31
实现了它),则可以以某种方式合并s(x)
和s(-x)
。下面是一个“真值表”:x > 0:s(x)= 0; s(-x)= 1;您的函数必须返回1
x < 0:s(x)= 1; s(-x)= 0;您的函数必须返回-1
x = 0:s(x)= 0 s(-x)= 0;函数必须返回0
因此,您可以按以下方式合并它们:
hec6srdp5#