The Elements of Computing Systems: Building a Modern Computer from First Principles by Noam Nisan, Shimon Schocken Read Free Book Online

significant bits (LSB) of the two binary numbers. Next, we add the resulting carry bit (which is either 0 or 1) to the sum of the next pair of bits up the significance ladder. We continue the process until the two most significant bits (MSB) are added. If the last bit-wise addition generates a carry of 1, we can report overflow; otherwise, the addition completes successfully:
    We see that computer hardware for binary addition of two n -bit numbers can be built from logic gates designed to calculate the sum of three bits (pair of bits plus carry bit). The transfer of the resulting carry bit forward to the addition of the next significant pair of bits can be easily accomplished by proper wiring of the 3-bit adder gates.
     
    Signed Binary Numbers A binary system with n digits can generate a set of 2 n different bit patterns. If we have to represent signed numbers in binary code, a natural solution is to split this space into two equal subsets. One subset of codes is assigned to represent positive numbers, and the other negative numbers. Ideally, the coding scheme should be chosen in such a way that the introduction of signed numbers would complicate the hardware implementation as little as possible.
    This challenge has led to the development of several coding schemes for representing signed numbers in binary code. The method used today by almost all computers is called the 2’s complement method, also known as radix complement. In a binary system with n digits, the 2’s complement of the number x is defined as follows:
    For example, in a 5-bit binary system, the 2’s complement representation of–2 or “minus(00010) two ” is 2 5 –(00010) two = (32) ten –(2) ten = (30) ten = (11110) two . To check the calculation, the reader can verify that (00010) two + (11110) two = (00000) two . Note that in the latter computation, the sum is actually (100000) two , but since we are dealing with a 5-bit binary system, the left-most sixth bit is simply ignored. As a rule, when the 2’s complement method is applied to n -bit numbers, x + (– x ) always sums up to 2 n (i.e., 1 followed by n 0’s)—a property that gives the method its name. Figure 2.1 illustrates a 4-bit binary system with the 2’s complement method.
    An inspection of figure 2.1 suggests that an n -bit binary system with 2’s complement representation has the following properties:

    Figure 2.1 2’s complement representation of signed numbers in a 4-bit binary system.
     
    ■ The system can code a total of 2 n signed numbers, of which the maximal and minimal numbers are 2 n –1 –1 and–2 n –1 , respectively.
    ■ The codes of all positive numbers begin with a 0.
    ■ The codes of all negative numbers begin with a 1.
    ■ To obtain the code of– x from the code of x, leave all the trailing (least significant) 0’s and the first least significant 1 intact, then flip all the remaining bits (convert 0’s to 1’s and vice versa). An equivalent shortcut, which is easier to implement in hardware, is to flip all the bits of x and add 1 to the result.
     
    A particularly attractive feature of this representation is that addition of any two signed numbers in 2’s complement is exactly the same as addition of positive numbers. Consider, for example, the addition operation (–2) + (–3). Using 2’s complement (in a 4-bit representation), we have to add, in binary, (1110) two + (1101) two . Without paying any attention to which numbers (positive or negative) these codes represent, bit-wise addition will yield 1011 (after throwing away the overflow bit). As figure 2.1 shows, this indeed is the 2’s complement representation of -5.
    In short, we see that the 2’s complement method facilitates the addition of any two signed numbers without requiring special hardware beyond that needed for simple bit-wise addition. What about subtraction? Recall that in the 2’s complement method, the arithmetic negation of a signed number x , that is, computing– x , is