CS311 Lecture: Representing Information in Binary Last revised 9/8/11Objectives:1.To review binary representation for unsigned integers2.To introduce octal and hexadecimal shorthands3.To review binary representation for characters4.To introduce binary representations for signed integers5.To introduce the IEEE 754 representation floating point representation6.To discuss the basic process of doing floating point arithmetic7.To review/introduce binary representations for sounds, graphics, moviesMaterials:1.Dr. Java2.RGB Demo AppletI.IntroductionA.One of the key suggestions in Von Neumann's landmark paper was that computer systems should be based on the binary system, using just the two bit values 0 and 1 to encode information.1.This is consistent with the nature of the physical devices used to construct computer systems, and has contributed to the high reliability we associate with digital systems.2.Although Von Neumann was thinking just in terms of representing integers in binary, we have since learned to represent many other kinds of information this way, including text, sounds, and graphics.3.To this day - over 6 decades later, and through several changes in fundamental technology - this idea still dominates the field of computing.1B.At the outset, we should note that there is a crucial distinction between a NUMBER (an abstraction) and a REPRESENTATION of a number (a symbol). 1.For example, the number we call four can be represented by the following symbols:FOUR QUATUOR 4 IV |||| 113 1002 etc.2.On the other hand, the symbol 100 could stand for 4 (as above) or for one hundred (decimal system) or for 9 (trinary system) or for any one of an infinite variety of possible values.C.Most often, we symbolize numbers by a symbol based on a positional notation system. The development of positional notation was a crucial advance in the development of modern mathematics. In a positional system, we have a base or radix (such as 2 for binary, 3 for trinary, or ten for decimal). We make use of a limited set of symbols fo representing values 0 .. radix - 1.1.For example, in binary, we use two symbols (0,1); in octal (base 8) we use 8 (0,1,2,3,4,5,6,7); in hexadecimal (base 16) we use 16 symbols (0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F) etc. 2.When there is any possibility of confusion, we denote the radix of a numerical symbol by a subscript (written using decimal notation!) - eg: 901016D.Further, in a positional system the value of a symbol depends on where it is written. The rightmost symbol (digit) has the value (symbol_value)*1; the one next to it has value (symbol_value) * radix etc. Thus, the radix-2 (binary) number 01000001 is equivalent to the decimal number:0*128 + 1*64 + 0*32 + 0*16 + 0*8 + 0*4 + 0*2 + 1*1 = 6510 2E.In this and subsequent lectures, we will consider how various kinds of information can be represented in binary. Today, we limit ourselves to unsigned integers.II.Review of Internal Encoding for Unsigned Binary IntegersA.The normal way of encoding unsigned binary integers is to use a straightforward place-value system, in which the bits are assigned weights 20, 21, 22 etc. Thus, for example, the binary integer 1011 would be interpreted as1 * 20 = ! 1+ 1 * 21 = ! 2+ 0 * 22 = ! 0+ 1 * 23 = ! 8! ! ---!!11B.Note that with n bits we can store values in the range 0 .. 2(n-1)C.Conversion between decimal and binary1.To go from binary to decimal, we use the basic approach outlined above: multiply the rightmost bit by 20, the next bit by 21, the next bit by 22 etc. Add the products. (It helps if you memorize the powers of 2)Example: convert 10011101 to decimal (157)Exercise: 10101010 (170)2.To go from decimal to binary, we can use successive division: Divide the decimal number by 2. The remainder is the rightmost bit of the binary equivalent. Divide the quotient by 2. The new remainder is the second rightmost bit. Divide the new quotient by 2. The new remainder is third rightmost bit ... Continue until the quotient is 0.3Example: convert 238 to binary238 / 2 = 119 rem 0 <- least significant bit119 / 2 = 59 rem 159 / 2 = 29 rem 129 / 2 = 14 rem 114 / 2 = 7 rem 07 / 2 = 3 rem 13 / 2 = 1 rem 11 / 2 = 0 rem 1 <- most significant 238 => 11101110Exercise: 252 (11111100)D.Adding binary numbers: As a child, you learned how to do addition based on an addition table like the following:! ! 0! 1! 2! 3! 4! 5! 6! 7! 8! 90! 0! 1! 2! 3! 4! 5! 6! 7! 8! 91! 1! 2! 3! 4! 5! 6! 7! 8! 9! 0 + carry2! 2! 3! 4! 5! 6! 7! 8! 9! 0+ca! 1 + carry3! 3! 4! 5! 6! 7! 8! 9! 0+ca! 1+ca! 2 + carryetc.For binary, the table is much simpler: ! 0 10! 0! 1Example:! 01011010 !Check:! 90! ! + 01101100 ! + 108!! ! 11000110! ! ! ! 198Exercise: ! 00111001!!+ 01011010! ! 10010011E.One issue to be sensitive to in addition and other operations is OVERFLOW. Computer hardware typically uses a fixed number of bits to represent integers, so an erroneous result will be produced if the correct sum is too big for the representation.4Example: assume a certain machine uses 8 bits for integers. Consider the following problem:! ! ! 11001000! ! ! ! 200! ! ! + 11001000! ! ! ! + 200! ! ! 10010000! ! ! ! 144 !!The error arises because 8 bits cannot represent the correct sum. (Here, we detect overflow by the fact that there was carry out of the most significant bit position.)F.Other arithmetic operations can be done on binary numbers in a manner analogous to the decimal operations, but using the binary tables - though other methods are actually used in practice, as we shall see.III.Octal and Hexadecimal ShorthandsA.By now you are probably tired of writing 1's and 0's all the time. Writing numbers in binary is tiring, and it is very easy to make mistakes. On the other hand, converting numbers between decimal and binary is complex, so at the hardware level we like to work with the binary form.B.Consider, for a moment, the radix-8 (octal) number system. Since there are 8 different symbols in this system, octal numbers are about as easy to write as decimal numbers. Further, because 8 is a power of 2, it is very easy to convert between binary and octal notations.1.Binary to octal: group binary number into groups of three bits, starting from the right. Each group will now represent a value in the range 0 .. 7 - i.e. an octal