Thread: Using bitwise operator to see if x>y

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

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 ~ & ^ | <<

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.

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.