2.6 Data Representations     continued...

Shifts such as these can be done in one machine cycle, so they are much faster than multiplication instructions, which usually takes several cycles. Other ``tricks'' are using a right shift to implement integer division by a power of 2, in which the result is an integer and the remainder is ignored (e.g. 15 4 = 3) and taking the modulus or remainder with respect to a power of 2 (see problem 8).

A fundamental relationship about binary patterns is that there are 2 distinct n-digit strings. For example, for n = 8 there are = 256 different strings of 1's and 0's. From this relationship it is easy to see that the largest integer that can be stored in an n-bit word is : the patterns are used to represent the integers in the interval .

An overflow occurs when a system generates a value greater than the largest integer. For example, in a 32-bit system, the largest positive integer is . = 4,294,976,295. If a program tries to add 3,000,000,000 and 2,000,000,000 it will cause an overflow. Right away we can see one source of problems that can arise when moving a program from one system to another: if the word size is smaller on the new system a program that runs successfully on the original system may crash with an overflow error on the new system.

There are two different techniques for representing negative values. One method is to divide the word into two fields, i.e. represent two different types of information within the word. We can use one field to represent the sign of the number, and the other field to represent the value of the number. Since a number can be just positive or negative, we need only one bit for the sign field. Typically the leftmost bit represents the sign, with the convention that a 1 means the number is negative and a 0 means it is positive. This type of representation is known as a sign-magnitude representation, after the names of the two fields.