Get the greater of two numbers with bitwise operations

Question

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?

So, the input values are signed or unsigned integers? Are you allowed to use plain `int` too? (It seems like the answer's "yes", but may as well check.) Given the error message, the inputs seem to be signed. Also, we're dealing with 32-bit values, not 64-bit values? This is the sort of sadistic homework question that drives people not in college bonkers; the answer is trivial when you're allowed to use the comparison operators, and ridiculously hard when you aren't — as you aren't. To your credit, you've clearly stated the constraints up front — thank you for that. — Jonathan Leffler, Jan 25 '15 at 21:55
Since you are using signed `int` in your code, every overflow is undefined behaviour. Whether that's actually impacting your answer is less clear, but in theory, you should avoid overflows when the types are signed. — Jonathan Leffler, Jan 25 '15 at 22:00
Apparently negatives are allowed. Theres a test harness that checks for all possible values of input for each of the functions. This function popped up this error. It IS homework, this here is the code I arrived at before running it through the test harness. Thing is, I've tried everything I can think of and theoretically it works with math when I tried, but this error fits into what I've programmed, because as unsigned, the negative number is greater than the other. Yes, 32-bit values; and it drives people who are IN college bonkers as well :) — stalagmite7, Jan 25 '15 at 22:06
OMG I've just reread the question and see that you said isGreater at first but then asked for the **greatest** of 2 numbers — phuclv, Jan 26 '15 at 03:42
@LưuVĩnhPhúc, yeah, the function is called isGreater, where it finds the greatest of two numbers and returns a 1 or a zero depending on whether or not it is true. — stalagmite7, Jan 26 '15 at 06:53
it doesn't find the greatest of the 2, if just returns the comparison between 2 values. A "greatest" function will return max(x, y) — phuclv, Jan 26 '15 at 07:14
possible duplicate of [Bitwise operations equivalent of greater than operator](http://stackoverflow.com/questions/10096599/bitwise-operations-equivalent-of-greater-than-operator) — phuclv, Jan 26 '15 at 11:48
some similar questions: http://stackoverflow.com/questions/14588160/bitwise-operators-for-finding-less-than-in-c http://stackoverflow.com/questions/10096599/bitwise-operations-equivalent-of-greater-than-operator http://stackoverflow.com/questions/12524038/find-if-x-is-bigger-than-y-using-bitwise-operator-in-c — phuclv, Jan 26 '15 at 11:49
@CodesInChaos rightshifting negative values is implementation-defined. — mch, Jan 26 '15 at 12:56

phuclv · Answer 1 · 2015-01-26T12:06:51.513

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

I am not alowed to use loops or conditionals, so no if statements :( Only bitwise operators mentioned in my code block above, can't use anything else. — stalagmite7, Jan 26 '15 at 06:54
@stalagmite7 you could just mux them of course, that doesn't prevent the overflow anymore but that wasn't the problem anyway — harold, Jan 26 '15 at 07:19

score 2 · Answer 2 · answered Jan 26 '15 at 07:40

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

harold · Answer 3 · 2018-07-03T15:28:52.843

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))

(verification)

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.

edited Jul 03 '18 at 15:28

answered Jan 26 '15 at 07:15

harold

61,398
6
86
164

I like your bot. But why does it return false for many expressions in [bit hacks](http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax)? For example with `y ^ ((x ^ y) & -(x < y)) == min(x, y)` it returns `[false] in 0x7fffffff00000000 cases, for example: [y = -1 (0xffffffff), x = -3 (0xfffffffd)]. Also [true] in 0x8000000100000000 cases, for example: [y = -1 (0xffffffff), x = -1 (0xffffffff)]` – phuclv Jan 26 '15 at 12:27
@LưuVĩnhPhúc booleans are 0 or -1 there, so you have to remove that minus. Btw you can make abs like `let m = x >> 31 in x + m ^ m` – harold Jan 26 '15 at 15:16
How can you run a test 2^64 times like that? – phuclv Jan 26 '15 at 16:10
@LưuVĩnhPhúc I don't, I'm not patient enough for that. I convert the expression to a BDD, that is why it works so well for some things (and, or, xor, addition, comparison) and badly or not at all for other things (shifting by a variable, multiplying two variables) – harold Jan 26 '15 at 16:26

Get the greater of two numbers with bitwise operations

3 Answers3

Linked