How to tell if a 32 bit int can fit in a 16 bit short

Question

Using only:

! ~ & ^ | + << >>

I need to find out if a signed 32 bit integer can be represented as a 16 bit, two's complement integer.

My first thoughts were to separate the MSB 16 bits and the LSB 16 bits and then use a mask to and the last 16 bits so if its not zero, it wont be able to be represented and then use that number to check the MSB bits.

An example of the function I need to write is: fitsInShort(33000) = 0 (cant be represented) and fitsInShort(-32768) = 1 (can be represented)

Answer 1

bool fits16(int x)
{
    short y = x;
    return y == x;
}

Just kidding :) Here's the real answer, assuming int is 32 bits and short is 16 bits and two's complement represantation:

Edit: Please see the last edit for the correct answer!

bool fits16(int x)
{
    /* Mask out the least significant word */
    int y = x & 0xffff0000;
    if (x & 0x00008000) {
        return y == 0xffff0000;
    } else {
        return y == 0;
    }
}

Without if statements i beleive that should do it:

return (
    !(!(x & 0xffff0000) || !(x & 0x00008000)) ||
    !((x & 0xffff0000) || (x & 0x00008000))
);

Edit: Oli's right. I somehow thought that they were allowed. Here's the last attempt, with explanation:

We need the 17 most significant bits of x to be either all ones or all zeroes. So let's start by masking other bits out:

int a = x & 0xffff8000; // we need a to be either 0xffff8000 or 0x00000000
int b = a + 0x00008000; // if a == 0xffff8000 then b is now 0x00000000
                        // if a == 0x00000000 then b is now 0x00008000
                        // in any other case b has a different value
int c = b & 0xffff7fff; // all zeroes if it fits, something else if it doesn't
return c;

Or more concisely:

return ((x & 0xffff8000) + 0x8000) & 0xffff7fff;

Answer 2

If a 32-bit number is in the range [-32768,+32767], then the 17 msbs will all be the same.

Here's a crappy way of telling if a 3-bit number is all ones or all zeros using only your operations (I'm assuming that you're not allowed conditional control structures, because they require implicit logical operations):

int allOnes3(int x)
{
    return ((x >> 0) & (x >> 1) & (x >> 2)) & 1;
}

int allTheSame3(int x)
{
    return allOnes3(x) | allOnes3(~x);
}

I'll leave you to extend/improve this concept.