How to determine if a 32-bit int can hold 16 bits

Question

Use only:

! ~ & ^ | + << >> 

I need to find out if a 32-bit integer can be represented as a 16-bit integer.

My first thoughts were to separate the MSB 16 bits and the LSB 16 bits, and then use the mask and the last 16 bits, so if it is not equal to zero, it cannot be represented, and then use this number to check the MSB.

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

Answer 1

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

Just kidding :) Here is the real answer, assuming int is 32 bits and short is 16 bits and two representations:

Edit: see the latest change 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 statements that should do this:

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

Edit: Oli is correct. For some reason I thought they were allowed. Here's the last attempt with an explanation:

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

 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 briefly:

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

Answer 2

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

Here's a crappy way of saying whether a 3-bit number is one or all zeros using only your operations (I assume you are 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 will leave you to expand / improve this concept.

Answer 3

Here is a solution without casting, if-statements and using only those operators that you requested:

 #define fitsInShort(x) !(((((x) & 0xffff8000) >> 15) + 1) & 0x1fffe) 

Answer 4

 if (!(integer_32 & 0x8000000)) { /* if +ve number */ if (integer_32 & 0xffff8000) /* cannot fit */ else /* can fit */ } else if (integer_32 & 0x80000000) { /* if -ve number */ if ( ~((integer_32 & 0xffff8000) | 0x00007fff)) /* cannot fit */ else /* can fit */ } 

First, if Checks the number + ve first, checking the bit-bit. If + ve, then it checks if bit 15 is equal to bit 31, if 0, then it cannot fit into short , otherwise it can.

A negative number corresponds to the range if bit 15-31 is set (representation of the complement method).

Therefore, the second if is the number -ve, then bit 15-31 is masked, and the remaining least significant bits (from 0 to 14) are set. If it is 0xffffffff , then only one complement will be 0 , which indicates that bit 15-31 is set, so it can fit (part of else), otherwise it cannot match (condition if).

Answer 5

 short fitsInShort(int x) { int positiveShortRange = (int) ((short) 0xffff / (short) 2); int negativeShortRange = (int) ((short) 0xffff / (short) 2) + 1; if(x > negativeShortRange && x < positiveShortRange) return (short) x; else return (short) 0; }