减去/增加值，没有溢出或下溢
想象一下，我有两个无符号的字节b和x 。 我需要计算bsub作为b - x和badd作为b + x 。 但是，在这些操作过程中，我不想发生下溢/溢出。 例如（伪代码）：
b = 3; x = 5; bsub = b - x; // bsub must be 0, not 254
和
b = 250; x = 10; badd = b + x; // badd must be 255, not 4
明显的做法包括分支：
bsub = b - min(b, x); badd = b + min(255 - b, x);
我只是想知道是否有更好的方法来做到这一点，即通过一些hacky位操纵？
文章Branchfree Saturating Arithmetic提供了这样的策略：
他们的添加解决scheme如下：
u32b sat_addu32b(u32b x, u32b y) { u32b res = x + y; res |= -(res < x); return res; }
修改为uint8_t：
uint8_t sat_addu8b(uint8_t x, uint8_t y) { uint8_t res = x + y; res |= -(res < x); return res; }
他们的减法解决scheme是：
u32b sat_subu32b(u32b x, u32b y) { u32b res = x - y; res &= -(res <= x); return res; }
修改为uint8_t：
uint8_t sat_subu8b(uint8_t x, uint8_t y) { uint8_t res = x - y; res &= -(res <= x); return res; }
一个简单的方法是检测溢出并相应地重置该值，如下所示
bsub = b - x; if (bsub > b) { bsub = 0; } badd = b + x; if (badd < b) { badd = 255; }
使用-O2进行编译时，GCC可以将溢出检查优化为条件分配。
我测量了与其他解决scheme相比有多less优化。 在我的电脑上有10亿次以上的操作，这个解决scheme和@ShafikYaghmour的解决scheme平均为4.2秒，而@chux平均为4.8秒。 这个解决scheme也更具可读性。
对于减法：
diff = (a - b)*(a >= b);
加成：
sum = (a + b) | -(a > (255 - b))
演化
// sum = (a + b)*(a <= (255-b)); this fails // sum = (a + b) | -(a <= (255 - b)) falis too
感谢@ R_Kapp
感谢@NathanOliver
这个练习显示了简单编码的价值。
sum = b + min(255 - b, a);
如果您使用的是最新版本的gcc或clang（也许还有其他一些版本），则可以使用内置程序来检测溢出。
if (__builtin_add_overflow(a,b,&c)) { c = UINT_MAX; }
如果你愿意使用汇编或内在函数，我想我有一个最佳的解决scheme。
对于减法：
我们可以使用sbb指令
在MSVC中，我们可以使用内部函数_subborrow_u64 （也可用于其他位大小）。
这是如何使用它：
// *c = a - (b + borrow) // borrow_flag is set to 1 if (a < (b + borrow)) borrow_flag = _subborrow_u64(borrow_flag, a, b, c);
以下是我们如何将其应用于您的情况
uint64_t sub_no_underflow(uint64_t a, uint64_t b){ uint64_t result; borrow_flag = _subborrow_u64(0, a, b, &result); return result * !borrow_flag; }
另外：
我们可以使用adcx指令
在MSVC中，我们可以使用内部函数_addcarry_u64 （也可用于其他位尺寸）。
这是如何使用它：
// *c = a + b + carry // carry_flag is set to 1 if there is a carry bit carry_flag = _addcarry_u64(carry_flag, a, b, c);
以下是我们如何将其应用于您的情况
uint64_t add_no_overflow(uint64_t a, uint64_t b){ uint64_t result; carry_flag = _addcarry_u64(0, a, b, &result); return !carry_flag * result - carry_flag; }
我不喜欢这个减法一个，但我认为这是非常漂亮的。
如果添加溢出， carry_flag = 1 。 如果carry_flag不为0，那么!carry_flag * result = 0当溢出时。 由于0 - 1将无符号整数值设置为最大值，所以如果没有进位，函数将返回相加的结果，如果有进位返回所选积分值的最大值。
所有这些都可以用无符号字节算术完成
// Addition without overflow return (b > 255 - a) ? 255 : a + b // Subtraction without underflow return (b > a) ? 0 : a - b;
如果你会调用这些方法很多，最快的方式不是位操作，但可能是一个查找表。 为每个操作定义一个长度为511的数组。 减（减）
static unsigned char maxTable[511]; memset(maxTable, 0, 255); // If smaller, emulates cutoff at zero maxTable[255]=0; // If equal - return zero for (int i=0; i<256; i++) maxTable[255+i] = i; // If greater - return the difference
该数组是静态的，只能初始化一次。 现在你的减法可以被定义为内联方法或使用预编译器：
#define MINUS(A,B) maxTable[A-B+255];
怎么运行的？ 那么你想预先计算所有可能的减法无符号的字符。 结果从-255到+255不等，总共有511个不同的结果。 我们定义一个所有可能结果的数组，但是因为在C中我们不能从负指数访问它，我们使用+255（在[A-B + 255]中）。 你可以通过定义一个指向数组中心的指针来删除这个动作。
const unsigned char *result = maxTable+255; #define MINUS(A,B) result[AB];
像这样使用它：
bsub = MINUS(13,15); // ie 13-15 with zero cutoff as requested
请注意，执行速度非常快。 只有一个减法和一个指针参考才能得到结果。 没有分支。 静态数组非常短，所以它们将被完全加载到CPU的caching中以进一步加速计算
相同的工作将增加，但有一点不同的表（前256个元素将是指数和最后255个元素将等于255模仿截止超过255。
如果你坚持位操作，使用（a> b）的答案是错误的。 这仍然可以实现为分支。 使用符号位技术
// (num1>num2) ? 1 : 0 #define is_int_biggerNotEqual( num1,num2) ((((__int32)((num2)-(num1)))&0x80000000)>>31)
现在你可以使用它来计算减法和加法。
如果你想模仿函数max（），min（）而不使用分支：
inline __int32 MIN_INT(__int32 x, __int32 y){ __int32 d=xy; return y+(d&(d>>31)); } inline __int32 MAX_INT(__int32 x, __int32 y){ __int32 d=xy; return x-(d&(d>>31)); }
我上面的例子使用32位整数。 您可以将其更改为64，但我相信32位计算运行速度更快。 由你决定
另外：
unsigned temp = a+b; // temp>>8 will be 1 if overflow else 0 unsigned char c = temp | -(temp >> 8);
对于减法：
unsigned temp = ab; // temp>>8 will be 0xFF if neg-overflow else 0 unsigned char c = temp & ~(temp >> 8);
没有比较运算符或乘法要求。
您也可以在Boost Library Incubator上使用安全的数字库。 它提供了int，long等的replace方式，保证你永远不会被检测到溢出，下溢等。
那这个呢：
bsum = a + b; bsum = (bsum < a || bsum < b) ? 255 : bsum; bsub = a - b; bsub = (bsub > a || bsub > b) ? 0 : bsub;
如果你想用两个字节做这个，可以使用最简单的代码。
如果你想用200亿字节做这个，检查你的处理器上有哪些向量指令可用，以及它们是否可以使用。 你可能会发现你的处理器可以用一条指令完成32个这样的操作。
