sorry if u didnt see the requirements:
we are only allowed to use ! ~ & ^ | + << >> op's
Printable View
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.
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).
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;
...
}
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.
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?
Hmmm...
It doesn't work if a is very big and b is very small.
@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.
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;
}
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.