无符号字节的饱和减法/加法

Question

假设我有两个无符号字节 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);

我只是想知道是否有更好的方法来做这件事，比如通过一些巧妙的二进制操作？

- ovk

---

y ^ ((x ^ y) & -(x < y)) 对于 int 类型的变量，可以在不使用分支语句的情况下计算 min(x, y)。根据你目前所拥有的内容，这可能会成为最终解决方案的一部分。 - Bathsheba

也许受限增量整数？会有所帮助。 - Shafik Yaghmour

这是一个C还是C++的问题？请选择一个。 - fuz

@AlanCampbell，这被称为“饱和算术”（Saturating Arithmetic）。 - Shafik Yaghmour

你需要它是可移植的吗？如果你在看特定的架构，那么可能有一个好的单指令。我知道ARM有用于字节饱和矢量加减的指令。在X86上，"_mm_adds_epi8" 内嵌函数可以在一个指令中对16个字节进行饱和加法。 - porglezomp

Answer 1

文章Branchfree Saturating Arithmetic提供了解决方案:

他们的加法解决方案如下:

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;
}

它们的减法解决方案是：

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;
}

- Shafik Yaghmour

---

@user1969104 可能是这样，但文章中的评论指出，在应用一元减之前将其转换为无符号类型即可解决此问题。实际上，你很少需要处理除了二进制补码以外的任何其他情况。 - Shafik Yaghmour

这可能是一个不错的 C 语言答案，但并不是一个很好的 C++ 答案。 - Yakk - Adam Nevraumont

这是一个“糟糕的”C++答案的原因是什么？这些都是基本的数学运算，我不明白为什么会被解释为纯C或糟糕的C++。 - JPhi1618

一种更好的 C++ 解答可能是 template<class T>struct sat{T t;};，并重载使之饱和的操作符？适当使用命名空间，主要是语法糖。 - Yakk - Adam Nevraumont

@Yakk，好的，我只是把这个作为一个最简化的例子供OP根据需要进行调整。我不会期望看到完整的实现。感谢澄清。 - JPhi1618

Answer 2

一种简单的方法是检测溢出并根据下面的情况重置值

bsub = b - x;
if (bsub > b)
{
    bsub = 0;
}

badd = b + x;
if (badd < b)
{
    badd = 255;
}

当使用 -O2 编译时，GCC 可以将溢出检查优化为条件赋值。

我对比了其他解决方案的优化程度。在我的电脑上进行了1000000000次以上操作，这个解决方案和 @ShafikYaghmour 的平均用时为4.2秒，而 @chux 的平均用时为4.8秒。这个解决方案更易读。

- user1969104

---

不是被优化掉了，而是根据进位标志进行条件赋值的优化。 - fuz

是的，user694733 是正确的。它被优化为条件赋值。 - user1969104

这种方法并不适用于所有情况，例如 badd: b = 155 x = 201，则 badd = 156，而且它比 b 还要大。你需要将结果与两个变量的min()或max()进行比较，具体取决于操作类型。 - Cristian F

@CristianF 你如何计算155+201 = 156？我认为它应该是155+201 = 356％256 = 100。我不认为在任何b，x值的组合中都需要min()，max()。 - user1969104

Answer 3

对于无符号字节的饱和减法/加法：

对于减法：

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)) fails too

感谢@R_Kapp。

感谢@NathanOliver。

这个练习展示了简单编码的价值。

sum = b + min(255 - b, a);

- chux - Reinstate Monica

---

对于 sum，也许可以使用 (a + b) | -(a <= (255 - b))？ - R_Kapp

假设 sizeof(int) > sizeof(unsigned char)，你可以使用sum = ((a + b) | (!!((a + b) & ~0xFF) * 0xFF)) & 0xFF，但这看起来非常复杂，我不知道你是否会从中获得任何好处（除了头痛）。 - user694733

@user1969104没有明确说明“更好”的定义（代码空间还是速度性能），也没有指定目标平台和编译器。在未发表的更大问题上下文中，速度评估才最有意义。 - chux - Reinstate Monica

我认为用bool乘法会使意图变得模糊；对于未来的用户来说，更明确地使用条件语句可能会更好。 - Kyle Kanos

@chux：我现在比起C更多地使用C++，而OP使用了两个标签，因此有了关于int和bool的评论。我所说的“更好”是为了未来用户对代码的理解，而不是为了满足OP想要的未定义改进。 - Kyle Kanos

Answer 4

如果您正在使用足够新的gcc或clang版本（可能还包括其他一些编译器），则可以使用内置函数来检测溢出。

if (__builtin_add_overflow(a,b,&c))
{
  c = UINT_MAX;
}

- erebos

---

这是最佳答案。使用编译器内置函数而不是位运算不仅更快，而且更清晰，使代码更易于维护。 - Cephalopod

谢谢，@erebos。我一定会在可用的平台上尝试这个。 - ovk

我无法让gcc生成无分支代码，有点令人失望。特别不幸的是，这里clang使用不同的名称。 - Shafik Yaghmour

@Cephalopod 这完全不是跨平台的，甚至很可能在另一个编译器上都无法工作。这不是21世纪的好解决方案。 - Ela782

@Ela782 恰恰相反：内建函数不是二十一世纪的好解决方案。欢迎来到未来！ - Cephalopod

Answer 5

针对加法:

unsigned temp = a+b;  // temp>>8 will be 1 if overflow else 0
unsigned char c = temp | -(temp >> 8);

减法：

unsigned temp = a-b;  // temp>>8 will be 0xFF if neg-overflow else 0
unsigned char c = temp & ~(temp >> 8);

没有比较运算符或乘法操作符是必要的。

- supercat

Answer 6

如果您愿意使用汇编或内嵌函数，我认为我有一个最优解决方案。

对于减法：

我们可以使用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会将无符号整数值设置为其最大值，所以如果没有进位，函数将返回加法结果，如果有进位，则返回所选整数值的最大值。

- MichaelMitchell

---

你可能需要提到这个答案是针对特定的指令集架构（x86？），并且需要为每个目标架构（SPARC、MIPS、ARM等）重新实现。 - Toby Speight

Answer 7

你也可以使用位于Boost Library Incubator的安全数值库。它提供了int，long等类型的替代品，保证你永远不会遇到未检测到的溢出、下溢等问题。

- Robert Ramey

---

提供一个如何使用这个库的示例会让这个回答更好。此外，它们提供无分支保证吗？ - Shafik Yaghmour

该库有广泛的文档和示例。但是在一天结束时，只需包含适当的头文件并将safe<int>替换为int即可轻松实现。 - Robert Ramey

无分支？我想你是指无分支。该库使用模板元编程，在必要时仅包含运行时检查。例如，unsigned char乘以unsigned char将导致unsigned int。这永远不会溢出，因此根本不需要进行任何检查。另一方面，无符号乘以无符号可能会溢出，因此必须在运行时进行检查。 - Robert Ramey

Answer 8

所有的操作都可以使用无符号字节算术完成。

// Addition without overflow
return (b > 255 - a) ? 255 : a + b

// Subtraction without underflow
return (b > a) ? 0 : a - b;

- user1196549

---

这实际上是最好的解决方案之一。在C++中，其他所有在进行减法或加法之前的操作实际上都会导致未定义行为，从而使编译器能够任意处理。在实践中，你可以大部分预测会发生什么，但仍然存在不确定性。 - Adrien Hamelin

Answer 9

如果你只需要处理两个字节，那么使用最简单的代码即可。

如果你需要处理二十亿个字节，建议检查一下你的处理器是否支持向量指令，并尝试使用它们。你可能会发现你的处理器可以在单个指令中执行32个这样的操作。

- gnasher729

Answer 10

这个怎么样：

bsum = a + b;
bsum = (bsum < a || bsum < b) ? 255 : bsum;

bsub = a - b;
bsub = (bsub > a || bsub > b) ? 0 : bsub;

- user4580220

---

我修复了（显而易见的？）打字错误，但我仍然认为这不正确。 - Bathsheba

这也包括分支。 - fuz

我会删除这个回答，只是一个快速的问题：在没有优化的情况下，在汇编语言中三元运算符和if/else语句之间有什么区别？ - user4580220

@GRC 没有任何区别。 - fuz

@GRC FUZxxl是正确的，但是像往常一样，要自己尝试。即使你不懂汇编语言（如果有什么不清楚的地方，你可以在SO上提问），只要检查长度/指令，你就会知道。 - edmz

大家好，我做到了。与if/else版本不同的是，三元操作符不包含单个跳转语句。 - user4580220