Chapter 3 - Control Flow 4

Answer to Exercise 3-4, page 64
Solution by Paul Griffiths - 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).

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.

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;
    }
}