2.2.4-BIT BINARY,HEXADECIMAL AND DECIMAL DIGITS 9 2.2 4-bit Binary,Hexadecimal and Decimal Digits 4-bits of data (a "nibble")can represent or be represented by several different things.It is common for computer programmers to use "hexadecimal"notation (0,1,2...9,A,B...F)as a "shorthand"for (0000,0001,0010...1001,1010,1011...1111).See the following table. However,collection of a certain number of bits has to be given an "interpretation"-one that is sensible to humans.One such assignment (which is completely arbitrary and is decided upon by the computer programmer or designer)is to assign "decimal"numbers to the strings of bits.Such an assignment could look like: Binary Hexadecimal Decimal representation representation assignment 0000 0 0 0001 1 1 0010 2 2 0011 5 3 0100 4 4 0101 5 0110 6 6 0111 7 7 1000 8 8 1001 9 9 1010 A 10 1011 B 11 1100 C 12 1101 D 13 1110 E 14 1111 F 15 We will use this particular representation in doing some simple arithmetic in the exercises and the assignments. 2.3 Binary arithmetic Let us pretend that we have to do some arithmetic (additions and multiplications)using only binary numbers.The numbers 2,3,....9 do not exist!Only 0 and 1 exist.We also assume that the operations of addition and multiplication are commutative (i.e.independent of the order of the mathematical operation). The addition of"fictional"binary numbers-base-2 arithmetic looks like:
2.2. 4-BIT BINARY, HEXADECIMAL AND DECIMAL DIGITS 9 2.2 4-bit Binary, Hexadecimal and Decimal Digits 4-bits of data (a “nibble”) can represent or be represented by several different things. It is common for computer programmers to use “hexadecimal” notation (0, 1, 2...9, A, B...F) as a “shorthand” for (0000, 0001, 0010...1001, 1010, 1011...1111). See the following table. However, collection of a certain number of bits has to be given an “interpretation”—one that is sensible to humans. One such assignment (which is completely arbitrary and is decided upon by the computer programmer or designer) is to assign “decimal” numbers to the strings of bits. Such an assignment couldlook like: Binary Hexadecimal Decimal representation representation assignment 0000 0 0 0001 1 1 0010 2 2 0011 3 3 0100 4 4 0101 5 5 0110 6 6 0111 7 7 1000 8 8 1001 9 9 1010 A 10 1011 B 11 1100 C 12 1101 D 13 1110 E 14 1111 F 15 We will use this particular representation in doing some simple arithmetic in the exercises andthe assignments. 2.3 Binary arithmetic Let us pretend that we have to do some arithmetic (additions and multiplications) using only binary numbers. The numbers 2,3,....9 do not exist! Only 0 and 1 exist. We also assume that the operations of addition and multiplication are commutative (i.e. independent of the order of the mathematical operation). The addition of “fictional” binary numbers–base-2 arithmetic looks like:
10 CHAPTER 2.DATA REPRESENTATIONS 0 +? +0 =? 1 +1 = 10 10 +1 1 +10 11 11 +1 = 1 + 11 心 100 10 +10 10 +10 100 1111+111=111+ 1111 =10110 The multiplication of"fictional"binary numbers-base-2 arithmetic looks like: 0 ×? × 0 =0 1 ×? ×1 =? 10 ×10=10 ×10 :100 10 ×11 =11 ×10 =110 11 ×11 1001 1111×111=111×1111=1101001 The arithmetic procedure is analogous to the more familiar base-10 system(that arose simply because of our anatomy-10 fingers).Additions of columns of numbers,subtraction,mul- tiplication,the procedure of long division,can be accomplished by analogous procedures. There is no limit to how long a "fictional"base-2 number can be and we may have to carry along some extra information with each number-its sign. 2.4 Converting from binary to decimal 2.4.1 Whole numbers Humans are usually quite awful at doing binary arithmetic.If you are doing such a calcula- tion,you can check by converting the binary numbers into their decimal equivalents. In general,to convert a whole binary number to a whole decimal number,consider a binary number of the form: bnbn-1bn-2…b2bbo
10 CHAPTER 2. DATA REPRESENTATIONS 0 +? =? +0 =? 1 + 1 = 10 10 + 1 = 1 + 10 = 11 11 + 1 = 1 + 11 = 100 10 + 10 = 10 + 10 = 100 . . 1111 + 111 = 111 + 1111 = 10110 . . . The multiplication of “fictional” binary numbers–base-2 arithmetic looks like: 0 × ? =? × 0 =0 1 × ? =? × 1 =? 10 × 10 = 10 × 10 = 100 10 × 11 = 11 × 10 = 110 11 × 11 = 1001 . . . 1111 × 111 = 111 × 1111 = 1101001 . . . The arithmetic procedure is analogous to the more familiar base-10 system (that arose simply because of our anatomy—10 fingers). Additions of columns of numbers, subtraction, multiplication, the procedure of long division, can be accomplished by analogous procedures. There is no limit to how long a “fictional” base-2 number can be andwe may have to carry along some extra information with each number—its sign. 2.4 Converting from binary to decimal 2.4.1 Whole numbers Humans are usually quite awful at doing binary arithmetic. If you are doing such a calculation, you can check by converting the binary numbers into their decimal equivalents. In general, to convert a whole binary number to a whole decimal number, consider a binary number of the form: bnbn−1bn−2 ··· b2b1b0
2.5.BINARY INTEGER ARITHMETIC ON COMPUTERS 11 where the bi's are either 0 or 1.We compute a decimal number using the following formula: d10=bn×2”+bn-1×2n-1+bn-2×2m-2.…b2×22+b1×2+bo×20. For example,the result of the two more difficult calculations above can be checked as follows: 101102=1×24+0×23+1×22+1×21+0×2°=24+22+21=1610+410+210=2210 is the result of one of the additions [11112(1510)+1112(710)]above,while 11010012=26+25+23+2°0=6410+3210+810+110=10510 is the result of one of the multiplications [11112(1510)x 1112(710)above.Note that the subscript“2”indicates a binary or base-2 number while the subscript“l0”indicates a decimal number. 2.4.2 Real numbers To convert a real(non-whole)binary number to a real decimal number,consider a binary number of the form: onon-16n-2...626160.6-16-2...6-(m-2)6-(m-1)6-m where the bi's are either 0 or 1 and a period,"."separates the whole part,bi where i>0 from the fractional part,bi where i<0.We compute a real decimal number using the following formula: r10=bn×2+bn-1×2m-1.…b1×22+b0×2°+b-1×2-1+b-2×2-2.+b-m-)×2-m-1)+b-m×2-m. It is not a whole lot different from the decimal numbers you are used to.However,sometimes the formulae can look a little messy. 2.5 Binary integer arithmetic on computers Computers,because of their comprehension of data in binary terms,naturally do their arithmetic using the base-2 representation.The circuitry within a computer is most easily set up this way.However,when it comes to base-2 arithmetic and computers,there is a subtle difference!For practical reasons,computers must deal with integers that are finite in length.16 bits,representing 65,536 separate possibilities,used to be the norm.Today
2.5. BINARY INTEGER ARITHMETIC ON COMPUTERS 11 where the bi’s are either 0 or 1. We compute a decimal number using the following formula: d10 = bn × 2n + bn−1 × 2n−1 + bn−2 × 2n−2 ··· b2 × 22 + b1 × 21 + b0 × 20 . For example, the result of the two more difficult calculations above can be checked as follows: 101102 = 1 × 24 + 0 × 23 + 1 × 22 + 1 × 21 + 0 × 20 = 24 + 22 + 21 = 1610 + 410 + 210 = 2210 is the result of one of the additions [11112(1510) + 1112(710)] above, while 11010012 = 26 + 25 + 23 + 20 = 6410 + 3210 + 810 + 110 = 10510 is the result of one of the multiplications [11112(1510) × 1112(710)] above. Note that the subscript “2” indicates a binary or base-2 number while the subscript “10” indicates a decimal number. 2.4.2 Real numbers To convert a real(non-whole) binary number to a real decimal number, consider a binary number of the form: bnbn−1bn−2 ··· b2b1b0 . b−1b−2 ··· b−(m−2)b−(m−1)b−m, where the bi’s are either 0 or 1 anda period, “.”, separates the whole part, bi where i ≥ 0 from the fractional part, bi where i < 0. We compute a real decimal number using the following formula: r10 = bn×2n+bn−1×2n−1 ··· b1×21 +b0×20 +b−1×2−1 +b−2×2−2 ···+b−(m−1)×2−(m−1)+b−(m)×2−m. It is not a whole lot different from the decimal numbers you are used to. However, sometimes the formulae can look a little messy. 2.5 Binary integer arithmetic on computers Computers, because of their comprehension of data in binary terms, naturally do their arithmetic using the base-2 representation. The circuitry within a computer is most easily set up this way. However, when it comes to base-2 arithmetic andcomputers, there is a subtle difference! For practical reasons, computers must deal with integers that are finite in length. 16 bits, representing 65,536 separate possibilities, usedto be the norm. Today
12 CHAPTER 2.DATA REPRESENTATIONS 32 bits is common (4294967296 possibilities).Soon,64 bits (about 18x1018)will be the standard.Some computers nowadays permit hardware 64-bit integer arithmetic. Let us consider 32-bit computers only-the most common type of hardware available today. In the course of doing an arithmetic calculation,any bits that are set beyond the 32-bit boundary are lost-they fall into the "bit bucket"and disappear. 2.5.1 Two's-complement integer arithmetic A string of 32-bits can represent many things but we will focus on hexadecimal,unsigned and signed integers.These signed integers must also carry information as to the sign of the number.Historically,there have been several ways to do this.The "industry"has "settled" on "two's-complement arithmetic"because it simplifies the process of adding positive,nega- tive or mixed numbers.In this scheme,to negate a signed integer,one takes the complement (change all the 1s to 0s and all the 0s to 1s)of the binary representation and adds 1 to it. This is seen in the table at the end of this chapter. Let's give the notation i to the complement of the integer i.So,for any i, i+i=11111111111111111111111111111111.That is: any 32-bit pattern complement of the above =11111111111111111111111111111111 and 11111111111111111111111111111111 00000000000000000000000000000001 =00000000000000000000000000000000 since the 33rd bit can not be set!In two's-complement arithmetic the expression i-j is calculated as i++1.So you see,computers can not really add and subtract,they can only add (and take complements)! A few examples help illustrate the simplicity of the two's-complement scheme.Consider a 4-bit representation of the number 310=00112 and 410 =01002.There are two tricks you should apply here:a)every time you see a negative sign in front of a bit pattern,i,to be used in a calculation,convert it to a positive sign,change i to i+1 and do the binary addition, and,b)if a final result has a leading order (leftmost)bit set to 1,it is a negative number, so,extract the minus sign and convert the resultant bit pattern j to j+1. 310+410=00112+01002=01112=710 310-410=00112-01002=00112+11002=11112=-00012=-110 -310-410=-00112-01002=11012+11002=10012=-01112=-710
12 CHAPTER 2. DATA REPRESENTATIONS 32 bits is common (4294967296 possibilities). Soon, 64 bits (about 18×1018) will be the standard. Some computers nowadays permit hardware 64-bit integer arithmetic. Let us consider 32-bit computers only—the most common type of hardware available today. In the course of doing an arithmetic calculation, any bits that are set beyond the 32-bit boundary are lost—they fall into the “bit bucket” and disappear. 2.5.1 Two’s-complement integer arithmetic A string of 32-bits can represent many things but we will focus on hexadecimal, unsigned andsignedintegers. These signedintegers must also carry information as to the sign of the number. Historically, there have been several ways to do this. The “industry” has “settled” on “two’s-complement arithmetic” because it simplifies the process of adding positive, negative or mixednumbers. In this scheme, to negate a signedinteger, one takes the complement (change all the 1s to 0s and all the 0s to 1s) of the binary representation and adds 1 to it. This is seen in the table at the endof this chapter. Let’s give the notation i to the complement of the integer i. So, for any i, i + i = 11111111111111111111111111111111. That is: any 32-bit pattern + complement of the above = 11111111111111111111111111111111 and 11111111111111111111111111111111 + 00000000000000000000000000000001 = 00000000000000000000000000000000 since the 33rdbit can not be set! In two’s-complement arithmetic the expression i − j is calculatedas i+j + 1. So you see, computers can not really addandsubtract, they can only add (and take complements)! A few examples help illustrate the simplicity of the two’s-complement scheme. Consider a 4-bit representation of the number 310 = 00112 and410 = 01002. There are two tricks you shouldapply here: a) every time you see a negative sign in front of a bit pattern, i, to be used in a calculation, convert it to a positive sign, change i to i + 1 and do the binary addition, and, b) if a final result has a leading order (leftmost) bit set to 1, it is a negative number, so, extract the minus sign andconvert the resultant bit pattern j to j + 1. 310 + 410 = 00112 + 01002 = 01112 = 710 310 − 410 = 00112 − 01002 = 00112 + 11002 = 11112 = −00012 = −110 −310 − 410 = −00112 − 01002 = 11012 + 11002 = 10012 = −01112 = −710
2.6.32-BIT BINARY,HEXADECIMAL,UNSIGNED AND SIGNED INTEGERS 13 See how easily it all worked out!This is why the two's-complement approach has been adopted.In order to handle negative integers one can convert them to their two's-complement counterparts and add.Otherwise,special circuitry would have to be developed for handling negative numbers and that would be less efficient. 2.6 32-bit Binary,Hexadecimal,Unsigned and Signed Integers 32-bit computers can represent 232=4,294,672,296 different things but ONLY 4,294,672,296 different things.Now we consider the conventional assignments to“unsigned”and“signed” integers.There is also the hexadecimal representation that is associated with every 4-bit sequence,as indicated in the table below. The unsigned integers associate the decimal number 0 to a string of 32 0 bits.The rest are formed by the addition by 1 in either binary or decimal.The maximum unsigned integer, therefore,is 4,294,672,295.Adding a one to this causes all the 32 bits to go back to zero, exactly as if you had "cycled"the odometer in your car!It's the same principle.There is no 33rd bit,so you can imagine it just falls off the end. The signed integers have the same sequence as the unsigned integers up to 231-1= 2147483647 which is the bit pattern 01111111111111111111111111111111.Adding a one to this gives a bit pattern of 10000000000000000000000000000000 which is interpreted as -231 =-2147483648.Note that these two are complements of each other and that they add up to 11111111111111111111111111111111,which has the interpretation "-1",consistent with the “two's-complement”scheme described above
2.6. 32-BIT BINARY, HEXADECIMAL, UNSIGNED AND SIGNED INTEGERS 13 See how easily it all workedout! This is why the two’s-complement approach has been adopted. In order to handle negative integers one can convert them to their two’s-complement counterparts and add. Otherwise, special circuitry would have to be developed for handling negative numbers andthat wouldbe less efficient. 2.6 32-bit Binary, Hexadecimal, Unsigned and Signed Integers 32-bit computers can represent 232 = 4, 294, 672, 296 different things but ONLY 4, 294, 672, 296 different things. Now we consider the conventional assignments to “unsigned” and “signed” integers. There is also the hexadecimal representation that is associated with every 4-bit sequence, as indicated in the table below. The unsignedintegers associate the decimal number 0 to a string of 32 0 bits. The rest are formed by the addition by 1 in either binary or decimal. The maximum unsigned integer, therefore, is 4, 294, 672, 295. Adding a one to this causes all the 32 bits to go back to zero, exactly as if you had “cycled” the odometer in your car! It’s the same principle. There is no 33rdbit, so you can imagine it just falls off the end. The signedintegers have the same sequence as the unsignedintegers up to 231 − 1 = 2147483647 which is the bit pattern 01111111111111111111111111111111. Adding a one to this gives a bit pattern of 10000000000000000000000000000000 which is interpretedas −231 = −2147483648. Note that these two are complements of each other andthat they add up to 11111111111111111111111111111111, which has the interpretation “-1”, consistent with the “two’s-complement” scheme described above