The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 3.04 on page 64
In a two's complement number representation, our version of itoa does not handle the largest negative number, that is, the value of n equal to -(2 to the power (wordsize - 1)) . Explain why not. Modify it to print that value correctly regardless of the machine on which it runs.
Solution by Paul Griffiths
Note: error spotted by Wayne Lubin and fixed.
Wayne Lubin's query involved Paul's discussion of two's complement. The
text has now been corrected (by Paul).
Exercise 3-4 explanation: There are a number of ways of
representing signed integers in binary, for example,
signed-magnitude, excess-M, one's complement and two's
complement. We shall restrict our discussion to the
latter two. In a one's complement number representation,
the binary represenation of a negative number is simply
the binary representation of its positive counterpart,
with the sign of all the bits switched. For instance,
with 8 bit variables:
SIGNED BINARY UNSIGNED
25 00011001 25
-25 11100110 230
127 01111111 127
-127 10000000 128
The implications of this are (amongst others) that there
are two ways of representing zero (all zero bits, and
all one bits), that the maximum range for a signed
8-bit number is -127 to 127, and that negative numbers
are biased by (2^n - 1) (i.e. -I is represented by
(2^n - 1) - (+I). In our example, so:
Bias = 2^8 - 1 = 255 = 11111111
Subtract 25 = 00011001
Equals = 11100110
In a two's complement representation, negative numbers
are biased by 2^n, e.g.:
Bias = 2^8 = 100000000
Subtract 25 = 00011001
Equals = 11100111
In other words, to find the two's complement representation
of a negative number, find the one's complement of it, and
add one. The important thing to notice is that the range
of an 8 bit variable using a two's complement
representation is -128 to 127, as opposed to -127 to 127
using one's complement. Thus, the absolute value of the
largest negative number cannot be represented (i.e. we
cannot represent +128). Since the itoa() function in
Chapter 3 handles negative numbers by reversing the
sign of the number before processing, then adding a
'-' to the string, passing the largest negative number
will result it in being translated to itself:
-128 : 10000000
One's complement: 01111111
Subtract 1 : 10000000
Therefore, because (n /= 10) will be negative, the do-while
loop will run once only, and will place in the string a '-',
followed by a single character, (INT_MIN % 10 + '0'). We can
remedy these two bugs in the following way: 1 - change
'while ((n /= 10) > 0)' to 'while (n /= 10)'. Since any
fractional part is truncated with integer division, n will
eventually equal zero after successive divides by 10, and
'n /= 10' will evaluate to false sooner or later. 2 - change
'n % 10 + '0 to 'abs(n % 10) + '0, to get the correct
character. EX3_4.C shows the revised function, which will
run correctly regardless of the number representation.
/* EX3_4.C ======= Suggested solution to Exercise 3-4 */ #include <stdlib.h> #include <stdio.h> #include <limits.h> void itoa(int n, char s[]); void reverse(char s[]); int main(void) { char buffer[20]; printf("INT_MIN: %d\n", INT_MIN); itoa(INT_MIN, buffer); printf("Buffer : %s\n", buffer); return 0; } void itoa(int n, char s[]) { int i, sign; sign = n; i = 0; do { s[i++] = abs(n % 10) + '0'; } while ( n /= 10 ); if (sign < 0) s[i++] = '-'; s[i] = '\0'; reverse(s); } void reverse(char s[]) { int c, i, j; for ( i = 0, j = strlen(s)-1; i < j; i++, j--) { c = s[i]; s[i] = s[j]; s[j] = c; } }
Suggestion by LingTalfi
I used an unsigned int instead of a signed one
#include <stdio.h> #include <string.h> #include <limits.h> void reverse(char s[]) { int length = strlen(s); int c, i, j; for (i = 0, j = length - 1; i < j; i++, j--) { c = s[i]; s[i] = s[j]; s[j] = c; } } void itoa(int n, char s[]) { int i, sign; unsigned int n2; i = 0; if ((sign = n) < 0) { n2 = -n; } else { n2 = n; } do { s[i++] = (n2 % 10) + '0'; } while ((n2 /= 10) > 0); if (sign < 0) { s[i++] = '-'; } s[i] = '\0'; reverse(s); } main() { char s[128]; itoa(INT_MIN, s); printf("%d is converted to %s.\n", INT_MIN, s); }
Solution by Revc
I use a formula
rem(a, b) = rem(rem(a + c, b) - c, b)
to avoid the overflow in expression
n = -n
.
Here is a brief proof: See Remainder in Wikipedia to get more information. I shall quote the following:
If a and d are integers, with d non-zero, it can be proven that there exist unique integers q and r, such that a = qd + r and 0 ≤ r < |d|. The number q is called the quotient, while r is called the remainder.
Say
a = k1 * b + s1, a + c = k2 * b + s2
,
so
c = s2 - s1 + (k2 - k1) * b
.
According to the assumption,
rem(rem(a + c, b) - c, b) = rem(s2 - c , b)
and
s2 - c = (k1 - k2) * b + s1
,
since quotient and remainder are unique,
thus
rem(s2 - c, b) = s1 = rem(a,b)
.
/* itoa: convert n to characters in s */ void itoa(int n, char s[]) { int i, sign; i = 0; sign = n; if (n < 0) { s[i++] = (((-(n + 1)) % 10) + 1) % 10 + '0'; // add one to negative for avoiding the overflow of -(2^wordsize - 1) n /= 10; n = -n; } else { s[i++] = n % 10 + '0'; n /= 10; } while (n > 0) { s[i++] = n % 10 + '0'; /* get next digit */ n /= 10; } if (sign < 0) s[i++] = '-'; s[i] = '\0'; reverse(s); }
Solution by Codybartfast (category 0)
The original itoa doesn't work because the range of negative numbers is one greater than the range of positive numbers. So instead of converting negative numbers to positive, we can convert positive to negative and use the original method with just a few small changes:
void itoa(int n, char s[]) { int i, sign; if ((sign = n) > 0) n = -n; i = 0; do { s[i++] = '0' - (n % 10); } while ((n /= 10) < 0); if (sign < 0) s[i++] = '-'; s[i] = '\0'; reverse(s); }
This will work with C99 but isn't strictly C89 compliant. With C99 I think we can assume -13/10 is -1 and -13%10 is -3 because division will truncate towards zero. However, C89 also allowed for floor towards negative infinity. In that case -13/10 = -2 with -13%10 = 7 was also valid. Both these satisfy the C89 requirement that "(a/b)*b + a%b = a" (A7.6, page 205). This version checks the behaviour of quotient and then adjusts the result of % if needed:
void itoa89(int n, char s[]) { int i, sign; /* * Test if we're getting floor quotient -2, instead of 'normal' * truncated quotient, -1. If so, % will give positive remainders * for negative dividends and we need to subtract 10 to get 'normal' * negative remainders. */ int adj = ((-13 / 10) == -2) ? 10 : 0; if ((sign = n) > 0) n = -n; i = 0; do { /* adj will ensure we get a negative remainder */ s[i++] = '0' - ((n % 10) - adj); } while ((n /= 10) < 0); if (sign < 0) s[i++] = '-'; s[i] = '\0'; reverse(s); }
Solution by Miguel Degrossoli
/* Exercise 3-4. In a two's complement number representation, out version of * "itoa" does not handle the largest negative number, that is, the value of n * equal to -[2^(wordsize-1)]. Explain why not. Modify it to print that value * correctly, regardless of the machine on which it runs. */ /* Let's think of a signed char, just because it's 8-bits long. The number -128 * in binary is 10000000 (in a two's complement machine). To obtain its positive * counterpart (128) you find the two's complement of 10000000. You'll end-up * finding that the two's complement of 10000000 is exactly 10000000. The * computer cannot tell the difference, and it'll rekon this binary as -128 * still, as MSB = 1. And that's why what tells a negative from a positive * number in a computer is the MSB (1 for negative, 0 for positive). * * The original "itoa" tries to convert the number to positive (i.e., calcs the * two's complement of the number), and that's not possible (that's why INT_MAX * equals |INT_MIN| - 1). */ #include <stdlib.h> #include <stdio.h> #include <limits.h> #define MAXLEN 13 /* maximum string length */ #define COUNT 8 /* how many numbers to convert */ void reverse(char s[]); void itoa(int n, char s[]); int main() { int i, number[] = {15, -15, 6, -6, 1983, -1983, INT_MIN, INT_MAX}; char s[MAXLEN]; for (i == 0; i < COUNT; i++) { itoa(number[i], s); printf("%s\n", s); } exit(0); } void reverse(char s[]) { int i, n; char line[MAXLEN]; for (i = 0; s[i] != '\0' && i < MAXLEN; ++i) ; n = 0; if (i == 0 || s[i] == '\0') line[i] = '\0'; if (i > 0) { for (--i; i >=0; --i) { line[i] = s[n]; n++; } for (i = 0; line[i] != '\0'; i++) s[i] = line[i]; } } void itoa(int n, char s[]) { int i, sign = 1; if (n < 0) sign = (-1); i = 0; do { s[i++] = (n % 10) * sign + '0'; } while ((n /= 10) != 0); if (sign < 0) s[i++] = '-'; s[i] = '\0'; reverse(s); }
Solution by Foowar
/* * Exercise 3-4. * * In as two's complement number representation, our version of * itoa does not handle the largerst negative number, that is,the value of n * equal -(2^(wordsize-1)). Explain why not, Modify it to print that value * correctly, regardless of the machine on which it runs. */ /* * the largest number in two's complement system is 2^(wordsize-1) - 1 * in itoa we converted n from negative to positive by negating it * if n where -(2^(worsize-1)) then -n will be 2^(wordsize-1) which is out * of range. */ #include <limits.h> void reverse(char s[]) { int i, j, tmp; for (j = -1; s[j+1] != '\0'; ++j) ; for (i = 0; i < j; ++i, --j) tmp = s[i], s[i] = s[j], s[j] = tmp; } void itoa(int n, char s[]) { int i, sign; if ((sign = n) < 0) { if (n == INT_MIN) n = -(n+1); /* will add this 1 later */ else n = -n; } i = 0; do { s[i++] = n % 10 + '0'; } while ((n /= 10) > 0); if (sign < 0) { s[i++] = '-'; if (sign == INT_MIN) { /* least significant digit in the largest negative number of any * two's complement type will always be even therefore it will * never be 9 therefor this code is safe */ s[0] += 1; } } s[i] = '\0'; reverse(s); }
