减去/添加值而不会出现溢出或下溢

Question

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

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

Answer 2

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

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

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

当使用-O2进行编译时,GCC可以将溢出检查优化为条件赋值.

我测量了与其他解决方案相比的优化程度.在我的PC上运行了100万次以上,这个解决方案和@ShafikYaghmour的平均时间为4.2秒,而@chux的平均时间为4.8秒.此解决方案也更具可读性.

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

感谢@R_Kapp

感谢@NathanOliver

本练习显示了简单编码的价值.

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

Answer 4

如果您使用的是最新版本的gcc或clang(也许还有其他版本),您可以使用内置函数来检测溢出.

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