2s complement and negation


While developing a multiprecision math library I ran into the following conundron. See if you can figure out what's wrong with the code below:

    int a, b;

    /* Some code which initializes "a" here ... */

    if (a < 0) {
        a = -a;
    }
    b = sqrt (a);

For nearly every possible value of "a" there is no problem with this code. "b" will be some kind of approximation to the square root of "a". The problem, it turns out is with the very nature of 2s complement itself. While mathematically we all know that negating a negative number will yield a positive number, it turns out that that is not the case for 2s complement representations. The trouble is with the value 0x80000000 (in 32 bits) or just MIN_INT. In 2s complement, negation is defined as complementing and adding 1. Here we find that negating this value just returns itself. Furthermore, this cannot be fixed by simply mapping this negation to some other value since we expect that -(-(x)) to be equal to x.

In this case, the problem is easy to fix:

    int a, b;

    /* Some code which initializes "a" here ... */

    if (a < 0) {
        b = sqrt (-(double)a)
    } else {
        b = sqrt (a);
    }

However, the generic problem exists for 2s complement. For example, in creating a 2s complement based multiprecision integer math library (as an array of words), one has to be careful about the rule that the "top bit" of the number represents the sign of the number. On a 32bit system, negating 0x80000000, for example, should lead to 0x0000000080000000.

Of course, while 1s complement doesn't have this problem -- it has others (like the double representation of 0).


Home Programming Cases Mail me!