4.3 INTEGERS

In the case of integer numbers, the addition and subtraction algorithms depend on the particular representation. Three nonredundant representation methods are considered in what follows: B's complement, sign-magnitude, and excess-E (Chapter 3).

4.3.1 B's Complement Addition

Given two n-digit B's complement integers x and y, and an initial carry cin equal to 0 or 1, then z = x + y + cin is an (n + 1)-digit B's complement integer. Assume that x and y are represented with n+1 digits. Then the natural numbers associated with x, y, and z are R(x) = x mod Bn+1, R(y) = y mod Bn+1, and R(z) = z mod Bn+1 (Definition 3.4), so that

image

Thus a straightforward addition algorithm consists in representing x and y with n+1 digits and adding the corresponding natural numbers, as well as the initial carry, modulo Bn+1 (that means without taking into account the output carry). In order to represent x and y with one additional digit, Comment 3.2 is taken into account. As before, the procedure natural_addition computes the sum of two natural numbers.

Algorithm 4.18 B's Complement Addition

if x(n-1)<B/2 then x(n):=0; else x(n):=B-1; end if;
if y(n-1)<B/2 then y(n):=0; else y(n):=B-1; end if;
natural_addition(n+1, c_in, x, y, not_used, z);

Example 4.1 Assume that B = 10, n = 4, cin = 0, x = −2345, and y = −3674.. Both x and y are negative so that they are represented by R(x) = − 2345 + 10

Get Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.