Saturating subtract/add for unsigned bytes

Solution 1:

The article Branchfree Saturating Arithmetic provides strategies for this:

Their addition solution is as follows:

u32b sat_addu32b(u32b x, u32b y)
{
    u32b res = x + y;
    res |= -(res < x);

    return res;
}

modified for uint8_t:

uint8_t  sat_addu8b(uint8_t x, uint8_t y)
{
    uint8_t res = x + y;
    res |= -(res < x);

    return res;
}

and their subtraction solution is:

u32b sat_subu32b(u32b x, u32b y)
{
    u32b res = x - y;
    res &= -(res <= x);

    return res;
}

modified for uint8_t:

uint8_t sat_subu8b(uint8_t x, uint8_t y)
{
    uint8_t res = x - y;
    res &= -(res <= x);

    return res;
}

Solution 2:

A simple method is to detect overflow and reset the value accordingly as below

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

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

GCC can optimize the overflow check into a conditional assignment when compiling with -O2.

I measured how much optimization comparing with other solutions. With 1000000000+ operations on my PC, this solution and that of @ShafikYaghmour averaged 4.2 seconds, and that of @chux averaged 4.8 seconds. This solution is more readable as well.

Solution 3:

For subtraction:

diff = (a - b)*(a >= b);

Addition:

sum = (a + b) | -(a > (255 - b))

Evolution

// sum = (a + b)*(a <= (255-b)); this fails
// sum = (a + b) | -(a <= (255 - b)) falis too

Thanks to @R_Kapp

Thanks to @NathanOliver

This exercise shows the value of simply coding.

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

Solution 4:

If you are using a recent enough version of gcc or clang (maybe also some others) you could use built-ins to detect overflow.

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

Solution 5:

For addition:

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