# Get the greater of two numbers with bitwise operations

0

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?

c
comparison
max
bit-manipulation
asked on Stack Overflow Jan 25, 2015 by stalagmite7 • edited Dec 19, 2019 by phuclv

2

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;
``````
answered on Stack Overflow Jan 26, 2015 by phuclv • edited Jan 26, 2015 by phuclv
2

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
1

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.

answered on Stack Overflow Jan 26, 2015 by harold • edited Jul 3, 2018 by harold

User contributions licensed under CC BY-SA 3.0