7 replies to this topic

[jaberwocky6669]

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/

[Mat]

Off the top of my head, something like this would work (if you think 0 is positive):

Spoiler

((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 by Mat, 22 September 2012 - 05:54 PM.

[Richard Robertson]

Why are we doing some reddit user's homework?

[jaberwocky6669]

Practice. I don't intend to post the solution back to Reddit.

[Mat]

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 by Mat, 23 September 2012 - 05:45 PM.

[jaberwocky6669]

It can be unrolled but what about 64 bit systems?

[Mat]

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:

Spoiler

Plain Text        expandcollapse  popup

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:

Spoiler

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 by Mat, 23 September 2012 - 06:37 PM.

[Shaggi]

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.

Spoiler

Plain Text        expandcollapse  popup

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 by Shaggi, 27 September 2012 - 12:05 AM.