网点code映射零，负数和积极的为0，1，2 [英] Branchless code that maps zero, negative, and positive to 0, 1, 2

问题描述

收件返回0，1，或2如果两个符号整数之间的差是零，负的或正一网点功能

下面是与分支版本：

  INT比较（INT X，int y）对
{
    INT差异=说明X  -  Y;
    如果（差异== 0）
        返回0;
    否则如果（差异℃，）
        返回1;
    其他
        返回2;
}
 

下面是一个可能更快取决于编译器和处理器的版本：

  INT比较（INT X，int y）对
{
    INT差异=说明X  -  Y;
    返回的diff == 0？ 0：（差异℃，1：2）;
}
 

您能想出一个更快的一个没有分支机构？

摘要

10个解决方案，我有基准类似的性能。实际数字和冠军取决于编译器（ICC / GCC），编译器选项（例如，-O3，​​-march =的Nocona，-fast，-xHost）和机器变化。 佳能的解决方案在许多基准运行表现不错，但同样的性能优势轻微。我很惊讶，在某些情况下，一些解决方案比设有分支机构天真的解决方案慢。

解决方案

  INT比较（INT X，int y）对{
     回报（X LT，Y）+（Y＆LT; X）LT;＆LT; 1;
}
 

编辑：只按位？猜猜＆LT;和>不计呢？

  INT比较（INT X，int y）对{
    INT差异=说明X  -  Y;
    返回（!!差异）| （!!（DIFF＆安培;为0x80000000）LT;＆LT; 1）;
}
 

但是，还有那个讨厌的 -

编辑：按住Shift键周围的其他方法

。

咩，只是再试一次：

  INT比较（INT X，int y）对{
    INT差异= Y  -  X;
    返程（!!差异）＆LT;＆LT; （（差异＆GT;＆GT; 31）及1）;
}
 

但我猜有一个为 没有标准的ASM指令！。此外，＆LT;＆LT; 可以用 + 被替换，这取决于这是更快...

位操作的乐趣！

嗯，我刚刚得知 setnz 。

我没有检查汇编输出（但我没有测试它有点这段时间），并与一点点运气可以节省的整个指令的：

理论上是这样。 MY汇编生锈

  subl％EDI，ESI％
setnz％EAX
SARL $ 31％ESI
和L $ 1，％ESI
SARL％EAX，ESI％
MOV％ESI，EAX％
RET
 

漫话是有趣的。

我需要睡眠。

Write a branchless function that returns 0, 1, or 2 if the difference between two signed integers is zero, negative, or positive.

Here's a version with branching:

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

Here's a version that may be faster depending on compiler and processor:

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

Can you come up with a faster one without branches?

SUMMARY

The 10 solutions I benchmarked had similar performance. The actual numbers and winner varied depending on compiler (icc/gcc), compiler options (e.g., -O3, -march=nocona, -fast, -xHost), and machine. Canon's solution performed well in many benchmark runs, but again the performance advantage was slight. I was surprised that in some cases some solutions were slower than the naive solution with branches.

解决方案

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

Edit: Bitwise only? Guess < and > don't count, then?

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

But there's that pesky -.

Edit: Shift the other way around.

Meh, just to try again:

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

But I'm guessing there's no standard ASM instruction for !!. Also, the << can be replaced with +, depending on which is faster...

Bit twiddling is fun!

Hmm, I just learned about setnz.

I haven't checked the assembler output (but I did test it a bit this time), and with a bit of luck it could save a whole instruction!:

IN THEORY. MY ASSEMBLER IS RUSTY

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

Rambling is fun.

I need sleep.

这篇关于网点code映射零，负数和积极的为0，1，2的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！