Wurster Hall, and multiplying 2's complement numbers

[nibot]

Nick gave me a short tour of Wurster Hall. What a cool place! Must explore further...

Brandon sent me the following algorithm to multiply two's complement numbers. I needed to invoke Kenny to help decipher it!

1. Use regular unsigned multiplication to compute A*B → H:L.
2. If A<0, set H ← (H - B).
3. If B<0, set H ← (H - A).

Comments

[forvrkate.livejournal.com]

Two's complement numbers? Whassat?

[nibot.livejournal.com]

It's how computers represent numbers that may be negative: a negative value X is represented as ~(-X-1), where ~ indicates bitwise complement. Suppose we have four-bit numbers. Then 5 would be represented as 0101 and -5 would be represented as ~(0101 - 1) = ~(0100) = 1011. Then arithmetic "just works": 1011 + 0101 = 0000 as expected (the 1 that is carried "falls off" the left).

The posting above has a nonstandard way of doing two's complement multiplication. Let A = 0001, B = 1111 (-1). First we compute A*B in the 'unsigned' sense: A*B = 0000 1111. Then, since B<0, we subtract A from the upper four bits of A*B to get (0000 - 0001) 1111 = 1111 1111, which is -1 represented with 8 bits.