Determining if an Int Fits into a Short in C using Bitwise Operators

I am tasked with making a function that returns whether or not an int x fits into a short in C (return 1 if it does, 0 otherwise). This would normally be a fairly simple solution, but I'm constrained to using only the following bitwise operators:! ~ & ^ | + << >>.

Here are some more rules:

• I am only allowed to use a maximum of 8 of these operators.

• No external libraries are to be included.

• I'm not allowed to use any conditional statements (so no ifs, whiles, etc).

• The only variables I can work with are those of type int and I cannot define constants like 0x0000ffff. However, I can use 0x0and 0xff.

• It is safe to assume ints are 32 bits and shorts are 16 bits.

I understand the basic functionalities of these operators, but am confused on the logic of implementation. Any ideas?

Supposing two’s complement, arithmetic right-shift, left-shift that discards overflowing bits, and 32-bit int, then:

x<<16>>16 ^ x

is zero if and only if x fits in a 16-bit short.

Since we are asked to return zero for does-not-fit and one for does-fit, we can return:

! (x<<16>>16 ^ x)

Proof:

If x fits in a short, then x•2¹⁶ fits in an int, so x<<16 produces that with no overflow, and x<<16>>16 restores x (since arithmetic shift right that only removes zeros is effectively a division with no remainder), after which x ^ x is zero.

If x exceeds a short, then x<<16 overflows (which we assume results in discarding the high bits). Furthermore, its value is one of the values produced by y<<16 for some y that is a short. Then x<<16>>16 must produce the same value as y<<16>>16, which is y, which differs from x, and therefore x<<16>>16 ^ x cannot be zero.