boy - 1 year ago 58

C Question

I'm having a hard time understanding this exercise:

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^(wordsize-1)). Explain why not. Modify it to print that value correctly, regardless of the machine on which it runs.

Here is what the itoa originally looks like:

`void reverse(char s[], int n)`

{

int toSwap;

int end = n-1;

int begin = 0;

while(begin <= end) // Swap the array in place starting from both ends.

{

toSwap = s[begin];

s[begin] = s[end];

s[end] = toSwap;

--end;

++begin;

}

}

// Converts an integer to a character string.

void itoa(int n, char s[])

{

int i, sign;

if ((sign = n) < 0)

n = -n;

i = 0;

do

{

s[i++] = n % 10 + '0';

} while ((n /= 10) > 0);

if (sign < 0)

s[i++] = '-';

s[i] = '\0';

reverse(s, i);

}

I found this answer, but I don't understand the explanation:

http://www.stevenscs.com/programs/KR/$progs/KR-EX3-04.html

Because the absolute value of the largest negative number a word can hold is greater than that of the largest positive number, the statement early in iota that sets positive a negative number corrupts its value.

Are they saying that negative numbers contain more bits because of the sign than a positive number which has no sign? Why would multiplying by -1 affect how the large negative number is stored?

Answer Source

In two's complement representation, the range of values you can represent is `-2`

to ^{n-1}`2`

. Thus, with 8 bits, you can represent values in the range -128 to 127. That's what's meant by the phrase, "the largest negative number a word can hold is greater than that of the largest positive number."^{n-1}-1

Illustrating with just 3 bits to make it clearer:

```
Value Bits
----- ----
0 000
1 001
2 010
3 011
-4 100
-3 101
-2 110
-1 111
```

With 3 bits, there's no way we can represent a *positive* `4`

in two's complement, so `n = -n;`

won't give us the result we expect^{1}. That's why the original `atoi`

implementation above can't deal with `INT_MIN`

.