# Using bitwise operator to see if x>y

Show 80 post(s) from this thread on one page
Page 3 of 3 First 123
• 09-21-2012
oogabooga
Quote:

Originally Posted by christop
That logical right shift doesn't work for negative values (except when n==1). Take x==-5 (0xFFFFFFFB) and n==2, for example. Shifting x right (arithmetically) by 2 bits gives -2 (0xFFFFFFFE). ANDing that with INT_MAX (0x7FFFFFFF) gives 0x7FFFFFFE. Shifting -5 right logically by 2 bits would give you 0x3FFFFFFE.

Excellent. Thanks. Here's a rewrite. The overall alg still seems to work.
Code:

```// Logical Right-Shift int lrs(int x, int n) {     if (x < 0) {         x = (x >> 1) & INT_MAX;         n--;     }     return (n > 0) ? x >> n : x; }```
EDIT: The above is overly-complicated. All you need do is this:
Code:

```int lrs(int x, int n) {     return (int)((unsigned)x >> n); }```
• 09-23-2012
oogabooga
Here's a hint for anyone interested in trying this.

To find the answer, you only have to compare 1 bit -- the highest order bit where the two numbers differ.

So the first trick is to create a bit-mask with a 1 in the highest order bit where the two numbers differ and 0's elsewhere. Exclusive-or (which leaves 1's everywhere the bits differ) and a technique known as "bit-smearing" are useful here. Bit-smearing turns this
00100101
into this
00111111 (highest-order 1 bit is "smeared out" over the lower-order bits)

It's done like this (z is the value to smear)
Code:

```z |= z >> 16; // leave out this one ... z |= z >> 8;  // ... and this one to test with just 8 bit numbers z |= z >> 4; z |= z >> 2; z |= z >> 1;```
Does anyone know a way of solving this problem without using the above technique? To restate the problem (as the OP has given it) : write this function
Code:

```int isitGreater(int x, int y) {     // Return 1 if x is greater than y, 0 otherwise.     // Use only these operators and no control statements (if, for, etc)     // ! ~ & ^ | + << >>     // I've assumed that you can create local variables. }```
I personally don't see how the + is going to come into it, at least not in the naive way since it has problems with overflow. My solution uses ! (in the common !! way to return 1 or 0 from non-zero or zero) and ~ & ^ | <<
• 09-23-2012
stahta01
I think I have an glimmer of an idea on how to do it.
It assumes you are allowed to cast between signed and unsigned values.
I would write my own minus function using the allowed operators.
I think being able to cast to long might also be needed.

Tim S.
• 09-23-2012
oogabooga
I was able to remove the local variable from my solution. So it's possible with no locals or casting and without + (or -, which is not allowed anyway).

But it's pretty unintelligible and has taken me at least 6 hours of total time.
Show 80 post(s) from this thread on one page
Page 3 of 3 First 123