c - Bithacks : Determine whether value is less, 大于或等于某个值

Question

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

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

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

我的一个想法是评估:

x = 3 * (x > y)

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

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

Answer 1

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

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