85

想象一下我有两个无符号字节b和x. 我需要计算bsubasb - x和baddas 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 位操作？

4

11 回答 11

87

文章无分支饱和算术为此提供了策略：

他们的添加解决方案如下：

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;
}
于 2015-11-02T16:17:36.840 回答
40

一个简单的方法是检测溢出并相应地重置值，如下所示

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

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

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

我测量了与其他解决方案相比有多少优化。在我的 PC 上进行 1000000000+ 次操作时，这个解决方案和 @ShafikYaghmour 的解决方案平均为 4.2 秒，@chux 的平均为 4.8 秒。该解决方案也更具可读性。

于 2015-11-02T15:50:29.343 回答
16

减法：

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);
于 2015-11-02T15:45:06.523 回答
13

如果您使用的是最新版本的 gcc 或 clang（可能还有其他版本），您可以使用内置函数来检测溢出。

if (__builtin_add_overflow(a,b,&c))
{
  c = UINT_MAX;
}
于 2015-11-03T06:40:18.980 回答
3

补充：

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

不需要比较运算符或乘法。

于 2015-11-02T20:33:23.650 回答
3

如果您愿意使用汇编或内在函数，我想我有一个最佳解决方案。

减法：

我们可以使用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. Not-ingcarry_flag产生 0，所以!carry_flag * result = 0当有溢出时。并且由于0 - 1将无符号整数值设置为其最大值，如果没有进位，该函数将返回加法的结果，如果有进位，则返回所选整数值的最大值。

于 2015-11-04T16:57:56.957 回答
2

您还可以使用Boost Library Incubator上的安全数字库。它为 int、long 等提供了直接替换，确保您永远不会遇到未检测到的溢出、下溢等。

于 2015-11-02T16:01:23.100 回答
2

一切都可以用无符号字节算术完成

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

// Subtraction without underflow
return (b > a) ? 0 : a - b;
于 2015-11-02T16:44:22.687 回答
2

如果您想用两个字节执行此操作，请尽可能使用最简单的代码。

如果您想用 200 亿字节执行此操作，请检查您的处理器上可用的向量指令以及它们是否可以使用。您可能会发现您的处理器可以使用一条指令执行其中 32 项此类操作。

于 2015-11-03T01:44:31.087 回答
1

那这个呢：

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

bsub = a - b;
bsub = (bsub > a || bsub > b) ? 0 : bsub;
于 2015-11-02T15:45:07.137 回答
1

如果您经常调用这些方法，那么最快的方法不是位操作，而是可能是查找表。为每个操作定义一个长度为 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[A-B];

像这样使用它：

bsub  = MINUS(13,15); // i.e 13-15 with zero cutoff as requested

请注意，执行速度非常快。只有一个减法和一个指针引用才能得到结果。没有分支。静态数组非常短，因此它们将完全加载到 CPU 的缓存中以进一步加快计算速度

同样适用于加法，但表略有不同（前 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=x-y; return y+(d&(d>>31)); }              

inline __int32 MAX_INT(__int32 x, __int32 y){   __int32 d=x-y; return x-(d&(d>>31)); }

我上面的例子使用 32 位整数。您可以将其更改为 64，但我相信 32 位计算运行得更快一些。由你决定

于 2015-11-02T17:31:38.753 回答