C语言 Bithacks:确定value是否小于、大于或等于某个值

Question

我正在研究的一个算法必须经常检查某个任意整数值'x'是否小于、大于或等于另一个任意整数值'y'。我实现它的语言是c。

一种简单的方法是使用if-then-else分支来检查这一点，但这不是最佳工作，因为处理器的分支预测器会混乱。我试图实现这种比较只使用算术/逻辑计算以及位操作，但是，老实说，我的大脑现在卡住了。

我将调用函数f(x, y)。函数将返回1，如果x <y;2，如果x> y

我的一个想法是评估:

x = 3 * (x > y)

当x> y时返回3，否则返回0。如果x == 0，使用一些位运算符，并且条件x == y或x <可以有一个返回1或2的操作;，但是我还没有发现任何这样的操作组合来达到我所需要的。

最后，我正在寻找任何函数f(x, y)，它将以最少的操作次数给我结果，无论是否有双叉;只要速度快就行了。因此，如果您有任何我可能没有考虑到的其他想法，也非常感谢您指出我的另一个解决方案。

Answer 1

下面的表达式将满足您的要求。

1 + (x >= y) + (x > y)

在x86-64上，使用SETcc而不是分支编译成相当高效的代码:

compare(int, int):
    xorl    %edx, %edx
    cmpl    %esi, %edi
    setg    %al
    setge   %dl
    movzbl  %al, %eax
    leal    1(%rdx,%rax), %eax
    ret

在手臂

:

compare(int, int):
    cmp r0, r1
    ite lt
    movlt   r0, #1
    movge   r0, #2
    it  gt
    addgt   r0, r0, #1
    bx  lr

Answer 2

简单地减去两个变量x和y。

你会得到:

1. 如果x<y结果为res<0
2. 如果x>y的结果是res>0
3. if x==y result is res==0 .

在宏 中实现

#define Chk(x, y) ((x)-(y))

另一个优点是您可以简单地使用!运算符来检查相等或不相等:

if (!Chk(x, y))
{
    // x == y
}
else
{
    // x != y
}

注:这与strcmp()等许多标准函数的结果相同。

P.P.S.请考虑处理器的机器指令cmp，至少对于我所知道的所有CPU类型，在两个操作数之间执行减法并设置标志以反映结果。在C语言中，即使只是比较两个值，也会产生包含cmp指令和jz、jl等分支的代码。

仅存储值的差异，即单个值，允许您保留信息，甚至用于以后的求值，保存您可能需要的所有元素。

Answer 3

一个选项是:

int f(int x,int y)
{
    return ((x-y)>>31)-((y-x)>>31) + 2;
}

int main(int argc, char *argv[])
{
    int x,y;
    for(x=-3;x<=3;x++)
    for(y=-3;y<=3;y++)
        printf("x=%d y=%d f(x,y)=%dn",x,y,f(x,y));
    return 0;
}

这依赖于int类型是一个32位的量。

您可能还需要查看SIMD指令(例如x86上的SSE或Arm上的Neon)，因为这些可以帮助您加速代码。