Like Tree1Likes

Using bitwise operator to see if x>y

This is a discussion on Using bitwise operator to see if x>y within the C Programming forums, part of the General Programming Boards category; Originally Posted by christop That logical right shift doesn't work for negative values (except when n==1). Take x==-5 (0xFFFFFFFB) and ...

  1. #31
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by christop View Post
    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);
    }
    Last edited by oogabooga; 09-21-2012 at 01:10 PM.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  2. #32
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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 ~ & ^ | <<
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  3. #33
    Registered User
    Join Date
    May 2009
    Posts
    2,770
    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.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  4. #34
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

Page 3 of 3 FirstFirst 123
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bitwise operator question
    By f1gh in forum C Programming
    Replies: 1
    Last Post: 12-25-2010, 12:31 PM
  2. bitwise operator
    By donkey_C in forum C Programming
    Replies: 7
    Last Post: 09-26-2010, 03:47 PM
  3. Bitwise Operator Help
    By ggraz in forum C Programming
    Replies: 2
    Last Post: 09-28-2008, 10:20 AM
  4. what does this mean, bitwise operator
    By InvariantLoop in forum C++ Programming
    Replies: 11
    Last Post: 03-09-2006, 07:43 PM
  5. bitwise operator
    By ssharish2005 in forum C Programming
    Replies: 8
    Last Post: 09-30-2005, 02:17 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21