Signed saturated addition with only bitwise operations

[batchprogram]

I'm doing some homework for a computer systems class and all is well except this one problem that I can't seem to find a solution to due to the limitations.

The problem requires me to write a function that performs addition on 32-bit signed integers but saturates the result to -21474... when there would be underflow, and 21474... when there would be overflow. The limitations are it can only be written with bitwise operations, addition, and subtraction(meaning no control statements, functions, macros, division, multiplication, modulus, comparisons, casting, and no resources from libraries).

I have attempted to write this several times but to no avail, however I have figured out how to get some information.

const int SINT32_MIN = 0x80000000;
const int SINT32_MAX = 0x7FFFFFFF;
 
int SaturatingAdd(int a, int b)
{
	// Determine if the signs are different. Under/Overflow is impossible if the signs differ.
	bool sdiff = !((a & 0x80000000) ^ (b & 0x80000000));
	return something;
}

This is a solution I came up with using some of the limitations.

const int SINT32_MIN = 0x80000000;
const int SINT32_MAX = 0x7FFFFFFF;
 
int SaturatingAdd(int a, int b)
{
	long sum = (long)a + (long)b;
	if (sum <= SINT32_MIN) return SINT32_MIN;
	if (sum >= SINT32_MAX) return SINT32_MAX;
	return (int)sum;
}

[Abramus]

I think you cannot use "!" as this is logical operator, not bitwise.

Based on your solution I would guess "long" is 64-bit on your system? Can you use 64-bit integers in this assignment?

Anyway, here is my proposition (I assume you can use 64-bit integers):
1) To detect overflow/underflow, you can XOR sum calculated using 32-bit integers with sum calculated using 64-bit integers - if the result is zero then an overflow/underflow didn't happened, otherwise you will get a non-zero value (0xFFFFFFFF00000000 to be precise).
2) To distinguish between overflow and underflow, you can check sign of the 64-bit sum.

Now we have a problem - how to implement conditional statement without using conditional statement? I will give you an example. Lets say you want to set "z" to "x" if some condition is met, or to "y" otherwise. You can do it like this: z = (mask & x) | (~mask & y), where "mask" is equal to 0xFFFFFFFF if the condition is met, or 0 otherwise.

OK, so how to create this mask? For (1) it is simple, you can get either 0 or 0xFFFFFFFF00000000, so if you shift the value right by 32 bits you will have 0 or 0xFFFFFFFF. For (2) it is a little more complicated, as we will have either 0 or 0x8000000000000000. So we must propagate this one bit, like this:

x = 0x80000000;
x |= x >> 1;  // x = 0xC0000000
x |= x >> 2;  // x = 0xF0000000
x |= x >> 4;  // x = 0xFF000000
x |= x >> 8;  // x = 0xFFFF0000
x |= x >> 16; // x = 0xFFFFFFFF 

This is everything you need to know in order to complete the program. Hope this helps.