Bithacks：确定值是小于、大于还是等于某个值

Question

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

一种天真的方法是使用 if-then-else 分支来检查这一点，但这不会以最佳方式工作，因为处理器的分支预测器会搞砸。我正在尝试仅使用算术/逻辑评估以及按位运算来实现此比较，但老实说，我的大脑现在卡住了。

我将调用函数 f(x, y)。如果 x < y，该函数将 return 1； 2、如果x==y；或 3，如果 x > y.

我的一个想法是评估：

x = 3 * (x > y)

当 x > y 时 return 3，否则为 0。如果 x == 0 使用一些按位运算符和条件 x == y 或 x < y，可能会有一个操作 returns 1 或 2，但我还没有找到任何这样的操作组合实现我所需要的。

最后，我正在寻找任何函数 f(x, y)，它会以尽可能少的操作给出我的结果，无论是否使用 bithacks；它只需要快。因此，如果您有任何其他我可能没有考虑过的想法，也非常感谢为我指出另一个解决方案。

Answer 1

一个选项是：

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)=%d\n",x,y,f(x,y));
    return 0;
}

这依赖于 int 类型是 32 位数量。

您可能还想查看 SIMD 指令（例如 x86 上的 SSE 或 Arm 上的 Neon），因为它们可能会帮助您加速代码。

Answer 2

只需减去 2 个变量 x 和 y。

您将获得：

如果x<y结果是res<0
如果x>y结果是res>0
如果 x==y 结果是 res==0。

在宏中实现

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

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

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

P.S。这与许多标准函数的结果相同，如 strcmp().

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

只存储值的差异，单个值，允许您保留信息，甚至用于以后的评估，包含您可能需要的所有元素。

Answer 3

以下表达式将执行您想要的操作。

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

在 x86-64 上这个 compiles to a fairly-efficient code using SETcc instead of branches:

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

在 ARM 上：

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

Bithacks：确定值是小于、大于还是等于某个值

Bithacks: Determine whether value is less, greater, or equal to some value

c

algorithm

optimization

bit-manipulation