CODEWITHSUNDEEP
carchitecturebinarybit-manipulation
user10992941
user10992941

Reputation:

How to Determine if an Int is 16 Bits

I'm working with bitwise and logical operators in C. I'm familiar with concept and purpose of these operators, but have run into bit of a problem.

I need to determine whether an integer x can fit into a short. I am restricted to using the operators ! ~ & ^ | + << >>. Also, I can only use up to 8 of these operators.

I know from several other posts (like this one: How to tell if a 32 bit int can fit in a 16 bit short) that a solution like

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

would work just fine (credit to Emil Romanus). However, I'm also forbidden to use any constants that are not 0x0 and 0xff.

I'm mostly confused on the logic here. Any ideas?

EDIT: I forgot to mention conditional statement are also forbidden. So no ifs, elses, loops etc.

Upvotes: 1

Views: 2085

Answers (3)

Alain Merigot
Alain Merigot

Reputation: 11537

Solution is based on the fact that x^(x<<1) will have its 16 MSB at zero iff the 17 MSB of x are all equal and x can be coded on 16 bits.

Hence

return (x^(x<<1))&(0xffff0000)==0;

solves the problem.

For readability, operations are split in several instructions and to reduce the number of used operators the final test is reversed (it does not seem to be forbidden).

int canNOTbemappedto16bits(int x) {
   int one = !0x0;  // 1 op
   int ffff = (unsigned short) ~0x0;//1 op
   int ffff0000 = (unsigned int) ~0x0 ^ ffff; // 2ops
   return   (x^(x<<one))&ffff0000 ; // 3ops
}

7 ops!

Upvotes: 0

deamentiaemundi
deamentiaemundi

Reputation: 5525

For readability set invuint = ~0u and invushort = ~((short)0u), than we can do invuint - invushort which is either 0 or not. 0 in standard C is equal to false, so you can see with a simple !(invuint - invushort) if an unsigned int fits into an unsigned short.

But that is most likely not what you are asked to do, it would be a bit too easy. If you need to know if the content of an unsigned int fits into an unsigned short it gets a bit more complicated.

We can reuse the incushort = ~((short)0u) here as a mask.

With an_uint = 0; an_uint = incushort we set the lowest bits of an_uint to ones so we have 0x0000ffff. Reversing that with ~an_uint gets you 0xXXXX0000 where the X stand for an unknown number of ones. So if sizeof(unsigned int) == sizeof(unsigned short) we get a 0 but we could have gotten that simpler, see above.

If we use mask = 0xXXXX0000 as a mask to get all of the bits that are larger than an unsigned short with uint_with_unknown_content & mask we get a 0 if uint_with_unknown_content fits into an unsigned short.

Upvotes: 0

0___________
0___________

Reputation: 67546

that is your sollution

 (unsigned)~0 == 0xffff

or without ==

 !((unsigned)~0 - 0xffff)

 !((unsigned)~0 ^ 0xffff)

or if only 0xff is allowed

!((unsigned)~0 ^ (((0xff << (!!0xff << !!0xff << !!0xff << !!0xff))) | 0xff)))

Upvotes: 1

Related Questions