jaberwacky Posted September 22, 2012 Share Posted September 22, 2012 Sorry if you're a redditor and seen this already. If you know the answer fifteen seconds after reading the question then how about using a spoiler tag in your answer so that you won't ruin it for the rest of us? Post follows (edited for clarity): "Given a signed integer, I'm trying to return 1 for positive, 0 for 0, and -1 for negative. The catch is that I can only use bitwise operators (! ~ ^ | + << >>) (and some non bitwise characters too) and I can't declare an integer value greater than 0xFF. My plan is to right shift 31 places, so the MSB is in the LSB spot. Once there, I perform an &1. If the result is 1, I know I have a negative number. So far I've got: int sign(int x) { return ((x>>31)&1); } The part that's giving me trouble is getting it to return 1 for a positive number and -1 for a negative number. I've tried countless different solutions, but when it returns the proper value for one it returns the wrong value for the others. I've been working in circles for hours and I'm about to lose my mind. Any help would be appreciated." http://www.reddit.com/r/C_Programming/comments/105von/how_to_check_positivezeronegative_using_bitwise/ Helpful Posts and Websites: AutoIt3 Variables and Function Parameters MHz | AutoIt Wiki | Using the GUIToolTip UDF BrewManNH | Can't find what you're looking for on the Forum? Link to comment Share on other sites More sharing options...
Mat Posted September 22, 2012 Share Posted September 22, 2012 (edited) Off the top of my head, something like this would work (if you think 0 is positive): ((x >> 31) << 1) ^ 1 Shifts are tricky when you are dealing with signed integers. I don't think you can simplify the << and >> into a single >>. No doubt there are more elegant solutions. Edit: Just checked the reddit page... There are a lot of rubbish answers not using bitwise operators. I would have expected more people to be able to give a good answer to this question, it really isn't that hard. Edit: I suspect it isn't possible to get the correct result for zero without using x more than once. Edit again: Not even this page does it using only bitwise operations: http://bits.stephan-brumme.com/sign.html, is it even possible to negate a 2s complement number using just bitwise? Edited September 22, 2012 by Mat AutoIt Project Listing Link to comment Share on other sites More sharing options...
Richard Robertson Posted September 22, 2012 Share Posted September 22, 2012 Why are we doing some reddit user's homework? Link to comment Share on other sites More sharing options...
jaberwacky Posted September 23, 2012 Author Share Posted September 23, 2012 Practice. I don't intend to post the solution back to Reddit. Helpful Posts and Websites: AutoIt3 Variables and Function Parameters MHz | AutoIt Wiki | Using the GUIToolTip UDF BrewManNH | Can't find what you're looking for on the Forum? Link to comment Share on other sites More sharing options...
Mat Posted September 23, 2012 Share Posted September 23, 2012 (edited) Given this a fair bit of thought, and this is possible to do using purely bitwise operators, as increment and decrementing are as well provided you know the size of the integers in advance. Quick example of dec is: int dec(int x) { int i = 1; for (int c = 0; c < 32; c++) { x ^= i; i = x & i; i <<= 1; } return x; } For those who are about to point out there is a loop, it's just to make it easier to read, it can be unrolled. Edited September 23, 2012 by Mat AutoIt Project Listing Link to comment Share on other sites More sharing options...
jaberwacky Posted September 23, 2012 Author Share Posted September 23, 2012 It can be unrolled but what about 64 bit systems? Helpful Posts and Websites: AutoIt3 Variables and Function Parameters MHz | AutoIt Wiki | Using the GUIToolTip UDF BrewManNH | Can't find what you're looking for on the Forum? Link to comment Share on other sites More sharing options...
Mat Posted September 23, 2012 Share Posted September 23, 2012 (edited) It can be unrolled but what about 64 bit systems? It can still be unrolled... Should probably have written: "c < sizeof(int)*8" but as I said, it was a small demo. With this in mind it is possible to negate an integer using just bitwise ops. This means that the method described here is possible using just bitwise ops. Complete code is: int inc(int x) { int i = 1, t; for (int c = 0; c < sizeof(int)*8; c++) { t = x & i; x ^= i; i = t << 1; } return x; } int neg(int x) { return inc(~x); } int sign(int x) { int minusOne = x >> 31; int plusOne = (int)((unsigned int)neg(x) >> 31); return minusOne | plusOne; } Or slightly shorter and more unreadable: int inc(int x) { int i = 1; for (int c = 0; c < sizeof(int)*8; c++) { x ^= i; i = ((x ^ i) & i) << 1; } return x; } int sign(int x) { return (x >> 31) | (int)((unsigned int)inc(~x) >> 31); } Just note this really is for academic purposes only. It misses out on all the optimisation usually done by inc, as it processes every bit, regardless of how many need processing. Edited September 23, 2012 by Mat AutoIt Project Listing Link to comment Share on other sites More sharing options...
Shaggi Posted September 26, 2012 Share Posted September 26, 2012 (edited) Well this had me bugged for hours... relies on some stuff like negatives shifted right will yield -1 at least. have not tested with anything else than x32. also, im not sure this counts since it's using an add operation to determine whether an integer is zero.. maybe this could be computed some other way. but it works so far. signed int det_sign(signed int x) { /* yields -1 or 0xFFFFFFFF for negative integers, yields zero for positive need to keep x signed.. probably not portable lol */ unsigned int sign = signed(x) >> (CHAR_BIT * sizeof(int) - 1); /* yields 1 for non-zero */ unsigned int nonzero = unsigned(~x + 1) >> 31; std::cout << "nonzero = " << nonzero << std::endl; std::cout << "sign = " << sign << std::endl; /* possible outcomes here: 1 ... 1 | 1 = -1 (negative | not zero) 0 ... 0 | 1 = 1 (positive | not zero) 0 ... 0 | 0 = 0 (positive | zero) */ return sign | nonzero; } //bits in an int -1 #define SIZ (CHAR_BIT * sizeof(int) - 1) //compact version signed int quick_sign(signed int x) { return unsigned(signed(x) >> SIZ) | unsigned(((x | (~x + 1)) >> SIZ) & 1); } //even quicker, not sure if welldefined signed int quicker_sign(signed int x) { return unsigned(x >> SIZ) | unsigned(~x + 1) >> SIZ); } e: typos, formatting, e2: spoilered, e3: reading over assignment again, + is allowed so this solution is valid Edited September 27, 2012 by Shaggi Ever wanted to call functions in another process? ProcessCall UDFConsole stuff: Console UDFC Preprocessor for AutoIt OMG Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now