Number SystemsThe Decimal Number SystemThe Binary Number SystemBinary ArithmeticDecimal To Binary ConversionRemainder MethodSubtraction MethodNegative NumbersHexadecimal Number SystemOctal Number SystemCSci 132 Practical UNIX and Programming Fall 2006 Prof. Stewart Weiss Lecture Notes: Binary Number System 1 Number Systems Almost all modern computers are digital computers, which means that they can recognize only two1 distinct electronic states of electrical charge. For simplicity, these states are identified as 0 and 1, or equivalently, false and true, or off and on. Since 0 and 1 are the most compact means of representing two states, data is represented as sequences of 0's and 1's. Sequences of 0's and 1's are binary numerals, or in common jargon, binary numbers. To understand binary numbers, or for that matter, any other number systems, you should first revisit the one you have been used to your whole life, namely, the decimal number system. If you truly understand decimal numbers, then the rest is a piece of cake. 1.1 The Decimal Number System Throughout the world, the main system of mathematical notation today is the decimal number system, which is also called the base-10 system. The term "base" refers to the number of distinct symbols that can be found in the numerals. The word "decimal" comes from the Latin word for "ten". In the decimal system, there are ten symbols, called digits, which are universally written 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Numerals are sequences of one or more digits. Numerals represent quantities, called numbers. You probably learned when you were young that the numeral "5" denotes a quantity consisting of five things, and that the numeral "9" represents the concept of nine things. I am sure your primary school teachers drilled these things into your brain until you could no longer separate the idea of nine things from a picture of the digit 9. This was useful then, but it is a hindrance to you now. If you speak more than one language, you are one step ahead, because you know that the quantity 9 is verbally representable in language in many ways. At some point you learned how to find the values of larger numerals, such as 7,154 or 83,762. The two digit number "10" means "ten" things. We use the word "value" to mean the actual quantity that a numeral represents. The value of "9" is nine things, and the value of "23" is twenty-three things. The concept of placeholders is used to evaluate numerals. Pick an arbitrary five-digit number such as 83,762. You know that the value of this number is (8 × 10,000) + (3 × 1,000) + (7 × 100) + (6 × 10) + (2 × 1) In other words, in the base-10 number system, the digits occupy specific positions in the number. Most people were also taught that the zero, "0", is an indispensable part of this system because without it the system could not represent all possible numbers. This is a false statement though; we do not need that zero. However, it is very convenient because it makes this place-value system easier. The fact that the zero exists makes it easy to represent the quantity six hundred four as the numeral 604: (6 × 100) + (0 × 10) + (4 × 1) 1 This is not entirely accurate. The term "digital" does not imply that there are only two distinguishable states. It implies that there is a finite number of such states, but since almost all modern computers are based on two-state logic, the term "digital" has come to take on this meaning in usage. 1CSci 132 Practical UNIX and Programming Fall 2006 Prof. Stewart Weiss Lecture Notes: Binary Number System because we can use the "0" to "hold" the tens place so that the "6" stays put in the hundreds place. At some point you learned about powers, or exponents, such as the "3" in 103, which you learned is the number of times by which 10 is multiplied by itself, i.e., 103 = 10 × 10 × 10. You also were taught that 1 is really 100, and 10 is 101, and 100 is 102, and so on. Thus, 83,762 could also be written as (8 × 104) + (3 × 103) + (7 × 102) + (6 × 101) + (2 × 100) These exponents make the representation shorter, and they also make the concepts more concise. Each position in a decimal numeral can now be thought of as representing the amount by which to multiply a specific power of ten to form the amount contributed by that placeholder in the numeral's value. To generalize this idea, think of a five-digit numeral more abstractly by writing it as d4d3d2d1d0, in which d4 stands for the leftmost digit (e.g., 8 in this case), d3 is the one after that (e.g., 3 in this case), d2 is the one after that (e.g., 7 in this case), and so on. Notice that there are five digits, but that their subscripts start at 0 and stop at 4: d0 is the ones' place, d1 is the tens' place, d2, the hundreds' place, d3, thousands', and finally d4 ten-thousands' . Since 1 = 100 and 10 = 101 and so on, the value of the numeral d4d3d2d1d0 is (d4× 104) + (d3× 103) + (d2 × 102) + (d1 × 101) + (d0 × 100) In other words, the subscript matches the power of ten by which the digit is multiplied. The usual way to visualize this is by thinking of the positions in a number with N digits is as follows: 10N-1 ...104 103 102 101 100 dN-1...d4d3d2d1d01.2 The Binary Number System We carry these same ideas into the a number system with just two digits. Everything works in exactly the same way. Suppose we only have two digits, 0 and 1. The digits 0 and 1 have the same value as in base 10, namely 0 represents zero things and 1, one thing. How can we write all possible numbers with just two digits? We can use the same principle as we used with base 10, except we will replace base 10 by base 2. In other words, a binary numeral is a sequence of binary digits, called bits. Each bit position is multiplied by a power of 2. Because these are called bits and not digits, I will use the letters b1, b2, and so on to stand for bits. The binary numeral 101, for example, represents the quantity that we write as 5 in decimal, because 101 stands for (1 × 22) + (0 × 21) + (1 × 20) = 22 + 0 + 20 = 4 + 0 + 1 = 5 More generally, to evaluate a binary numeral, you need to write out the powers of two the same was we wrote powers of ten before. The N-bit binary numeral bN-1 ... b4b3b2b1b0 should be visualized by the following table: 2CSci 132 Practical UNIX and Programming Fall 2006 Prof. Stewart Weiss Lecture Notes: Binary Number System 2N-1 ...24 23 22 21 20 bN-1...b4b3b2b1b0If you do