Page 272 - Discrete Mathematics and Its Applications

4.2 Integer Representations and Algorithms 251

so that c 2 = 1 and s 2 = 0. Finally, because
11 1
a 3 + b 3 + c 2 = 1 + 1 + 1 = 1 · 2 + 1,
1110
+1011

1 1001 follows that c 3 = 1 and s 3 = 1.This means that s 4 = c 3 = 1.Therefore, s = a + b = (1 1001) 2 .
This addition is displayed in Figure 1, where carries are shown in blue. ▲
FIGURE 1
Adding (1110) 2 The algorithm for addition can be described using pseudocode as follows.
and (1011) 2 .

ALGORITHM 2 Addition of Integers.
procedure add(a, b: positive integers)
{the binary expansions of a and b are (a n−1 a n−2 ...a 1 a 0 ) 2
and (b n−1 b n−2 ...b 1 b 0 ) 2 , respectively}
c := 0
for j := 0 to n − 1
d := (a j + b j + c)/2
s j := a j + b j + c − 2d
c := d
s n := c
return (s 0 ,s 1 ,...,s n ) {the binary expansion of the sum is (s n s n−1 ...s 0 ) 2 }

Next, the number of additions of bits used by Algorithm 2 will be analyzed.

EXAMPLE 9 How many additions of bits are required to use Algorithm 2 to add two integers with n bits (or
less) in their binary representations?

Solution: Two integers are added by successively adding pairs of bits and, when it occurs, a carry.
Adding each pair of bits and the carry requires two additions of bits. Thus, the total number of
additions of bits used is less than twice the number of bits in the expansion. Hence, the number
of additions of bits used by Algorithm 2 to add two n-bit integers is O(n). ▲

MULTIPLICATION ALGORITHM Next, consider the multiplication of two n-bit integers a
and b. The conventional algorithm (used when multiplying with pencil and paper) works as
follows. Using the distributive law, we see that

0
1
ab = a(b 0 2 + b 1 2 + ··· + b n−1 2 n−1 )
1
0
= a(b 0 2 ) + a(b 1 2 ) + ··· + a(b n−1 2 n−1 ).
We can compute ab using this equation. We first note that ab j = a if b j = 1 and ab j = 0if
b j = 0. Each time we multiply a term by 2, we shift its binary expansion one place to the left
j
and add a zero at the tail end of the expansion. Consequently, we can obtain (ab j )2 by shifting
the binary expansion of ab j j places to the left, adding j zero bits at the tail end of this binary
j
expansion. Finally, we obtain ab by adding the n integers ab j 2 ,j = 0, 1, 2,...,n − 1.
Algorithm 3 displays this procedure for multiplication.