Thursday, March 17, 2005

The Games Complements Play

I recently came across a program, that converted negative values to positive by using the following logic.

if (n < 0) {
n = -n;

It seemed correct and would work almost all the time. Why do we use the word almost. I was reading some parts of Don Knuth's famous Art of Computer Programming and the MMIX architecture

The only number that cannot be represented in signed integers of length k is 2k. The number -2k can be easily represented. What if n = -2k

Taking two's complement (add one to ones' complement of the number) of returns the same value. If you are interested in the reason for difference in the apostrophe placement for the ones' complement and two's complement - see Art of Computer Programming volume 2

Coming back to "n = -n", this code does not work for n = -2k.
The same thing has been mentioned in Andrew Koenig's C Traps and Pitfalls
Post a Comment