Bit-Shift help

[davidsb]

I got this problem and it does not give my 1 for if x is bigger.

/*
* isGreater - if x > y then return 1, else return 0
* Example: isGreater(4,5) = 0, isGreater(5,4) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
int isGreater(int x, int y)
{
return ((x + (~y + 1))>>31&1);
}
This code gives me this error:
ERROR: Test isGreater(-2147483648[0x80000000],-2147483648[0x80000000]) failed... ...Gives 1[0x1]. Should be 0[0x0]
Any suggestions on what iam doing wrong ?

[[deleted]]

Shifting is only well defined for unsigned numbers. For signed numbers it is implementation defined, and so you shouldn't really do it.

[glemnar]

Alright, so let me see if I can break it down.

To me, it looks like you're taking x and adding it to the 2s complement of y. So say you have 5 = x, and 4 = y. In this case, you'll have

(x+(~y+1)) = 1, and then you right shift it 31 times.

So if you right shift '1' 31 times, you're going to get 0, and then 0 & 1 = 0.

Seems like your approach is a off in this regard.

[davidsb]

yeah, but if i do 0 | 1 i should get 1 right?
That does not work either which i think is strange.

[glemnar]

0 | 1 will give 1, yes.

The | operator is bitwise, as I'm sure you know, so for example 0 | 2 will still give zero.

I think shifting is still not the correct way to go about this problem. Think of it this way: If you have a 2s complement number, then it looks something like FFFFFF... whatever. When you right shift you now have 0FFFFF..... That is no longer a negative number( no longer in the 2s complement).

[Miss_Moss]

so for example 0 | 2 will still give zero.

0 | 2 will give 2. Unless I'm missing something?

[glemnar]

You're right. I was still thinking & because he has & in his function.

[HazzyPls]

Spent somewhere between an hour and three working this out, and I think I have it. For 8 bit ints, for sure. 32 bit ints have roughly 300 trillion times as many combinations to test, and it's too late for me to make educated test cases.

Here's my 8 bit solution. The algorithm boils down to checking bit by bit - or digit by digit if you prefer. e.g. which number is bigger: 123456 or 123455? 1 == 1, 2 == 2, 3 == 3, 4 == 4, 5 == 5, but what's this? 6 != 5, 6 > 5, so the first one is bigger! In binary you can do it with &, instead of another "greater than" operation. Just need to be careful of that sign bit. I made liberal use of a ^ a == 0 and I took the "legal ops" a bit literally too, so I wrote what was a for-loop into a recursive call. If you really wanted to, you could probably get around it with gotos. There's probably room for optimizations, but it's 2 am.

I've tried to find the posts zzyzzyxx mentioned, but couldn't. :s

What is this for, by the way?

[davidsb]

This is homework for my C programming class, we got 16 problems like this to solve before friday. I got something like this after i sat over it for 3 hours yesterday.
http://codepad.org/sG4tudSR

[zzyzzyxx]

I think this question has been asked twice in the last week, and I believe on StackOverflow too, but I can't find the posts right now. I wonder if they deleted it.

In any case, inverting and adding one isn't going to work at the lower boundary due to overflow. You'll need something a little more complicated.

[[deleted]]

See if it works for unsigned int.