Greater than function in C

user_3047143 0
Viewed 2862

I know this is an age old question and you probably have come across this aswell, but there's a bug in my solution and I don't know how to solve it. I need to write a function that compares two integers. I am only allowed to use the operations (!,~,&,^,|,+,>>,<<) and also no control structures(if,else loops etc).

isGreater(int x, int y) {
    //returns 1 if x > y.
      return ((y+(~x+1))>>31)&1;
}

my idea is simple, we compute y-x, we shift by 31 to get the sign bit, if it's negative, then we return zero else we return 1. This fails when x is negative and falsly returns 1 although it should return zero. I'm stuck at this and don't know how to proceed.

We assume that integer is 32bits and uses two's complement representation. This question is NOT about portability. Some help would be much appreciated.

Thanks in advance

bitwise-operators c
2 Answers

Hacker's Delight has a chapter Comparison Predicates, which is exactly what we need here.

One of the things it writes is:

x < y: (x - y) ^ ((x ^ y) & ((x - y) ^ x))

Which we can use almost directly, except that x and y should be swapped, the subtractions must be replaced by something legal, and the result appears in the top bit instead of the lowest bit. Fortunately a - b == ~(~a + b) so that's not too hard. First applying those transformations:

// swap x <-> y
(y - x) ^ ((y ^ x) & ((y - x) ^ y))
// rewrite subtraction
~(~y + x) ^ ((y ^ x) & (~(~y + x) ^ y))
// get answer in lsb
((~(~y + x) ^ ((y ^ x) & (~(~y + x) ^ y))) >> 31) & 1

I have a website here that says it works.

If local variables are allowed it can be simplified a bit by factoring out the subexpression
~(~y + x):

int diff = ~(~y + x);
return ((diff ^ ((y ^ x) & (diff ^ y))) >> 31) & 1;
user_5550450

First of all let's clarify that we assume:

  • negative integers are represented in 2's complement
  • int is exactly 32 bits wide and long long is exactly 64 bits wide
  • right shifting a negative number is an arithmetic shift

There is a problem with the (~x+1) part in your solution which is supposed to return -x. The problem is that the absolute value of INT_MIN is greater than the absolute value of INT_MAX, thus when x is INT_MIN then (~x+1) yields INT_MIN instead of -INT_MIN as you expected.

There's also a problem with overflows in the y+(-x) part of your solution (second step).

Now if you're allowed to use other types than int, we can solve both of these problems by casting the values to long long before the conversion, assuming that it's a 64-bit type, so that (~x+1) would return the expected result -x and y+(-x) would not cause any overflows. Then, obviously, we will have to change the >>31 bit to >>63.

The end solution is as follows:

static bool isGreater(int x, int y)  {
    long long llx = x;
    long long lly = y;
    long long result = ((lly+(~llx+1))>>63)&1;
    return result;
}

It's feasible to test it with some corner-cases, such as x == INT_MIN, x == 0 and x == INT_MAX:

int main(void) {
    int x = INT_MIN;
    for (long long y = INT_MIN; y <= INT_MAX; ++y) {
        assert(isGreater(x, y) == (x > y));
    }
    x = INT_MAX;
    for (long long y = INT_MIN; y <= INT_MAX; ++y) {
        assert(isGreater(x, y) == (x > y));
    }
    x = 0;
    for (long long y = INT_MIN; y <= INT_MAX; ++y) {
        assert(isGreater(x, y) == (x > y));
    }
}

This was successful on my particular machine with my particular compiler. The testing took 163 seconds.

But again, this depends on being able to use other types than int (but then again with more work you could emulate long long with int).

This whole thing could be more portable if you used int32_t and int64_t instead of int and long long, accordingly. However, it still would not be portable:

ISO/IEC 9899:2011 §6.5.7 Bitwise shift operators

5 The result of E1 >> E2is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

user_85902920
Related