More than a function in C

Question

I know this is an old question, and you probably came across this, but there is a mistake in my solution, and I do not know how to solve it. I need to write a function that compares two integers. I am allowed to use operations (!, ~, &, ^, |, +, →, <<), as well as no control structures (if, more loops, etc.).

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

my idea is simple, we calculate yx, shift by 31 to get the sign bit, if it is negative, then we return zero again, we return 1. This does not work when x negatively and falsely returns 1, although it should return zero, I stuck in it and don't know how to act.

We assume that the integer is 32 bits and uses two additional representations. This question is NOT about portability. Some help would be greatly appreciated.

Thanks in advance

Answer 1

Hacker Delight has a Predicates Comparison section that we need here.

One of the things she writes:

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

We can use almost immediately, except that xand yshould be reversed, the subtraction must be replaced with something legitimate, and the result appears in the upper-bit instead of the LSB. Fortunately, a - b == ~(~a + b)so not too difficult. First apply these 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, they can be simplified a bit by decomposing the subexpression
~(~y + x):

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

Answer 2

First of all, we specify that we assume:

• 2
• int 32 , long long - 64 .
• -

(~x+1) , -x. , INT_MIN INT_MAX, , x INT_MIN, (~x+1) INT_MIN -INT_MIN, .

y+(-x) ( ).

, , int, , long long , , 64- , (~x+1) -x y+(-x) . , , >>31 >>63.

:

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;
}

, x == INT_MIN, x == 0 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));
    }
}

. 163 .

, , int ( long long int).

, int32_t int64_t int long long . :

ISO/IEC 9899: 2011 §6.5.7

5 E1 → E2 - E2 E1. E1 , E1 , E1/2E2. E1 , .