sorry if u didnt see the requirements:
we are only allowed to use ! ~ & ^ | + << >> op's
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; sorry if u didnt see the requirements: we are only allowed to use ! ~ & ^ | + << ...
sorry if u didnt see the requirements:
we are only allowed to use ! ~ & ^ | + << >> op's
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
isitGreater(-2147483648[0x80000000],2147483647[0x7fffffff]) this will fail due to X overflow.
what can i do when x is 0x80000000
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 01:32 AM.
The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss
Can you use larger variables in your calculations?
i.e.
That way you don't have to worry about overflowsCode:int isitGreater(int a, int b) { long int x = (long int) a; long int y = (long int) b; ... }
Fact - Beethoven wrote his first symphony in C
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 02:16 AM.
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 02:29 AM.
Fact - Beethoven wrote his first symphony in C
Hmmm...
It doesn't work if a is very big and b is very small.
Fact - Beethoven wrote his first symphony in C
@Click_here: The - operator is not allowed. Reread post #8, or #16, to learn what you can and can't do.
it's a 32bit machine
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
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 11:19 AM.
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:
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. )).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; }
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 11:30 AM.
The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss
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.