CODEWITHSUNDEEP
cbitwise-operatorsinteger-overflow
Sam Tyson
Sam Tyson

Reputation: 61

C checking for overflow during subtraction

I've been trying to determine whether there is overflow when subtracting two numbers of 32 bits. The rules I was given are:

Can only use: ! ~ & ^ | + << >>
 *   Max uses: 20
Example: subCheck(0x80000000,0x80000000) = 1,
 *       subCheck(0x80000000,0x70000000) = 0
No conditionals, loops, additional functions, or casting

So far I have

int dif = x - y; // dif is x - y
int sX = x >> 31; // get the sign of x
int sY = y >> 31; // get the sign of y
int sDif = dif >> 31; // get the sign of the difference
return (((!!sX) & (!!sY)) | (!sY)); // if the sign of x and the sign of y 
                                    // are the same, no overflow. If y is 
                                    // 0, no overflow.

I realize now I cannot use subtraction in the actual function (-), so my entire function is useless anyways. How can I use a different method than subtraction and determine whether there is overflow using only bitwise operations?

Upvotes: 3

Views: 5956

Answers (3)

Jay-Pi
Jay-Pi

Reputation: 428

Please buy and read Hacker's Delight for this stuff. Its a very good book.

int overflow_subtraction(int a, int b, int overflow)
{
    unsigned int sum = (unsigned int)a - (unsigned int)b; // wrapround subtraction
    int ssum = (int)sum;
    // Hackers Delight: section Overflow Detection, subsection Signed Add/Subtract
    // Let sum = a -% b == a - b - carry == wraparound subtraction.
    // Overflow in a-b-carry occurs, iff a and b have opposite signs
    // and the sign of a-b-carry is opposite of a (or equivalently same as b).
    // Faster routine: res = (a ^ b) & (sum ^ a)
    // Slower routine: res = (sum^a) & ~(sum^b)
    // Overflow occured, iff (res < 0)
    if (((a ^ b) & (ssum ^ a)) < 0)
        panic();
    return ssum;
}

Upvotes: 2

Sam Tyson
Sam Tyson

Reputation: 61

Thank you all for your help! Here is what I came up with to solve my issue:

int ny = 1 + ~y; // -y
int dif = x + ny; // dif is x - y
int sX = x >> 31; // get the sign of x
int sY = y >> 31; // get the sign of -y
int sDif = dif >> 31; // get the sign of the difference
return (!(sX ^ sY) | !(sDif ^ sX));

Every case I tried it with worked. I changed around what @HackerBoss suggested by getting the sign for y rather than ny and then reversing the two checks in the return statement. That way, if the signs are the same, or if the sign of the result and the sign of x are the same, it returns true.

Upvotes: 1

HackerBoss
HackerBoss

Reputation: 829

To avoid undefined behavior, I will assume that integers are represented in two's complement, inferred from your calculation of sX, sY, and sDif. I will also assume that sizeof(int) is 4. It would probably be better to use int32_t if you are working only with 32-bit integers, since the size of int can vary by platform.

Since you are allowed to use addition, you can think of subtraction as addition of the negation of a number. A number stored in two's complement may be negated by flipping all of the bits and adding one. This gives the following modified code:

int ny = 1 + ~y; // -y
int dif = x + ny; // dif is x - y
int sX = x >> 31; // get the sign of x
int sNY = ny >> 31; // get the sign of -y
int sDif = dif >> 31; // get the sign of the difference
return ((sX ^ sNY) | (~sDif ^ sX)); // if the sign of x and the sign of y 
                                    // are the same, no overflow. If the
                                    // sign of dif is the same as the signs
                                    // of x and -y, no overflow.

Upvotes: 0

Related Questions