12

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;
}

在这种情况下，我只得到一个比较。

有什么办法可以完全避免比较吗？

编辑 可能的重复不会给出问题的答案，因为所有答案都是 C++，使用比较（我应该避免）或不返回-1, +1, 0.

4

5 回答 5

44

首先，整数比较非常便宜。它的分支可能很昂贵（由于分支预测错误的风险）。

我已经使用 gcc 4.7.2 在 Sandy Bridge 盒子上对您的功能进行了基准测试，每次调用大约需要 1.2ns。

以下是大约 25% 的速度，每次调用大约 0.9ns：

int sign(int x) {
    return (x > 0) - (x < 0);
}

上面的机器代码是完全无分支的：

_sign:
    xorl    %eax, %eax
    testl   %edi, %edi
    setg    %al
    shrl    $31, %edi
    subl    %edi, %eax
    ret

有两点值得指出：

  1. 性能的基础水平非常高。
  2. 消除分支确实可以提高性能，但不会显着。
于 2013-01-30T20:21:10.783 回答
6 
int sign(int x)
{
    // assumes 32-bit int and 2s complement signed shifts work (implementation defined by C spec)
    return (x>>31) | ((unsigned)-x >> 31);
}

第一部分 ( x>>32) 为负数提供 -1，为 0 或正数提供 0。如果 x > 0 或等于 INT_MIN，则第二部分为您提供 1，否则为 0。或者给你正确的最终答案。

还有 canonical return (x > 0) - (x < 0);，但不幸的是大多数编译器会使用分支来生成代码，即使没有可见的分支。您可以尝试手动将其转换为无分支代码，如下所示：

int sign(int x)
{
    // assumes 32-bit int/unsigned
    return ((unsigned)-x >> 31) - ((unsigned)x >> 31);
}

这可以说比上面更好，因为它不依赖于实现定义的行为，但有一个微妙的错误，即它将为 INT_MIN 返回 0。

于 2013-01-30T19:48:29.660 回答
2 
int sign(int x) {    
    return (x>>31)|(!!x);
}
于 2013-08-07T11:50:01.397 回答
0

Ifs(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

因此，您可以通过以下方式组合它们：

s(-x) - s(x)
于 2013-01-30T19:47:21.847 回答
-1 
int i = -10;
if((i & 1 << 31) == 0x80000000)sign = 0;else sign = 1;
//sign 1 = -ve, sign 0 = -ve
于 2013-01-30T19:44:07.403 回答