-6

To answer this question, I read this source code on github and found a problem with the second function.

The challenge is to write C code with various restrictions in terms of operators and language constructions to perform given tasks.

/* 
 * fitsShort - return 1 if x can be represented as a 
 *   16-bit, two's complement integer.
 *   Examples: fitsShort(33000) = 0, fitsShort(-32768) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 1
 */
int fitsShort(int x) {
  /* 
   * after left shift 16 and right shift 16, the left 16 of x is 00000..00 or 111...1111
   * so after shift, if x remains the same, then it means that x can be represent as 16-bit
  */
  return !(((x << 16) >> 16) ^ x); 
}

Left shifting a negative value or a number whose shifted value is beyond the range of int has undefined behavior, right shifting a negative value is implementation defined, so the above solution is incorrect (although it is probably the expected solution).

Is there a solution to this problem that only assumes 32-bit two's complement representation?

chqrlie
  • 131,814
  • 10
  • 121
  • 189
  • 2
    To answer the question which you asked: yes there is a solution to this problem that only assumes 32-bit two's complement representation. P.S. stackoverflow.com is not a web site where you can find someone who can figure out the solution, to some question from some dumb online quiz web site, for you. – Sam Varshavchik Sep 23 '17 at 14:11
  • Perhaps if you mask and then use the other sign-extender, `((x & 0xFFFF) ^ 0x8000) - 0x8000` (then apply the same xor/! logic) – harold Sep 23 '17 at 14:26
  • 1
    A 32-bit 2s complement integer can be represented in 16 bits if its first 17 bits are either all 0s or all 1s. Maybe that helps. – rici Sep 23 '17 at 15:03
  • @harold: integer constants are limited to the range `0` to `255` – chqrlie Sep 23 '17 at 15:29
  • @SamVarshavchik: I am not really interested in the solution, I posted the question to show an example of undefined behavior that many programmers do not know about, possibly including the ones who wrote the challenge. I guess the form is inappropriate. I shall remove this question. – chqrlie Sep 23 '17 at 15:34
  • @chqrlie that's not a real problem, just build the constants in any allowed way. – harold Sep 23 '17 at 15:42
  • @Ron: I agree with you and in fact I do not spend much time at all on such silly sites. I thought the error in the proposed solution deserved some exposure. Given how much time I devote to SO, I gave up on https://projecteuler.net/ which hardly qualifies as a waste of time, but is a humbling experience once one gains access to other people's solutions. – chqrlie Sep 23 '17 at 15:43

1 Answers1

1

The following only assumes 2's complement with at least 16 bits:

int mask = ~0x7FFF;
return !(x&mask)|!(~x&mask);

That uses a 15-bit constant; if that is too big, you can construct it from three smaller constants, but that will push it over the 8-operator limit.

An equivalent way of writing that is:

int m = 0x7FFF;
return !(x&~m)|!~(x|m);

But it's still 7 operations, so int m = (0x7F<<8)|0xFF; would still push it to 9. (I only added it because I don't think I've ever before found a use for !~.)

chqrlie
  • 131,814
  • 10
  • 121
  • 189
rici
  • 234,347
  • 28
  • 237
  • 341
  • I get it from 2 small constants: `int mask = ~0u >> 17;`. The total number of ops is 8, not counting the assignment nor the parentheses. This seems to be a good solution. – chqrlie Sep 23 '17 at 16:20
  • @chqrlie: That works if you know ints are exactly 32 bits; I was trying to avoid that assumption, although I don't know if that's part of the original problem or not. It seems to me that restricting constants to 8 bits when you have a problem which requires 16 bit values is a bit arbitrary, but then it's a puzzle so it's allowed to be completely arbitrary without explanation. – rici Sep 23 '17 at 18:56
  • `0x7FFF` can be computed as `217 * 151`, but multiplication is not allowed. – chqrlie Sep 24 '17 at 07:00