Thread: Using bitwise operator to see if x>y

  1. #16
    Registered User
    Join Date
    Sep 2012
    Posts
    50
    sorry if u didnt see the requirements:

    we are only allowed to use ! ~ & ^ | + << >> op's

  2. #17
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    In that case, I think that there is nothing wrong with the code you have.

    If it is not working, you are going to have to explain what is not working.
    Fact - Beethoven wrote his first symphony in C

  3. #18
    Registered User
    Join Date
    Sep 2012
    Posts
    50
    isitGreater(-2147483648[0x80000000],2147483647[0x7fffffff]) this will fail due to X overflow.

    what can i do when x is
    0x80000000

  4. #19
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    isitGreater(INT_MAX-1, INT_MIN+1) is another example that doesn't work. There are many similar examples.

    whiteflag's suggestion (casting to a larger type, which I assume you can't do) gave me an idea.
    It's still inchoate, but I'm working on it.

    EDIT: It's turning out to be more complicated than I first thought, but I think it's doable. I should warn you that even if I figure it out, I'm not going to post the answer. In fact, I'm done posting for the night (well, here it's night).
    Last edited by oogabooga; 09-21-2012 at 12:32 AM.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  5. #20
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    Can you use larger variables in your calculations?

    i.e.
    Code:
    
    int isitGreater(int a, int b)
    {
        long int x = (long int) a;
        long int y = (long int) b;
    
    
        ...
    }
    That way you don't have to worry about overflows
    Fact - Beethoven wrote his first symphony in C

  6. #21
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Here are some ideas to help you out:

    • It seems this assignment assumes you are working on a 2's compliment machine. If that's the case, are there other assumptions you can make about the system? How does your compiler behave when right shifting a negative signed number (it's implementation defined per the standard).
    • Does your teacher even expect this to be a standards-compliant program? Is that stated in your assignment anywhere?
    • You are allowed the | and & operator. Does that mean you can use the logical || and && operators? That would simplify things a bit, especially if you can take advantage of short-circuit evaluation.
    • What else are you allowed to use? It seems literals/constants are fine. What about temporary variables?
    • Work with int8_t instead of a regular int. It's only 8 bits, and the smaller numbers will be easier to digest (only -128 to 127), and you can test all possible combinations much more quickly, to guarantee your algorithm works. The algorithm should scale up to regular ints just fine, when the time comes.
    • Break it into several distinct cases, and make each one work independently, then worry about combining them.
    • Consider the edge cases: both x and y are INT_MIN (or INT8_MIN), both are INT_MAX, x is INT_MIN and y INT_MAX, and vice versa.
    • Consider the case where the signs are different. Testing just one bit there should be sufficient.
    • Consider the case where the signs are the same. This is probably the hardest one, but if you've eliminated the corner cases and are sure that x and y aren't at the very limits of their type, then you can probably use your (~x)+1 safely.
    • EDIT: Even without the logical || and && operators, you can achieve the same thing with | and & so long as your bits are all lined up, but you wont have short-circuit evaluation this way.
    Last edited by anduril462; 09-21-2012 at 01:16 AM.

  7. #22
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    OK - I've done it and the numbers that you were having trouble with are now working.

    How I did it was to take the integers into the function unsigned, and the add (unsigned int)(-2147483648) that is (0x8000) to the number.

    From there it was easy! Does b-a set the MSB?
    Last edited by Click_here; 09-21-2012 at 01:29 AM.
    Fact - Beethoven wrote his first symphony in C

  8. #23
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    Hmmm...

    It doesn't work if a is very big and b is very small.
    Fact - Beethoven wrote his first symphony in C

  9. #24
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    @Click_here: The - operator is not allowed. Reread post #8, or #16, to learn what you can and can't do.

  10. #25
    Registered User
    Join Date
    Sep 2012
    Posts
    50
    it's a 32bit machine

  11. #26
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Quote Originally Posted by Lina_inverse View Post
    it's a 32bit machine
    Okay...that doesn't change any advice you've been given so far in this thread. Have you made any progress? Are you stuck on something in particular?

  12. #27
    Registered User
    Join Date
    Sep 2012
    Posts
    50
    still stuck on how to handle the overflow of X, if X is -2147483648[0x80000000] , x will be overflown with my algothrim, and gives an error

  13. #28
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Okay, so you know your algorithm doesn't work, at least, not completely. Thus my advice to break the problem up into separate parts, in particular, dealing with X as INT_MIN.

    Think about it. If X is the smallest possible number, it is ______________ than Y
    A. always greater
    B. sometimes greater
    C. never greater

    Figure out how to code that part independent of your general algorithm. We will worry about combining the two parts later.

    As a side note, you can make a somewhat similar statement about Y, but not with INT_MIN.
    Last edited by anduril462; 09-21-2012 at 10:19 AM.

  14. #29
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by Lina_inverse View Post
    still stuck on how to handle the overflow of X, if X is -2147483648[0x80000000] , x will be overflown with my algothrim, and gives an error
    If you've bothered to read the thread you'll know that there are a lot of other cases for which your attempt fails.

    I've solved it using just ! ~ & ^ | >>
    It assumes 2's complement but it works whether the right shift is arithmetic or logical.
    Using anduril's advice of testing it with signed char, it works on all possible combinations.
    But it's a little complicated so there's probably a simpler solution.

    I can't post the solution, but the test function looks like this:
    Code:
    int main(void) {
        signed char x = SCHAR_MIN, y = SCHAR_MIN;
        do {
            do {
                if ((x > y) != isitGreater_schar(x, y))
                    printf("Error: %d %d\n", x, y);
            } while (y++ < SCHAR_MAX);
        } while (x++ < SCHAR_MAX);
        return 0;
    }
    do-while loops are used to cover the entire range (not possible with for-loops (EDIT: laserlight has pointed out that it is, of course, possible, to do it with a for loop, but it's uglier that way. )).

    My machine uses an arithmetic right shift, so I also used this logical right shift for testing:
    Code:
    // Logical Right-Shift
    int lrs(int x, int n) {
        return (x < 0) ? (x >> n) & INT_MAX :  x >> n;
    }
    Last edited by oogabooga; 09-21-2012 at 10:30 AM.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  15. #30
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    945
    Quote Originally Posted by oogabooga View Post
    My machine uses an arithmetic right shift, so I also used this logical right shift for testing:
    Code:
    // Logical Right-Shift
    int lrs(int x, int n) {
        return (x < 0) ? (x >> n) & INT_MAX :  x >> n;
    }
    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.

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, 02:47 PM
  3. Bitwise Operator Help
    By ggraz in forum C Programming
    Replies: 2
    Last Post: 09-28-2008, 09: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, 01:17 AM

Tags for this Thread