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?
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.