Using bitwise operators to determine if one number is greater than another

All,

First post. Hope to stick around.

I got an assignment yesterday dealing with bits and bytes and C. There's a variety of functions we have to write that replicate operators using bitwise operations. The one I'm stuck on (this time, anyway...) is one that accepts to integers and then returns 1 if the first is greater than the second.

We're only allowed to use bitwise operators along with + and !, and the code has to be straight line. No functions, loops, etc. No unsigned ints permitted.

Here's what I came up with so far:

Code:

int greaterThan(int first, int second){
     // first > second means second - first is less than 0
    // shift the sign bit and then compare it to 1
    return (second + (~first +1)) >> 31 & 1;
}

This works fine in a lot of cases, but I think when I get to values like the negative max, the output is incorrect. I'm assuming it has to do with some kind of overflow on the addition, but I'm unsure of how to actually fix it without the use of conditionals.

Thanks.

It will also fail for any variable that is not 32 bits in size.

If (first + second) is less than either operand then you know the comparison will overflow. That's the trouble with the math for this. You could return an overflow code in that case. The real operation never fails because it boils down to a processor instruction. Understanding how that works involves understanding ALUs. So there you go.

No unsinged ints?! Wow, that's harsh.

By the way, don't just assume it will or wont work, write a bunch of unit tests like this:

Code:

assert(greaterThan(0x80000000, 0x7FFFFFFF) == 1);
assert(greaterThan(0x7FFFFFFF, 0x80000000) == 0);

Make sure you also have cases that test with both inputs being equal.

When they all pass, you're either done or you're tests are inadequate.

Originally Posted by CommonTater

It will also fail for any variable that is not 32 bits in size.

Yes, I know. It's an assumption we're allowed to make.

Originally Posted by whiteflags

If (first + second) is less than either operand then you know the comparison will overflow. That's the trouble with the math for this. You could return an overflow code in that case. The real operation never fails because it boils down to a processor instruction. Understanding how that works involves understanding ALUs. So there you go.

What do you mean "less than either operand"? Also, I understand that the math
doesn't literally stop working. But I still have to spit out the right answer, and if I remember correctly, we can't throw an overflow code.

Originally Posted by iMalc

No unsinged ints?! Wow, that's harsh.

By the way, don't just assume it will or wont work, write a bunch of unit tests like this:

Code:

assert(greaterThan(0x80000000, 0x7FFFFFFF) == 1);
assert(greaterThan(0x7FFFFFFF, 0x80000000) == 0);

Make sure you also have cases that test with both inputs being equal.

When they all pass, you're either done or you're tests are inadequate.

If it wasn't harsh, I wouldn't be posting here

And yes, I know that we should test with a variety of cases. I also know that it fails when using +/- max/mins of int. I know THAT it fails, I'm just unsure of how to make it...stop failing.