Prior Page Next Page This Chapter Next Chapter

Representing Numbers with Bits

Placing things in correspondence with the integers is the fundamental way of measuring things in the world, it's called counting. Bits can also provide a method for counting.

Take 3 bits, we know they can represent 8 different equally likely states. If those states are the numbers from zero to seven then we can represent the digits from zero to seven with bits, two possibilities are shown below underneath the column labeled A and B. The middle column shows the 8 possible bit configurations.

Above there are two possible assignments of meaning for the thee bits out of the 40,320 possible ways (that's

ways) one could have assigned a meaning. What is the advantage of method A over method B? Method A is organized so one can figure it out without remembering the bit pattern for each number. If each bit represents the value 1 or 0 and the position of the bit represents a power of two starting from the right (the least significant bit) with 0, then one can compute the value of any bit sequence and get the number in column A.

If one labels the bit columns in the figure by the digits 4, 2, and 1, that is, the first three powers of two, then one can use these column markers to figure out the bit representations. To get the 5 in column A one finds a 1 from the 4-column of bits, with a 0 in the 2-column of bits, and with a 1 in the 1-column; the decimal sum the power-of-two column labels that have a 1 in the bit representation give the decimal number equivalent. gives 5. So 101 is the bit representation of the decimal digit 5. It is just as easy to go the other way 011 must be 0 (the 4s column), 1 (the 2s column), and 1 (1s column) this corresponds to the digit 3.

Using this bit representation of the digits, the one in the A column, possesses a real advantage: one can treat the bits just like numbers and do arithmetic directly on the number bit representation. There exists an add table for bit encoded numbers of this form, this table is just like the decimal add table only it is a bit shorter and easier to remember. The add table for bit encoded numbers is:

The (1)0 at the intersection of 1+1 means the answer is 0 but carry 1 into the next column to the left. Using this addition table one can build the whole table of three bits. Let's do one example.

Any integer can be represented in bits using subsequent powers of two to label additional columns to the left.

In the same way we can do addition of bits we can do multiplication. Here is the multiplication table for the bit representation of decimal digits.

Here is a small example to show how bit encoded multiplication works. It is just like decimal multiplication, in that you multiply serially by successive digits from the right, writing down the partial answers each shifted one to the left, then you add the results to get the answer. The only difference is you do use the bit multiplication and addition tables.

This particular encoding of numbers by bits is so important that it is given a name. It is called binary, and binary arithmetic conceptually models how the machine does its arithmetic with hardware flip-flops inside the machine. Thus representation A has an overwhelming advantage over representation B.

This idea of correspondence and ordering is far more general than just this particular representation. If a particular method is chosen to order sets of a given kind then there is a canonical order for the sets (that is they can be put in one to one correspondence with the integers). Canonical sets are easy to check for equivalence, generate differences, and unite. By ordering both sets and then performing the operation sequentially one can efficiently create the result.

The representation A of integer numbers to correspond to the bits makes it easy to order and to use.

So far our method of representing number in binary will only allow positive integers. How does one represent negative integers? Many ways have been used, but most machines today use what is called twos-complement arithmetic for integers. Here is how it works. Consider the binary subtraction table!

In the above table if you are trying to compute 0 ~- ~1

the table tells you produce (1)1, this means the answer is 1 and you have to borrow one from the column to the left. Here is an example of bit subtraction.

Now let's be more adventurous; let's subtract 1 from zero. This should give us -1 the first negative integer.

The subtraction is still not done because there is still one to borrow. This is represented by the (1) at the beginning of the number. The answer seems to be getting larger at every step of the subtraction. This is not headed in the direction of negative numbers at all. Have we made a mistake?

The answer is no. If you keep following the rules what you discover is that the answer keeps getting larger without bound, the limit of the answer is the mathematicians infinity. This requires an ever increasing number of bits to store the number. Not a useful result for a computing machine that has only finite sized numbers and a limited space to store a number. So what really happens is that when the machine runs to the end of the bits it is using to represent a number it just looses the carry. The first bit in the number, the one on the left is considered the sign-bit to show the number is positive or negative. In the sign position a zero bit represents a positive number, a one bit represents a negative number. The positive value, pv, of a bit representation of a twos-complement negative number, v, is pv~ =~ 0~ -~ v with the carry from the sign position forgotten. So the correct way to interpret, 11111111, is as 00000000~-~11111111 .

Another way to get the positive value of a twos-complement negative number is to complement every bit, by changing zeros to ones and ones to zeros, and then add one.

These somewhat odd twos-complement negative numbers act properly if you add and multiply with them just as if they were positive. They also give you the right signed number as an answer. For hardware designers this is attractive because nothing special has to be added to the hardware to do arithmetic with signed numbers.

The only problem with the representation is that the sign bit is turned over, a 1 in the sign bit represents something less than a 0 in the sign bit. This means that comparison of signed integer numbers must be done with hardware which recognizes the special status of the sign bit.

One can, of course, change the interpretation of what the bits in a number mean. For example if every integer represents the number multiplied by five and this is done consistently then the hardware arithmetic operations can continue to be used. Since arithmetic is isomorphic to linear transformations. If you change the interpretation of numbers some way that is not isomorphic to the hardware interpretation then you must write your own arithmetic routines to do the operations you want. For example a non isomorphic representation of numbers would occur if you decided to represent numbers as rationals with separate numerator and denominator for each number.

The meaning of the machine number representation is built into the Pascal run-time library, if you want some other interpretation then you just need to write your programs to make what you want happen. When the Pascal run-time library is told to print an integer, it interprets the numeric bits as twos-complement numbers and produces the proper decimal characters with the right sign. If you wanted five times that value you will have to either write your own print routine or adjust the value properly to match the expectations of the Pascal run-time library.

The finite nature of the machine limits the number of bits that can represent a number. This is the choice of the hardware designer. Computing machines have been built that have 8, 12, 24, 36, 48, or 64 bit integers. Commonly modern computers usually give you both 16 and 32 bit integers; 16 bit integers are called short integers, and 32 bit ones are called long integers. (In Macintosh Think Pascal these are called integer and longint.) A sixteen bit twos-complement integer holds 15 bits of magnitude and 1 bit of sign. The smallest number which can be represented in sixteen bits is -2 sup 15 , or -32,768, and the largest is 2¹⁵ - 1, or 32,767. Notice the asymmetry of the range, this is caused by the top bit being both sign and value for negative numbers in twos-complement notation.

Because of the finite number of bits used to represent a number, arithmetic will not work right if you go over the size available in the machine. For example if you add one to the largest positive number the machine can hold it will suddenly become the smallest negative number. In a 16-bit twos-complement machine, adding 1 to 32,767 gives -32,768. Not exactly what you might expect if you were thinking about mathematical abstractions. This sudden break with mathematical conventions is called a machine addition overflow. Some programming languages catch overflow and give an error message, most don't give an error and just go on with the wrong number.

Other common ways to represent negative numbers are called sign-magnitude, ones-complement, and excess-n.

With sign-magnitude negative numbers are represented by a bit that gives the sign, followed by a positive number. For sign-magnitude the machine must recognize and process the sign bit when doing arithmetic and comparisons.

Ones-complement negative numbers are represented by the positive number with all the zero bits turned to one and all the one bits turned to zero. Again the first bit is the sign bit; special hardware is needed to make ones-complement work for arithmetic and comparisons, as well.

For excess-n numbers, some number n is added to each number. For example with excess-128 numbers, 128 is added to each number. The positive number after the addition is represented in binary. So in excess-128, the number -125 is represented as -125 + 128 or 3. The number 12 is 12 + 128 or 140. We will meet excess numbers again when we explore ways to represent real numbers. No special methods are needed for excess-n numbers, but positive numbers have a top bit of one rather than zero, and some people find this disturbing.

In the table different values are shown with their representation in a variety of different notations for negative numbers. The number size, or word size, used here is 8 bits, 1-bit of sign and 7-bits of number.

Note that in mathematics there is no such thing as -0, yet it occurs as a distinct value in two of these representations. When sign-magnitude numbers were commonly used, in the 1960s and 70s, it proved a convenient way to represent `missing values' that when they are used in a computation act like zero. It is less common today because most machines use twos-complement negative numbers and so there is no representation for -0. You might think a good twos-complement alternative for the missing value might be the full word equivalent of -128, but this is seldom used because just about anything you do with it causes arithmetic overflow.

This is important: a computer does not really do arithmetic at all. Think about it, a computer only follows some simple rules that create bit patterns that bear a one to one correspondence with arithmetic across some small range of values. Outside that range machine arithmetic and conceptual arithmetic are vastly different. The conventions the machine follows are man made and finite; they are subject to the engineering constraints of the computer hardware. If you want to do arithmetic in a program, you must know the limits of its machine arithmetic, and then you must make sure you stay within them, otherwise your answers will not be what you expect.