Section 1.6 Summary
In this chapter, we covered the basics of computer arithmetic for integers. We have discussed two interpretation functions that assign bit strings natural numbers and integers. One crucial observation is that bit strings are not per se signed or unsigned but the algorithms we employ on them have to be sound with respect to the one or the other interpretation.
We have introduced a simple addition algorithm that uses elementary boolean functions (and, or, xor) and can easily implemented in hardware. Furthermore, we have seen how subtraction can easily implemented based on addition by complementing the right operand and setting the carry into the least position to 1.
One crucial limitation in computers is that they intrinsically operate on word-size data and we have seen that it is not always possible to accurately represent the result of an addition because adding to \(n\)-bit numbers may require \(n+1\) bits for the result. We have discussed under which circumstances the least significant \(n\) bits of the addition result are exact, i.e. no overflow occured. For unsigned addition and subtraction the carry out of the last position gives an indication for an overflow. For signed addition and subtraction, the xor of the carries into and out of the last position detects an overflow.
Finally, we have briefly presented sign- and zero-extension of bit strings to convert bit strings into longer bit strings while maintaining their signed/unsigned interpretations and we have briefly looked into shifts which can be used to implement multiplication and division by powers of two.
Basic knowledge about computer arithmetic is important, because signed and unsigned numbers pop up in the type systems of many statically-typed imperative programming languages such as C, Java, and so on.
