How to perform addition of two vectors of 8-bit integers with a single addition in C/C++

Question

From my reading of this answer, it is possible to perform addition of two pairs of 4-bit integers, stored in 8-bit integers, with just one addition and some bitwise operations. Also, the author of that answer states it should be easy to generalize that method a bit. Thus, I try to generalize this method to the addition of two vectors, each consisting of four 8-bit integers, stored in 32-bit integers.

uint32_t a, b;

uint32_t c = a + b;
uint32_t r = a ^ b ^ c; // calculate all carry
uint32_t s = r & (0x01010100); // carry of only the digits that we care
uint32_t sum = c - s; // undo the carry on these digits

This code works for most input, but I found exceptions when I try to add integers that are basically complement form of negative numbers close to 0. For example, if I set

a = 0xfffeff00 // (-1,-2,-1, 0)
b = 0x01010100 // ( 1, 1, 1, 0)

expected result is 0x00ff0000. It runs

c = 0x01000000 // ( 1, 0, 0, 0)
r = 0xfffffe00 // (-1,-1,-2, 0)
s = 0x01010000 // ( 1, 1, 0, 0)
sum=0xffff0000 // (-1,-1, 0, 0)

The first two digits of sum becomes ff (which represents -1), but the correct number should be 0. This is because when subtracting c = 01 00 00 00 with s = 01 01 00 00, the subtraction of the second group overflows and affects the result on the first group.

I want to improve the last step to get rid of this problem, but can't figure a good solution.

Answer 1

The following is a solution:

    uint32_t c = (a & 0x7f7f7f7f) + (b & 0x7f7f7f7f);
    uint32_t d = (a & 0x80808080) + (b & 0x80808080) + (c & 0x80808080);
    uint32_t sum = (c & 0x7f7f7f7f) | (d & 0x80808080);

The idea is to first add the lower 7 bits of each octet which gives the correct lower 7 bits of each octet of the result without spilling carries into the next octet. Then add the upper bits of each octet along with the carries from the first addition to get the correct upper bit of each octet of the result. Finally, the result is "glued" together from the correct bits in each part.

Update 1: As correctly commented, this can be simplified by replacing the second line with:

    uint32_t d = a ^ b ^ c;

Update 2: Following this line of thought, XOR can be used to add the upper bits directly into the 7-bit sums giving the following solution:

    uint32_t sum = ((a & 0x7f7f7f7f) + (b & 0x7f7f7f7f)) ^ ((a^b) & 0x80808080);