CODEWITHSUNDEEP
cbit-manipulationadditionsaturation-arithmetic
Zach
Zach

Reputation: 61

Saturating signed integer addition with only bitwise operators in C (HW)

For a homework assignment, I have to write a function in C that adds together two signed integers, but returns INT_MAX if there would be positive overflow and INT_MIN if there would be negative overflow. I have to follow very strict restrictions in what operators I can use. All integers are in two's complement form, right shifts are arithmetic, and the integer size is variable (I can find it with sizeof(int)<<3). I can't use contitionals, loops, comparison operators, or casting. I can only use bitwise and logical operators, addition and subtraction, equality tests, and the integer constants INT_MAX and INT_MIN.

I know that overflow can be detected if the two inputs have the same sign and the result has a different sign. I've gotten to the point where I have a flag showing if the equation did overflow. I have no idea how to get from there to the end product. This is what I have so far: 

int saturating_add(int x, int y){
    int w = sizeof(int)<<3;
    int result = x+y;
    int signX = (x>>w-1)&0x01;//Sign bit of X
    int signY = (y>>w-1)&0x01;//Sign bit of Y
    int resultSign = (result>>w-1)&0x01; //Sign bit of result
    int canOverflow = ~(signX ^ signY); //If they're the same sign, they can overflow
    int didOverflow = (resultSign^signX)&canOverflow; //1 if input signs are same and result sign different, 0 otherwise

}

I'm trying to follow the answer shown at Bitwise saturated addition in C (HW), but I'm stuck on the part where I have to fill an integer with the same bit for all but the sign bit (1 goes to 0111..11 and 0 goes to 0000.00). I have no idea what the "combination of shifts and ORs" would be.

Upvotes: 4

Views: 4015

Answers (1)

Yoctohan
Yoctohan

Reputation: 121

I think you misunderstood the answer. What you should do is extend the sign bit to all of the bits, including the MSB. This can be accomplished by taking the int holding the sign bit, e.g. didOverflow, and add 1 to its complement.

Then you find which overflow value should be returned in the case that there is an overflow. That can be done by XORing INT_MAX with extended signX (or signY, both will work). Let's call this value overflow. Finally, alter overflow and result like this:

overflow := (extended didOverflow) AND overflow
result := (NOT (extended didOverflow)) AND result

Now, after these assignments, if the extended didOverflow is 1...1, then overflow will obviously remain unchanged. result, on the other hand, will be equal 0.

But if didOverflow is 0...0, then the opposite applies: overflow is now 0, while result remains unchanged.

In the first case (where didOverflow was 1...1, signaling that there was an overflow), overflow OR result equals overflow. In the second case (where we have no overflow), overflow OR result equals result. So either way, overflow OR result will give us the correct value.

Upvotes: 2

Related Questions