是的，有一种方法可以计算两个的最大值或最小值doubles 没有任何分支。执行此操作的 C++ 代码如下所示：
#include <algorithm>
double FindMinimum(double a, double b)
{
return std::min(a, b);
}
double FindMaximum(double a, double b)
{
return std::max(a, b);
}
我打赌你以前见过这个。免得你不相信这是无分支的，查看拆解 https://gcc.godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(fontScale:0.8957951999999999,j:1,lang:c%2B%2B,source:%27++++%23include+%3Calgorithm%3E%0A%0A++++double+FindMinimum(double+a,+double+b)%0A++++%7B%0A++++++++return+std::min(a,+b)%3B%0A++++%7D%0A%0A++++double+FindMaximum(double+a,+double+b)%0A++++%7B%0A++++++++return+std::max(a,+b)%3B%0A++++%7D%27),l:%275%27,n:%270%27,o:%27C%2B%2B+source+%231%27,t:%270%27)),k:31.467710371819962,l:%274%27,m:100,n:%270%27,o:%27%27,s:0,t:%270%27),(g:!((g:!((h:compiler,i:(compiler:clang700,filters:(b:%270%27,binary:%271%27,commentOnly:%270%27,demangle:%270%27,directives:%270%27,execute:%271%27,intel:%270%27,libraryCode:%271%27,trim:%271%27),fontScale:0.8957951999999999,lang:c%2B%2B,libs:!(),options:%27-O2+-fverbose-asm%27,source:1),l:%275%27,n:%270%27,o:%27x86-64+clang+7.0.0+(Editor+%231,+Compiler+%231)+C%2B%2B%27,t:%270%27)),header:(),k:64.41182865840402,l:%274%27,m:22.5,n:%270%27,o:%27%27,s:0,t:%270%27),(g:!((h:compiler,i:(compiler:g83,filters:(b:%270%27,binary:%271%27,commentOnly:%270%27,demangle:%270%27,directives:%270%27,execute:%271%27,intel:%270%27,libraryCode:%271%27,trim:%271%27),lang:c%2B%2B,libs:!(),options:%27-O2+-fverbose-asm%27,source:1),l:%275%27,n:%270%27,o:%27x86-64+gcc+8.3+(Editor+%231,+Compiler+%232)+C%2B%2B%27,t:%270%27)),header:(),l:%274%27,m:25.963673057517656,n:%270%27,o:%27%27,s:0,t:%270%27),(g:!((h:compiler,i:(compiler:vcpp_v19_16_x64,filters:(b:%270%27,binary:%271%27,commentOnly:%270%27,demangle:%270%27,directives:%270%27,execute:%271%27,intel:%270%27,libraryCode:%271%27,trim:%271%27),lang:c%2B%2B,libs:!(),options:/O2,source:1),l:%275%27,n:%270%27,o:%27x64+msvc+v19.16+(Editor+%231,+Compiler+%233)+C%2B%2B%27,t:%270%27)),header:(),l:%274%27,m:51.53632694248234,n:%270%27,o:%27%27,s:0,t:%270%27)),k:68.53228962818004,l:%273%27,n:%270%27,o:%27%27,t:%270%27)),l:%272%27,n:%270%27,o:%27%27,t:%270%27)),version:4:
FindMinimum(double, double):
minsd xmm1, xmm0
movapd xmm0, xmm1
ret
FindMaximum(double, double):
maxsd xmm1, xmm0
movapd xmm0, xmm1
ret
这就是您从所有针对 x86 的流行编译器获得的结果。使用的是SSE2指令集，具体是minsd/maxsd指令，无分支地计算两个双精度浮点值的最小值/最大值。
所有 64 位 x86 处理器均支持SSE2 https://en.wikipedia.org/wiki/SSE2; AMD64 扩展需要它。即使大多数不带 64 位的 x86 处理器也支持 SSE2。它于 2000 年发布。您必须走很长的路才能找到不支持 SSE2 的处理器。但如果你这样做了呢？好吧，即使在那里，您可以在最流行的编译器上获得无分支代码 https://gcc.godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(fontScale:0.8957951999999999,j:1,lang:c%2B%2B,source:%27++++%23include+%3Calgorithm%3E%0A%0A++++double+FindMinimum(double+a,+double+b)%0A++++%7B%0A++++++++return+std::min(a,+b)%3B%0A++++%7D%0A%0A++++double+FindMaximum(double+a,+double+b)%0A++++%7B%0A++++++++return+std::max(a,+b)%3B%0A++++%7D%27),l:%275%27,n:%270%27,o:%27C%2B%2B+source+%231%27,t:%270%27)),k:31.467710371819962,l:%274%27,m:100,n:%270%27,o:%27%27,s:0,t:%270%27),(g:!((g:!((h:compiler,i:(compiler:clang700,filters:(b:%270%27,binary:%271%27,commentOnly:%270%27,demangle:%270%27,directives:%270%27,execute:%271%27,intel:%270%27,libraryCode:%271%27,trim:%271%27),fontScale:0.8957951999999999,lang:c%2B%2B,libs:!(),options:%27-O2+-fverbose-asm+-mno-sse+-m32%27,source:1),l:%275%27,n:%270%27,o:%27x86-64+clang+7.0.0+(Editor+%231,+Compiler+%231)+C%2B%2B%27,t:%270%27)),header:(),k:64.41182865840402,l:%274%27,m:22.5,n:%270%27,o:%27%27,s:0,t:%270%27),(g:!((h:compiler,i:(compiler:g83,filters:(b:%270%27,binary:%271%27,commentOnly:%270%27,demangle:%270%27,directives:%270%27,execute:%271%27,intel:%270%27,libraryCode:%271%27,trim:%271%27),lang:c%2B%2B,libs:!(),options:%27-O2+-fverbose-asm+-mno-sse+-m32%27,source:1),l:%275%27,n:%270%27,o:%27x86-64+gcc+8.3+(Editor+%231,+Compiler+%232)+C%2B%2B%27,t:%270%27)),header:(),l:%274%27,m:25.963673057517656,n:%270%27,o:%27%27,s:0,t:%270%27),(g:!((h:compiler,i:(compiler:vcpp_v19_16_x86,filters:(b:%270%27,binary:%271%27,commentOnly:%270%27,demangle:%270%27,directives:%270%27,execute:%271%27,intel:%270%27,libraryCode:%271%27,trim:%271%27),lang:c%2B%2B,libs:!(),options:%27/O2+/arch:IA32%27,source:1),l:%275%27,n:%270%27,o:%27x86+msvc+v19.16+(Editor+%231,+Compiler+%233)+C%2B%2B%27,t:%270%27)),header:(),l:%274%27,m:51.53632694248234,n:%270%27,o:%27%27,s:0,t:%270%27)),k:68.53228962818004,l:%273%27,n:%270%27,o:%27%27,t:%270%27)),l:%272%27,n:%270%27,o:%27%27,t:%270%27)),version:4:
FindMinimum(double, double):
fld QWORD PTR [esp + 12]
fld QWORD PTR [esp + 4]
fucomi st(1)
fcmovnbe st(0), st(1)
fstp st(1)
ret
FindMaximum(double, double):
fld QWORD PTR [esp + 4]
fld QWORD PTR [esp + 12]
fucomi st(1)
fxch st(1)
fcmovnbe st(0), st(1)
fstp st(1)
ret
The fucomi指令执行比较，设置标志，然后fcmovnbe指令根据这些标志的值执行条件移动。这完全是无分支的，并且依赖于 1995 年 Pentium Pro 引入 x86 ISA 的指令，自 Pentium II 以来所有 x86 芯片都支持该指令。
唯一的编译器won't这里生成无分支代码是MSVC，因为它没有利用FCMOVxx操作说明 https://stackoverflow.com/questions/13661285/generating-cmov-instructions-using-microsoft-compilers/41144749#41144749。相反，你会得到：
double FindMinimum(double, double) PROC
fld QWORD PTR [a]
fld QWORD PTR [b]
fcom st(1) ; compare "b" to "a"
fnstsw ax ; transfer FPU status word to AX register
test ah, 5 ; check C0 and C2 flags
jp Alt
fstp st(1) ; return "b"
ret
Alt:
fstp st(0) ; return "a"
ret
double FindMinimum(double, double) ENDP
double FindMaximum(double, double) PROC
fld QWORD PTR [b]
fld QWORD PTR [a]
fcom st(1) ; compare "b" to "a"
fnstsw ax ; transfer FPU status word to AX register
test ah, 5 ; check C0 and C2 flags
jp Alt
fstp st(0) ; return "b"
ret
Alt:
fstp st(1) ; return "a"
ret
double FindMaximum(double, double) ENDP
注意分支JP指令（如果奇偶校验位设置则跳转）。这FCOM指令用于进行比较，它是基本 x87 FPU 指令集的一部分。不幸的是，这会在 FPU 状态字中设置标志，因此为了在这些标志上进行分支，需要提取它们。这就是该项目的目的FNSTSW指令，它将 x87 FPU 状态字存储到通用AX寄存器（它也可以存储到内存中，但是......为什么？）。那么代码TESTs 适当的位，并相应地分支以确保返回正确的值。除了分支之外，检索 FPU 状态字也会相对较慢。这就是 Pentium Pro 推出FCOM指示。
然而，它是unlikely您可以通过使用位旋转操作来确定最小值/最大值来提高任何代码的速度。有两个基本原因：
-
唯一生成低效代码的编译器是 MSVC，并且没有好方法强制它生成您想要的指令。尽管 MSVC 中支持 32 位 x86 目标的内联汇编，当寻求性能改进时，这是一个愚蠢的差事 https://stackoverflow.com/questions/3323445/what-is-the-difference-between-asm-asm-and-asm/35959859#35959859。我也引用一下我自己的话：
内联汇编以相当显着的方式破坏优化器，所以除非你正在编写重要的在内联汇编中使用大量代码，不太可能获得实质性的净性能提升。此外，微软的内联汇编语法极其有限。它在很大程度上牺牲了灵活性以换取简单性。特别是，没有办法指定input值，因此您必须将输入从内存加载到寄存器中，并且调用者被迫将输入从寄存器溢出到内存中以进行准备。这创造了一种现象，我喜欢称之为“一大堆乱七八糟的事情”，或者简称为“缓慢的代码”。在可以接受慢速代码的情况下，您不会放弃内联汇编。因此，最好（至少在 MSVC 上）弄清楚如何编写 C/C++ 源代码来说服编译器发出您想要的目标代码。即使你只能得到close对于理想的输出，这仍然比使用内联汇编所付出的代价要好得多。
-
为了访问浮点值的原始位，您必须进行域转换，从浮点到整数，然后再返回到浮点。那很慢，尤其没有 SSE2，因为从 x87 FPU 获取值到 ALU 中通用整数寄存器的唯一方法是通过内存间接获取。
如果您无论如何都想采用这种策略（例如，对其进行基准测试），您可以利用浮点值按照其字典顺序排序的事实IEEE 754 https://en.wikipedia.org/wiki/IEEE_754表示，符号位除外。因此，既然您假设两个值都是正数：
FindMinimumOfTwoPositiveDoubles(double a, double b):
mov rax, QWORD PTR [a]
mov rdx, QWORD PTR [b]
sub rax, rdx ; subtract bitwise representation of the two values
shr rax, 63 ; isolate the sign bit to see if the result was negative
ret
FindMaximumOfTwoPositiveDoubles(double a, double b):
mov rax, QWORD PTR [b] ; \ reverse order of parameters
mov rdx, QWORD PTR [a] ; / for the SUB operation
sub rax, rdx
shr rax, 63
ret
或者，为了避免内联汇编：
bool FindMinimumOfTwoPositiveDoubles(double a, double b)
{
static_assert(sizeof(a) == sizeof(uint64_t),
"A double must be the same size as a uint64_t for this bit manipulation to work.");
const uint64_t aBits = *(reinterpret_cast<uint64_t*>(&a));
const uint64_t bBits = *(reinterpret_cast<uint64_t*>(&b));
return ((aBits - bBits) >> ((sizeof(uint64_t) * CHAR_BIT) - 1));
}
bool FindMaximumOfTwoPositiveDoubles(double a, double b)
{
static_assert(sizeof(a) == sizeof(uint64_t),
"A double must be the same size as a uint64_t for this bit manipulation to work.");
const uint64_t aBits = *(reinterpret_cast<uint64_t*>(&a));
const uint64_t bBits = *(reinterpret_cast<uint64_t*>(&b));
return ((bBits - aBits) >> ((sizeof(uint64_t) * CHAR_BIT) - 1));
}
请注意，有severe此实施的注意事项。特别是，如果两个浮点值具有不同的符号，或者两个值都是负数，它将中断。如果两个值都是负数，则可以修改代码以翻转它们的符号，进行比较，然后返回相反的值。为了处理两个值具有不同符号的情况，可以添加代码来检查符号位。
// ...
// Enforce two's-complement lexicographic ordering.
if (aBits < 0)
{
aBits = ((1 << ((sizeof(uint64_t) * CHAR_BIT) - 1)) - aBits);
}
if (bBits < 0)
{
bBits = ((1 << ((sizeof(uint64_t) * CHAR_BIT) - 1)) - bBits);
}
// ...
处理负零也会是一个问题。 IEEE 754 规定 +0.0 等于 −0.0，因此您的比较函数必须决定是否要将这些值视为不同的值，或者向比较例程添加特殊代码，以确保负零和正零被视为等效。
添加所有这些特殊情况代码将当然将性能降低到我们将通过简单的浮点比较收支平衡的程度，并且很可能最终会变慢。
