如何做C饱和加法？
什么是最好（最干净，最有效）的方式来写入饱和加法在C？
如果总和溢出，函数或macros应该添加两个无符号的input（需要16位和32位版本），并返回全位1（0xFFFF或0xFFFFFFFF）。
目标是使用gcc（4.1.2）和Visual Studio的x86和ARM（仅用于模拟，所以后备实现在那里）。
您可能需要在这里使用可移植的C代码，您的编译器将转换为适当的ARM程序集。 ARM有条件的移动，并且这些可以以溢出为条件。 algorithm然后变成添加，并且如果检测到溢出，则有条件地将目的地设置为无符号（-1）。
uint16_t add16(uint16_t a, uint16_t b) { uint16_t c = a + b; if (c<a) /* Can only happen due to overflow */ c = -1; return c; } 请注意，这不同于其他algorithm，因为它纠正了溢出，而不是依靠另一个计算来检测溢出。
x86-64铿锵3.7 -O3输出为adds32 ：显着优于任何其他答案：
add edi, esi mov eax, -1 cmovae eax, edi ret
ARMv7： gcc 4.8 -O3 -mcpu=cortex-a15 -fverbose-asm output for adds32 ：
adds r0, r0, r1 @ c, a, b it cs movcs r0, #-1 @ conditional-move bx lr
16bit：仍然不使用ARM的无符号饱和加指令（ UADD16 ）
add r1, r1, r0 @ tmp114, a movw r3, #65535 @ tmp116, uxth r1, r1 @ c, tmp114 cmp r0, r1 @ a, c ite ls @ movls r0, r1 @,, c movhi r0, r3 @,, tmp116 bx lr @
在普通的C：
uint16_t sadd16(uint16_t a, uint16_t b) { return (a > 0xFFFF - b) ? 0xFFFF : a + b; } uint32_t sadd32(uint32_t a, uint32_t b) { return (a > 0xFFFFFFFF - b) ? 0xFFFFFFFF : a + b;}
几乎是macros观化的，直接expression了意义。
在没有条件跳转的IA32中：
uint32_t sadd32(uint32_t a, uint32_t b) { #if defined IA32 __asm { mov eax,a xor edx,edx add eax,b setnc dl dec edx or eax,edx } #elif defined ARM // ARM code #else // non-IA32/ARM way, copy from above #endif }
在ARM中，您可能已经具有饱和算术内置。 ARMv5 DSP扩展可以将寄存器饱和到任何位长。 另外在ARM上，饱和度通常很便宜，因为你可以执行大部分指令。
ARMv6甚至具有饱和加法，减法和所有其他的32位和打包数字的东西。
在x86上，您可以通过MMX或SSE获得饱和算术。
所有这些都需要汇编程序，所以这不是你所要求的。
还有C-tricks做饱和算术。 这个小代码在dword的四个字节上做了饱和的添加。 它是基于这样的思想来并行计算32个半加器，例如添加没有进位溢出的数字。
这首先完成。 然后进行计算，添加并用掩码replace，如果加法溢出。
uint32_t SatAddUnsigned8(uint32_t x, uint32_t y) { uint32_t signmask = 0x80808080; uint32_t t0 = (y ^ x) & signmask; uint32_t t1 = (y & x) & signmask; x &= ~signmask; y &= ~signmask; x += y; t1 |= t0 & x; t1 = (t1 << 1) - (t1 >> 7); return (x ^ t0) | t1; }
你可以通过改变信号屏蔽常数和底部的移位来得到16位（或任何types的位域）相同的值：
uint32_t SatAddUnsigned16(uint32_t x, uint32_t y) { uint32_t signmask = 0x80008000; uint32_t t0 = (y ^ x) & signmask; uint32_t t1 = (y & x) & signmask; x &= ~signmask; y &= ~signmask; x += y; t1 |= t0 & x; t1 = (t1 << 1) - (t1 >> 15); return (x ^ t0) | t1; } uint32_t SatAddUnsigned32 (uint32_t x, uint32_t y) { uint32_t signmask = 0x80000000; uint32_t t0 = (y ^ x) & signmask; uint32_t t1 = (y & x) & signmask; x &= ~signmask; y &= ~signmask; x += y; t1 |= t0 & x; t1 = (t1 << 1) - (t1 >> 31); return (x ^ t0) | t1; }
上面的代码对于16位和32位值是一样的。
如果您不需要函数添加的function并且将多个值并行地进行饱和，则只需屏蔽掉您需要的位。 在ARM上，您还需要更改符号掩码常量，因为ARM无法在单个周期中加载所有可能的32位常量。
编辑：并行版本最有可能比直接的方法慢，但是如果你必须一次饱和多个值，它们会更快。
如果你关心性能，你真的想在SIMD中做这样的事情，其中x86有本地饱和algorithm。
由于在标量math中缺乏饱和算术，可以得到在四variables宽SIMD上完成的操作比等效C快4倍的情况（并且对于8variables宽SIMD相应也是如此）：
sub8x8_dct8_c: 1332 clocks sub8x8_dct8_mmx: 182 clocks sub8x8_dct8_sse2: 127 clocks
零分支解决scheme：
uint32_t sadd32(uint32_t a, uint32_t b) { uint64_t s = (uint64_t)a+b; return -(s>>32) | (uint32_t)s; }
一个好的编译器会优化这个以避免做任何实际的64位算术（ s>>32将仅仅是进位标志，而-(s>>32)是sbb %eax,%eax ）。
在x86 asm（AT＆T语法， eax和ebx a和b ，导致eax ）：
add %eax,%ebx sbb %eax,%eax or %ebx,%eax
8位和16位版本应该是显而易见的。 签名版本可能需要更多的工作。
uint32_t saturate_add32(uint32_t a, uint32_t b) { uint32_t sum = a + b; if ((sum < a) || (sum < b)) return ~((uint32_t)0); else return sum; } /* saturate_add32 */ uint16_t saturate_add16(uint16_t a, uint16_t b) { uint16_t sum = a + b; if ((sum < a) || (sum < b)) return ~((uint16_t)0); else return sum; } /* saturate_add16 */
编辑：现在你已经发布了你的版本，我不知道我的是更清洁/更好/更有效/更完美。
我不确定这是否比Skizz的解决scheme（总是configuration文件）更快，但是这里有一个替代的无分支组装解决scheme。 请注意，这需要条件移动（CMOV）指令，我不确定是否在您的目标上可用。
uint32_t sadd32(uint32_t a, uint32_t b) { __asm { movl eax, a addl eax, b movl edx, 0xffffffff cmovc eax, edx } }
目前我们正在使用的实现是：
#define sadd16(a, b) (uint16_t)( ((uint32_t)(a)+(uint32_t)(b)) > 0xffff ? 0xffff : ((a)+(b))) #define sadd32(a, b) (uint32_t)( ((uint64_t)(a)+(uint64_t)(b)) > 0xffffffff ? 0xffffffff : ((a)+(b)))
我想，x86的最好的方法是使用内联汇编程序在添加之后检查溢出标志。 就像是：
add eax, ebx jno @@1 or eax, 0FFFFFFFFh @@1: .......
这不是很便携，但恕我直言，最有效的方式。
最好的性能通常会涉及内联汇编（如一些已经说过的）。
但对于便携式C，这些function只涉及一个比较，没有types铸造（因此我相信最佳）：
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; }
作为macros，它们变成：
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'作为练习给读者。 😉
以防万一有人想知道一个实现没有分支使用2的补码32位整数。
警告！ 此代码使用未定义的操作：“右移-1”，因此利用Intel Pentium SAL指令的属性将计数操作数屏蔽为5位。
int32_t sadd(int32_t a, int32_t b){ int32_t sum = a+b; int32_t overflow = ((a^sum)&(b^sum))>>31; return (overflow<<31)^(sum>>overflow); }
这是我知道的最好的实现
使用C ++，您可以编写一个更灵活的Remo.D解决scheme：
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定义的限制。 另请注意， 固定宽度整数types可能在您的系统上不可用。
分支免费x86 asm解决scheme的替代scheme是（AT＆T语法，eax和ebx中的a和b，导致eax）：
add %eax,%ebx sbb $0,%ebx
//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;\ }\ })
我做了一个快速的testing，似乎工作，但没有广泛的打击它呢！ 这适用于SIGNED 32位。 op：在网页上使用的编辑器不让我发布一个macros，即它不理解非缩进语法等！
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); }
这个实现不使用控制stream，竞争运算符（ == ， != ）和?:运算符。 它只是使用按位运算符和逻辑运算符。
