3 ms·

My current favorite interview question is write itoa in C, and actually this comes up in almost every solution. (generally, people want to set some flag for neg

• m0nastic 15y ago
  Neat, K&R's itoa implementation example (page 64, in case anyone is curious) specifically calls out that it doesn't handle INT_MIN, and explaining why and fixing it is one of the exercises.
• psykotic 15y ago
  It's interesting to see the range of proposed solutions to this issue. Here's a few from memory. Koenig's C Traps and Pitfalls does the opposite of what you'd expect by making the recursion work with negative integers and reducing the positive case to that. That in turn exposes the issue of C having an implementation-dependent meaning for x / y and x % y when x is negative. But he works around that in the usual way. This solution doesn't assume 2's complement, but it does assume that the negative range of integers is at least as large as the positive range. This works with 2's complement, 1's complement and sign-magnitude, so it's pretty damn bulletproof. It wouldn't work with a hypothetical representation where the positive range was larger than the negative range. Making this fully portable to any ANSI C conforming system is possible (work with either positive or negative integers depending on which has the larger range) but it involves the chicken-and-egg problem of portably determining whether INT_MIN or INT_MAX is numerically largest. Here's one way to do that (untested): div_t quotrem(int numer, int denom) { div_t d; d.quot = numer / denom; d.rem = numer % denom; if (d.rem < 0) { d.rem += denom; d.quot--; } return d; } int abscmp(int x, int y) { if (x == 0 && y == 0) return 0; if (x == 0) return y > 0 ? -1 : +1; if (y == 0) return x < 0 ? -1 : +1; div_t dx = quotrem(x, 2), dy = quotrem(y, 2); int r = abscmp(dx.quot, dy.quot); return r == 0 ? dx.rem - dy.rem : r; } That is purely an academic exercise in theoretical portability wanking, of course. Hanson and Fraser's A Retargetable C Compiler does the inner loop the usual way with positive integers but using unsigned arithmetic. They specifically handle the INT_MIN case with code along these lines: if (i >= 0) u = (unsigned) i; else if (i == INT_MIN) u = 1 + (unsigned) INT_MAX; else u = (unsigned) -i; Thus it assumes a 2's complement representation. Here's another solution I just thought of that should be portable to any ANSI C conformant platform. Write the usual divide-by-base-until-zero loop but use this function to determine the right digit to put into the string buffer: int digit(int x, int base) { div_t d = quotrem(x, base); return x >= 0 ? d.rem : base - d.rem; } This works for either positive or negative integers. That's the key. You don't need to normalize anything to either positive or negative values in your inner loop.
  • caf 15y ago
    Hanson and Fraser's example can be improved: if (i >= 0) u = (unsigned)i; else u = -(unsigned)i; This doesn't assume 2's complement - it works based on C's defined rules for wrapping arithmetic in unsigned types (out-of-range results are brought into range by repeatedly adding or subtracting UINT_MAX + 1).
    • psykotic 15y ago
      Yeah, I had a conversation a few weeks ago with a coworker where he misremembered that as being what was in the lcc book. I actually posted about this here (including an excerpt from Steele and Harbinson) ten days ago: http://news.ycombinator.com/item?id=2935583 http://news.ycombinator.com/item?id=2935583. I notice my description there was slightly bungled since I forgot that after the cast for negative integers you of course have to do an unsigned negation (otherwise -1 would be mapped to UINT_MAX, for example).
• timsally 15y ago
  How often are you interviewing C programmers for project work? Genuinely curious.