I have to find the greater of two numbers using bit manipulation. These are the rules for the same:

```
/*
* isGreater - if x > y then return 1, else return 0
* Example: isGreater(4,5) = 0, isGreater(5,4) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
*/
```

This is the code I've written for this:

```
int isGreater(int x, int y) {
/* to find greater, subtract y from x using 2's complement method.
* then find 2's complement of the answer and shift right by 31 to give MSB
* which is 1 if x>y and 0 if x<y */
int ydash=(~y)+0x01;
int diff=x+ydash;
int a=(~diff)+0x01;
int b=a>>31;
int c=b&0x01;
return c;
}
```

For which I get this error:

ERROR: Test isGreater(-2147483648[0x80000000],2147483647[0x7fffffff]) failed... ...Gives 1[0x1]. Should be 0[0x0]

I'm allowed to use unsigned int, but no other data types. I'm not sure how that'd help though. How do I get around this?

With x = -2147483648 and y = 2147483647 then x - y = -4,294,967,295 which is outside the range of `int`

, hence the result cannot be represented in the variable and you got undefined behavior.

To get over this you need to use a type wider than int. As you are only allowed to use unsigned int, you'll have to implement big int operations yourself if you want to use a bigger type. You can also use another way like checking the overflow condition separately

```
if ((x ^ y) & 0x80000000) // x and y have different sign
{
return (y >> 31) & 1; // return 1 if y is negative
}
else // x and y have the same sign, overflow never occurs
{
unsigned int xu = x, yu = y;
unsigned int xmu = ~xu + 1U;
unsigned int diffu = yu + xmu;
return diffu >> 31;
}
```

If you aren't allowed to use conditionals you can use a muxer to mux the values

```
unsigned int r1 = (y >> 31) & 1U; // 1st case
unsigned int xu = x, yu = y;
unsigned int xmu = ~xu + 1U;
unsigned int diffu = yu + xmu;
unsigned int r2 = diffu >> 31; // 2nd case
unsigned int s = ((x ^ y) >> 31) & 1U; // s = 1 if x and y have different sign, 0 otherwise
unsigned int mask = 0xFFFFFFFFU + s;
return (r1 & ~mask) | (r2 & mask);
```

Here you may not be allowed use if-else or any of the control statements. But you can "construct" some if-else-like statement.

```
int isGreater(int x, int y) {
int sgnext_x = x >> 31; //sgnext_x = x >= 0 ? 00000000 : 11111111
int sgnext_y = y >> 31;
int sgn_y = sgnext_y & 1; //sgn_y = y >= 0 ? 0 : 1
int minus = x + (~y + 1); // a - b = a + (~b+1)
int sgn_minus =(minus >> 31) & 1;
//A control-like statement. ((statement & a) | (!(statement | (b))))
//Returns a if statment = 11111111
//Returns (b&1) if statment = 00000000
int which = sgnext_x ^sgnext_y;
int result = (!!(x^y)) & ((which & sgn_y) | (!(which | (sgn_minus))));
return result;
}
```

answered on Stack Overflow Jan 26, 2015 by pwwpche

The algorithm you came up with fundamentally doesn't work, since if you subtract, almost all possible answers can be both the result of a subtraction where `a < b`

and of a subtraction where `a >= b`

. So essentially, the result doesn't tell you anything, except when it's zero then you know that `a == b`

.

Hacker's Delight has this answer in chapter 2.11, Comparison Predicates:

```
x < y: (x & ~y) | ((x ^ ~y) & (x - y))
```

You know how to implement subtraction in terms of addition, and swapping `x`

and `y`

shouldn't be a problem either. The result appears in the sign bit.

User contributions licensed under CC BY-SA 3.0