将0,负和正映射到0,1,2的无分支代码

写一个无分支函数,如果两个有符号整数之间的差为零,负或正,则返回0,1或2.

这是一个分支版本:

int Compare(int x, int y)
{
    int diff = x - y;
    if (diff == 0)
        return 0;
    else if (diff < 0)
        return 1;
    else
        return 2;
}

这是一个可能更快的版本,具体取决于编译器和处理器:

int Compare(int x, int y)
{
    int diff = x - y;
    return diff == 0 ? 0 : (diff < 0 ? 1 : 2);
}

你能想出一个没有分支的更快的吗？

摘要

我基准测试的10个解决方案具有相似的性能.实际数字和获胜者取决于编译器(icc/gcc),编译器选项(例如,-O3,-march = nocona,-fast,-xHost)和机器. 佳能的解决方案在许多基准测试中表现良好,但性能优势再次轻微.令我感到惊讶的是,在某些情况下,某些解决方案比使用分支的天真解决方案慢.

1> AnT..：

---

无分支(在语言级别)将负数映射到-1,零到0以及正数到+1的代码如下所示

int c = (n > 0) - (n < 0);

如果您需要不同的映射,您只需使用显式映射来重新映射它

const int MAP[] = { 1, 0, 2 };
int c = MAP[(n > 0) - (n < 0) + 1];

或者,对于请求的映射,使用一些数字技巧

int c = 2 * (n > 0) + (n < 0);

(只要0被映射到0,显然很容易从中生成任何映射.并且代码是可读的.如果0被映射到其他东西,它变得更棘手,更不易读.)

作为附加说明:通过在C语言级别减去一个来比较两个整数是一种有缺陷的技术,因为它通常容易溢出.上述方法的优点在于它们可以立即用于"减法"比较,例如

int c = 2 * (x > y) + (x < y);

---

根据指令集,这不一定是无分支的.

---

滑稽.这是我的第一个答案,我把它丢弃在按位论证上.

---

@Adisak:是的,我完全理解,这显然是我在原始回复中加入"语言水平"评论的原因.所以？

2> Tordek..：

---

int Compare(int x, int y) {
     return (x < y) + (y < x) << 1;
}

编辑:仅按位？猜猜<和>不算数呢？

int Compare(int x, int y) {
    int diff = x - y;
    return (!!diff) | (!!(diff & 0x80000000) << 1);
}

但那有点麻烦-.

编辑:反过来改变.

嗯,再试一次:

int Compare(int x, int y) {
    int diff = y - x;
    return (!!diff) << ((diff >> 31) & 1);
}

但我猜测没有标准的ASM指令!!.此外,<<可以替换+,取决于哪个更快......

有点杂乱很有趣!

嗯,我刚学会了setnz.

我没有检查汇编器输出(但这次我测试了一下),运气好的话可以保存整个指令!:

理论上.我的装配者很生气

subl  %edi, %esi
setnz %eax
sarl  $31, %esi
andl  $1, %esi
sarl  %eax, %esi
mov   %esi, %eax
ret

漫步很有趣.

我需要睡觉.

3> Stephen Cano..：

---

假设2s补码,算术右移,减法没有溢出:

#define SHIFT (CHARBIT*sizeof(int) - 1)

int Compare(int x, int y)
{
    int diff = x - y;
    return -(diff >> SHIFT) - (((-diff) >> SHIFT) << 1);
}

---

Tordek意味着`(2&(-diff >> 30))`相当于` - (( - - diff)>> 31)<< 1)`,而不是它取代整个表达式.

---

另外,`(2&(-diff >> 30))`

4> Paul Hsieh..：

---

两个补码:

#include 
#define INT_BITS (CHAR_BITS * sizeof (int))

int Compare(int x, int y) {
    int d = y - x;
    int p = (d + INT_MAX) >> (INT_BITS - 1);
    d = d >> (INT_BITS - 2);
    return (d & 2) + (p & 1);
}

假设一个理智的编译器,这不会调用系统的比较硬件,也不会使用该语言的比较.要验证:如果x == y则d和p显然为0,因此最终结果为零.如果(x-y)> 0则((x-y)+ INT_MAX)将设置整数的高位,否则将取消设置.因此,当且仅当(x - y)> 0时,p将具有其最低位设置.如果(x-y)<0则其高位将被置位而d将其第二位设置为最低位.

5> Adisak..：

---

返回-1,0,1(cmpu)的无符号比较是GNU SuperOptimizer测试的案例之一.

cmpu: compare (unsigned)
int cmpu(unsigned_word v0, unsigned_word v1)
{
    return ( (v0 > v1) ? 1 : ( (v0 < v1) ? -1 : 0) );
}

SuperOptimizer在指令空间中详尽地搜索将实现给定功能的最佳指令组合. 建议编译器通过其超优化版本自动替换上述函数(尽管并非所有编译器都这样做).例如,在PowerPC编译器编写指南(powerpc-cwg.pdf)中,cmpu函数如附录D第204页中所示:

cmpu: compare (unsigned)
PowerPC SuperOptimized Version
subf  R5,R4,R3
subfc R6,R3,R4
subfe R7,R4,R3
subfe R8,R7,R5

这是非常好的不是它...只有四个减法(并带有进位和/或扩展版本).更不用说它在机器操作码级别上真正无分支.可能有一个PC/Intel X86等效序列同样短,因为GNU Superoptimizer运行X86和PowerPC.

注意,在将符号比较(cmpu)传递给cmpu之前,可以将无符号比较(cmpu)转换为32位比较中的符号比较(cmps),方法是将两个符号输入添加0x80000000.

cmps: compare (signed)
int cmps(signed_word v0, signed_word v1)
{
    signed_word offset=0x80000000;
    return ( (unsigned_word) (v0 + signed_word),
        (unsigned_word) (v1 + signed_word) );
}

这只是一个选项...... SuperOptimizer可能会找到一个更短的cmps,而不必添加偏移量并调用cmpu.

要获取您请求的版本,返回值{1,0,2}而不是{-1,0,1},请使用以下代码,该代码利用SuperOptimized cmps函数.

int Compare(int x, int y)
{
    static const int retvals[]={1,0,2};
    return (retvals[cmps(x,y)+1]);
}