Programming and Graphics

1.3 Binary system arithmetic 11

+ 1000 1000 1000 1000 1000 1000

- 11 10 100 100 1000 1000

carry: - 1

---- ---- ---- ---- ---- ----

1 1 01 101 0101

The negative “carry” in the third row are added to those in the second row.

To develop rules for multiplication, we observe that, if we multiply a
number by 2 = (10) 2 , the binary digits is shifted to the right by one place. This
is analogous to the rule that, if we multiply a number by 10, the decimal digits
is shifted to the left by one place. For example,

(1101.0) 2 ×(10) 2 = (11010.0) 2 , (27)

and
(10101.001) 2 ×(10) 2 = (101010.010) 2. (28)

If we multiply a number by 0.5=(0.1) 2 , which amounts to dividing by two,
the binary point will be shifted to the left by one place.

More generally, if we multiply a number by 2i= (10...0) 2 , where the
binary string containsizeros, the binary digits will be shifted to the right byi
places. For example,

(1101.000) 2 ×(1000) 2 = (1101000.0) 2. (29)

If the integeriis negative, corresponding to division, the binary digits will be
shifted to the right. For example,

(1101.0) 2 ×(0.01) 2 = (11.01) 2. (30)

The distributive property of multiplication allows us to write for any
numberα:

α×(bkbk− 1 ···b 0 ·b− 1 ···b−l) 2

=bk×α× 2 k+bk− 1 ×α× 2 k−^1 ...+b−l×α× 2 −l. (31)

This expression serves as a basis for implementing multiplication in terms of
binary point shifts and additions. As an example, we compute the product:

(111) 2 ×(101) 2

=1×(111) 2 ×(100) 2 +0×(111) 2 ×(010) 2 +1×(111) 2 ×(001) 2

= (11100) 2 + (111) 2 = (100011) 2. (32)

which confirms the equation 7×5 = 35. The method is implemented in terms
of the intuitive rules of binary digit multiplication:

(0) 2 ×(0) 2 = (0) 2

(0) 2 ×(1) 2 = (0) 2

(1) 2 ×(0) 2 = (0) 2 (33)

(1) 2 ×(1) 2 = (1) 2.