http://en.wikipedia.org/wiki/Ones'_complement has a discussion. The net result has to be addition in which both positive and negative zero values are taken into account.

In assembly language you wrap the carry-out back and increment if the carry-out has been set. In C it gets messy, but the usual technique is to use extra precision for the addition and catch the carry-out bits there, then add them back in later.

Ok, thank you. Can you explain why 1's complement is required. You only say it kills performance, but give no explanation. Thank you for your blog BTW, I took your advice and implemented the fletcher checksum in order to verify the ROM content of an ASIC.

One's complement addition catches the carry-out bit of the addition and "wraps it around" back into a carry in to the lowest bit position. (That's not the mathematical definition; it's how you implement it on a two's complement computer.) It catches the case where the the highest two bits of a word are changed from 0/0 to 1/1 or the reverse because that change generates the opposite carry-out bit value. Two's complement throws that change away. One's complement wraps that changed carry-out back to the sum, detecting the change.

The performance hit is modest or almost zero if you use a clever algorithm; high if you do it the hard way. The clever algorithms are a post for another day.

What do you mean: "use 1's complement addition"?

ReplyDeleteLike this? a = b + (~c)

No, that won't quite do it.

ReplyDeletehttp://en.wikipedia.org/wiki/Ones'_complement

has a discussion. The net result has to be addition in which both positive and negative zero values are taken into account.

In assembly language you wrap the carry-out back and increment if the carry-out has been set. In C it gets messy, but the usual technique is to use extra precision for the addition and catch the carry-out bits there, then add them back in later.

Ok, thank you. Can you explain why 1's complement is required. You only say it kills performance, but give no explanation. Thank you for your blog BTW, I took your advice and implemented the fletcher checksum in order to verify the ROM content of an ASIC.

ReplyDeleteOne's complement addition catches the carry-out bit of the addition and "wraps it around" back into a carry in to the lowest bit position. (That's not the mathematical definition; it's how you implement it on a two's complement computer.) It catches the case where the the highest two bits of a word are changed from 0/0 to 1/1 or the reverse because that change generates the opposite carry-out bit value. Two's complement throws that change away. One's complement wraps that changed carry-out back to the sum, detecting the change.

ReplyDeleteThe performance hit is modest or almost zero if you use a clever algorithm; high if you do it the hard way. The clever algorithms are a post for another day.