代码之家 › 专栏 › 技术社区 › Alex

C中整数的快速符号

signed-integer micro-optimization c

17

Alex · 技术社区 · 13 年前

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

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

有什么办法可以避免比较吗?

编辑 possible duplicate 不给出问题的答案,因为所有答案都是C++,使用比较(我应该避免)或不返回 -1 , +1 , 0 .

5 回复 | 直到 3 年前

1

50

NPE 13 年前

首先,整数比较非常便宜。it is 的常用口语形式分岔这可能很昂贵(由于分支预测失误的风险)。

我使用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

有两点值得指出:

性能的基础水平非常高。
消除分支确实可以提高这里的性能,但不会显著提高。

2

6

Chris Dodd 13 年前

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>,则第二部分为1;0或等于INT_MIN,否则为0。或者给你正确的最终答案。

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

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

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

3

1

Bruce 13 年前

int sign(int x) {    
    return (x>>31)|(!!x);
}

4

0

Community Mohan Dere 6 年前

如果 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

因此,您可以按以下方式组合它们:

s(-x) - s(x)

5

-2

Aniket Inge 13 年前

int i = -10;
if((i & 1 << 31) == 0x80000000)sign = 0;else sign = 1;
//sign 1 = -ve, sign 0 = -ve