C中整数的快速符号

5vf7fwbs  于 2023-05-16  发布在  其他
关注(0)|答案(5)|浏览(168)

在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+10

xzlaal3s

xzlaal3s1#

首先,整数比较非常便宜。它的 * 分支 * 可能是昂贵的(由于分支预测错误的风险)。
我已经用gcc 4.7.2在桑迪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.业绩的基础水平非常高。
1.消除分支确实提高了这里的性能,但并不显著。

yruzcnhs

yruzcnhs2#

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。或者给你正确的最终答案。
还有规范的return (x > 0) - (x < 0);,但不幸的是,大多数编译器将使用分支来生成代码,即使没有可见的分支。您可以尝试手动将其转换为无分支代码:

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

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

yzxexxkh

yzxexxkh3#

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

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
因此,您可以按以下方式合并它们:

s(-x) - s(x)
hec6srdp

hec6srdp5#

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

相关问题