将0，负和正映射到0,1,2的无分支代码
https://stackoverflow.com/questions/1610836
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
写一个无分支函数，如果两个有符号整数之间的差值为零，负数或正数，则返回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）和机器。 佳能的解决方案在许多基准测试中表现良好，但性能优势再次轻微。令我感到惊讶的是，在某些情况下，某些解决方案比使用分支的天真解决方案慢。
解决方案
int Compare(int x, int y) {
return (x < y) + (y < x) << 1;
}
编辑：仅按位？猜猜<！> lt;和<！> gt;不计算，那么？
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
漫游很有趣。
我需要睡觉。
其他提示
无分支（在语言级别）代码，将负数映射到-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);
假设2s补码，算术右移，减法没有溢出：
#define SHIFT (CHARBIT*sizeof(int) - 1)
int Compare(int x, int y)
{
int diff = x - y;
return -(diff >> SHIFT) - (((-diff) >> SHIFT) << 1);
}
两个补充：
#include <limits.h>
#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）<！> gt; 0然后（（x-y）+ INT_MAX）将设置整数的高位，否则将取消设置。因此，当且仅当（x - y）<！> gt时，p才会设置其最低位; 0. If（x - y）<！> lt; 0然后它的高位将被置位，d将其第二位设置为最低位。
返回-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）可以在32位比较中转换为有符号比较（cmpu），方法是在将两个有符号输入传递给cmpu之前将其加到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]);
}
我支持Tordek的原始答案：
int compare(int x, int y) {
return (x < y) + 2*(y < x);
}
使用gcc -O3 -march=pentium4进行编译会产生使用条件指令的无分支代码setg和setl（请参阅解释x86指令）。
push %ebp
mov %esp,%ebp
mov %eax,%ecx
xor %eax,%eax
cmp %edx,%ecx
setg %al
add %eax,%eax
cmp %edx,%ecx
setl %dl
movzbl %dl,%edx
add %edx,%eax
pop %ebp
ret
天哪，这困扰着我。
无论如何，我认为我挤出了最后一滴表现：
int compare(int a, int b) {
return (a != b) << (a > b);
}
虽然在GCC中使用-O3进行编译会给（跟我一起，我是从内存中做到的）
xorl %eax, %eax
cmpl %esi, %edi
setne %al
cmpl %esi, %edi
setgt %dl
sall %dl, %eax
ret
但第二次比较似乎（根据一点点测试;我吮吸ASM）是多余的，留下小而美丽的
xorl %eax, %eax
cmpl %esi, %edi
setne %al
setgt %dl
sall %dl, %eax
ret
（Sall可能完全不是ASM指令，但我不记得确切）
所以......如果你不介意再次运行你的基准测试，我很想听听结果（我的改进了3％，但可能是错误的。）
结合Stephen Canon和Tordek的答案：
int Compare(int x, int y)
{
int diff = x - y;
return -(diff >> 31) + (2 & (-diff >> 30));
}
产量：（g ++ -O3）
subl %esi,%edi
movl %edi,%eax
sarl $31,%edi
negl %eax
sarl $30,%eax
andl $2,%eax
subl %edi,%eax
ret
紧！但是，Paul Hsieh的版本指令更少：
subl %esi,%edi
leal 0x7fffffff(%rdi),%eax
sarl $30,%edi
andl $2,%edi
shrl $31,%eax
leal (%rdi,%rax,1),%eax
ret
int Compare(int x, int y)
{
int diff = x - y;
int absdiff = 0x7fffffff & diff; // diff with sign bit 0
int absdiff_not_zero = (int) (0 != udiff);
return
(absdiff_not_zero << 1) // 2 iff abs(diff) > 0
-
((0x80000000 & diff) >> 31); // 1 iff diff < 0
}
对于32个有符号整数（如Java中），请尝试：
return 2 - ((((x >> 30) & 2) + (((x-1) >> 30) & 2))) >> 1;
其中(x >> 30) & 2为负数返回2，否则返回0。
x将是两个输入整数的差异
