如何在C语言中实现最佳（最干净、最高效）的饱和加法？
该函数或宏应该将两个无符号输入相加（需要16位和32位版本），如果总和溢出，返回全1位（0xFFFF或0xFFFFFFFF）。
目标是在使用gcc（4.1.2）和Visual Studio（仅用于模拟，因此回退实现也可以）的x86和ARM上运行。
如何在C语言中进行无符号饱和加法？
51
- Frank Szczerba
3
2MSalters的答案编译成x86上迄今为止最好的代码，与我使用内联汇编能做到的最好的相当（实际上更好，因为编译器理解发生了什么，并且可以选择哪个操作数将是加法的目标）。在ARM上也同样不错。然而，gcc似乎没有使用ARM的带无符号饱和度的加法指令。MSalters的答案应该被接受。 - Peter Cordes
不幸的是，对于16位adds16_msalters，带有条件跳转和其他所有内容，胜利似乎在GCC 6中消失了。 - user1649948
相关：有符号饱和度：64位整数的有符号饱和加法？ 是一个更难的问题。我在那里的回答需要一个GCC内置函数来高效编译；与进位标志不同，很难让编译器使用有符号溢出标志输出。 - Peter Cordes
19个回答
2
我认为，在x86中检查溢出标志的最佳方式是使用内联汇编来进行加法后的检查。具体如下：
add eax, ebx
jno @@1
or eax, 0FFFFFFFFh
@@1:
.......
这不是特别的便携，但在我看来是最有效的方式。
- Igor Semenov
3
我认为ARM的答案类似（甚至更有效率，使用条件操作），但我希望有人知道一个模式，可以欺骗GCC生成接近这个的东西。 - Frank Szczerba
@Frank，你正在使用哪个GCC版本？（gcc --version）。 更新的版本会做这样的技巧。 - Nils Pipenbrinck
jno 检查有符号溢出。 jnc 会检查无符号环绕，就像此处 Q 所需，这将与 mov eax，-1（或带有错误依赖项的简短形式; or eax，-1）相匹配。 但如果您要引入对添加的数据依赖项，则会破坏分支预测+规范执行的效果，您可以使用 sbb edx，edx / or eax，edx 将 CF 广播到所有位并 OR 进去。 但是，CMOVC 的效率更高，关键路径上只有 1 或 2 个微操作，而不是 2 或 3 个。 - Peter Cordes2
通常最好的性能涉及到内联汇编（正如一些人已经提到的那样）。
但是对于可移植的C语言，这些函数只涉及一个比较和没有类型转换（因此我认为是最优的）：
unsigned saturate_add_uint(unsigned x, unsigned y)
{
if (y > UINT_MAX - x) return UINT_MAX;
return x + y;
}
unsigned short saturate_add_ushort(unsigned short x, unsigned short y)
{
if (y > USHRT_MAX - x) return USHRT_MAX;
return x + y;
}
作为宏，它们变成了：
SATURATE_ADD_UINT(x, y) (((y)>UINT_MAX-(x)) ? UINT_MAX : ((x)+(y)))
SATURATE_ADD_USHORT(x, y) (((y)>SHRT_MAX-(x)) ? USHRT_MAX : ((x)+(y)))
我留下“unsigned long”和“unsigned long long”的版本作为读者的练习。;-)
- Kevin
1
int saturating_add(int x, int y)
{
int w = sizeof(int) << 3;
int msb = 1 << (w-1);
int s = x + y;
int sign_x = msb & x;
int sign_y = msb & y;
int sign_s = msb & s;
int nflow = sign_x && sign_y && !sign_s;
int pflow = !sign_x && !sign_y && sign_s;
int nmask = (~!nflow + 1);
int pmask = (~!pflow + 1);
return (nmask & ((pmask & s) | (~pmask & ~msb))) | (~nmask & msb);
}
这个实现不使用控制流、比较运算符（==, !=）和三目运算符?:。它只使用位运算符和逻辑运算符。
- Shangchih Huang
1
除了无分支的x86汇编解决方案外，还有一种替代方案（AT&T语法，a和b在eax和ebx中，结果在eax中）：
add %eax,%ebx
sbb $0,%ebx
- Ian Rogers
1
2
sbb $0, %ebx 是否减去1。如果加法溢出超过1，则会得到错误的答案。另外一种方法是使用sbb same,same来产生0或-1掩码，并将加法结果与其进行OR运算。然而，这种方法具有更长的关键路径延迟比add %edi,%esi / mov $-1,%eax / cmovnc %esi,%edi。 （sbb和cmov在所有CPU上具有相同的延迟：在Intel pre-Broadwell上为2，在其他情况下为1。） - Peter Cordes0
//function-like macro to add signed vals,
//then test for overlow and clamp to max if required
#define SATURATE_ADD(a,b,val) ( {\
if( (a>=0) && (b>=0) )\
{\
val = a + b;\
if (val < 0) {val=0x7fffffff;}\
}\
else if( (a<=0) && (b<=0) )\
{\
val = a + b;\
if (val > 0) {val=-1*0x7fffffff;}\
}\
else\
{\
val = a + b;\
}\
})
我进行了快速测试，似乎可以工作，但还没有进行全面的测试！这适用于有符号32位。 操作：网页上使用的编辑器不允许我发布宏，即它无法理解非缩进语法等！
- twostickes
0
饱和算术对于C语言不是标准的，但通常是通过编译器内部实现的，因此最有效的方法并非最干净的。您必须添加#ifdef块来选择适当的方法。对于x86架构，MSalters的答案是最快的。对于ARM架构，您需要使用16位版本的__qadd16函数（ARM编译器）或_arm_qadd16（Microsoft Visual Studio），以及32位版本的__qadd。它们将自动翻译为一个ARM指令。
链接：
- {{link1：
__qadd16}} - {{link2：
_arm_qadd16}} - {{link3：
__qadd}}
- Alexei Shcherbakov
0
我会添加以上未提及的解决方案。
在Intel x86中存在ADC指令。它表示为_addcarry_u32()内部函数。对于ARM应该有类似的内部函数。
这使我们能够为Intel x86实现非常快速的uint32_t饱和加法：
#include <stdint.h>
#include <immintrin.h>
uint32_t add_sat_u32(uint32_t a, uint32_t b) {
uint32_t r, carry = _addcarry_u32(0, a, b, &r);
return r | (-carry);
}
Intel x86 MMX 饱和加法指令可用于实现 uint16_t 变体：
#include <stdint.h>
#include <immintrin.h>
uint16_t add_sat_u16(uint16_t a, uint16_t b) {
return _mm_cvtsi64_si32(_mm_adds_pu16(
_mm_cvtsi32_si64(a),
_mm_cvtsi32_si64(b)
));
}
我不提及ARM解决方案，因为它可以通过其他答案中的通用解决方案来实现。
- Arty
0
C++ 模板，防止使用有符号类型，并且不进行 -1 强制转换：
template<typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
T saturatingAdd(T a, T b)
{
T c = a + b;
return c < a ? std::numeric_limits<T>::MAX : c;
}
- Timmmm
0
使用C++，您可以编写一个更灵活的Remo.D解决方案的变体：
template<typename T>
T sadd(T first, T second)
{
static_assert(std::is_integral<T>::value, "sadd is not defined for non-integral types");
return first > std::numeric_limits<T>::max() - second ? std::numeric_limits<T>::max() : first + second;
}
这可以很容易地翻译成C语言 - 使用在limits.h中定义的限制。请注意，固定宽度整数类型可能在您的系统上不可用。
- 0xbadf00d
1
1非常好，尽管我认为你需要进一步确定
T是有符号还是无符号的，因为当使用有符号整数时，对max()的测试不会正常工作。 - Alexis Wilke网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接