C++ Programming/Chapter Learning the Basics
From Wikibooks, the open-content textbooks collection
Binary Number System The Binary Number Base Systems Most modern computer systems (including the IBM PC) operate using binary logic. The computer represents values using two voltage levels (usually 0V for logic 0 and either +3.3 V or +5V for logic 1). With two levels we can represent exactly two different values. These could be any two different values, but by convention we use the values zero and one. These two values, coincidentally, correspond to the two digits used by the binary number system. Since there is a correspondence between the logic levels used by the computer and the two digits used in the binary numbering system, it should come as no surprise that computers employ the binary system. The binary number system works like the decimal number system except the Binary Number System: uses base 2 includes only the digits 0 and 1 (any other digit would make the number an invalid binary number)
Binary addition (unsigned)
Example:
011110 <-- carries
101101
+ 100111
overflow --> 1 010100
The weighted values for each position is determined as follows: 2^7 2^6 2^5 2^4 2^3 2^2 2^1 2^0 2^-1 2^-2 128 64 32 16 8 4 2 1 .5 .25 In the United States among other countries, every three decimal digits is separated with a comma to make larger numbers easier to read. For example, 123,456,789 is much easier to read and comprehend than 123456789. We will adopt a similar convention for binary numbers. To make binary numbers more readable, we will add a space every four digits starting from the least significant digit on the left of the decimal point. For example, the binary value 1010111110110010 will be written 1010 1111 1011 0010.
Number Base Conversion Binary to Decimal It is very easy to convert from a binary number to a decimal number. Just like the decimal system, we multiply each digit by its weighted position, and add each of the weighted values together. For example, the binary value 1100 1010 represents: 1*2^7 + 1*2^6 + 0*2^5 + 0*2^4 + 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0 = 1 * 128 + 1 * 64 + 0 * 32 + 0 * 16 + 1 * 8 + 0 * 4 + 1 * 2 + 0 * 1 = 128 + 64 + 0 + 0 + 8 + 0 + 2 + 0 = 202
Decimal to Binary To convert decimal to binary is slightly more difficult. There are two methods, that may be used to convert from decimal to binary, repeated division by 2, and repeated subtraction by the weighted position value. Repeated Division By 2 For this method, divide the decimal number by 2, if the remainder is 0, on the side write down a 0. If the remainder is 1, write down a 1. This process is continued by dividing the quotient by 2 and dropping the previous remainder until the quotient is 0. When performing the division, the remainders which will represent the binary equivalent of the decimal number are written beginning at the least significant digit (right) and each new digit is written to more significant digit (the left) of the previous digit. Consider the number 2671. Division Quotient Remainder Binary Number 2671 / 2 1335 1 1 1335 / 2 667 1 11 667 / 2 333 1 111 333 / 2 166 1 1111 166 / 2 83 0 0 1111 83 / 2 41 1 10 1111 41 / 2 20 1 110 1111 20 / 2 10 0 0110 1111 10 / 2 5 0 0 0110 1111 5 / 2 2 1 10 0110 1111 2 / 2 1 0 010 0110 1111 1 / 2 0 1 1010 0110 1111
The Subtraction Method For this method, start with a weighted position value greater that the number. If the number is greater than the weighted position for the digit, write down a 1 and subtract the weighted position value.
If the number is less than the weighted position for the digit, write down a 0 and subtract 0. This process is continued until the result is 0. When performing the subtraction, the digits which will represent the binary equivalent of the decimal number are written beginning at the most significant digit (the left) and each new digit is written to the next lesser significant digit (on the right) of the previous digit. Consider the same number, 2671, using a different method. Weighted Value Subtraction Remainder Binary Number 2^12 = 4096 2671 - 0 2671 0 2^11 = 2048 2671 - 2048 623 0 1 2^10 = 1024 623 - 0 623 0 10 2^9 = 512 623 - 512 111 0 101 2^8 = 256 111 - 0 111 0 1010 2^7 = 128 111 - 0 111 0 1010 0 2^6 = 64 111 - 64 47 0 1010 01 2^5 = 32 47 - 32 15 0 1010 011 2^4 = 16 15 - 0 15 0 1010 0110 2^3 = 8 15 - 8 7 0 1010 0110 1 2^2 = 4 7 - 4 3 0 1010 0110 11 2^1 = 2 3 - 2 1 0 1010 0110 111 2^0 = 1 1 - 1 0 0 1010 0110 1111 ________________________________________ Binary Number Formats We typically write binary numbers as a sequence of bits (bits is short for binary digits). We have defined boundaries for these bits. These boundaries are: Name Size (bits) Example Bit 1 1 Nibble 4 0101 Byte 8 0000 0101 Word 16 0000 0000 0000 0101 Double Word 32 0000 0000 0000 0000 0000 0000 0000 0101 In any number base, we may add as many leading zeroes as we wish without changing its value. However, we normally add leading zeroes to adjust the binary number to a desired size boundary. For example, we can represent the number five as: Bit 101 Nibble 0101 Byte 0000 0101 Word 0000 0000 0000 0101 We'll number each bit as follows: 1. The rightmost bit in a binary number is bit position zero. 2. Each bit to the left is given the next successive bit number. Bit zero is usually referred to as the LSB (least significant bit). The left-most bit is typically called the MSB (most significant bit). We will refer to the intermediate bits by their respective bit numbers.
The Bit The smallest "unit" of data on a binary computer is a single bit. Since a single bit is capable of representing only two different values (typically zero or one) you may get the impression that there are a very small number of items you can represent with a single bit. Not true! There are an infinite number of items you can represent with a single bit. With a single bit, you can represent any two distinct items. Examples include zero or one, true or false, on or off, male or female, and right or wrong. However, you are not limited to representing binary data types (that is, those objects which have only two distinct values). To confuse things even more, different bits can represent different things. For example, one bit might be used to represent the values zero and one, while an adjacent bit might be used to represent the values true and false. How can you tell by looking at the bits? The answer, of course, is that you can't. But this illustrates the whole idea behind computer data structures: data is what you define it to be. If you use a bit to represent a boolean (true/false) value then that bit (by your definition) represents true or false. For the bit to have any true meaning, you must be consistent. That is, if you're using a bit to represent true or false at one point in your program, you shouldn't use the true/false value stored in that bit to represent red or blue later. Since most items you will be trying to model require more than two different values, single bit values aren't the most popular data type. However, since everything else consists of groups of bits, bits will play an important role in your programs. Of course, there are several data types that require two distinct values, so it would seem that bits are important by themselves. however, you will soon see that individual bits are difficult to manipulate, so we'll often use other data types to represent boolean values.
The Nibble A nibble is a collection of bits on a 4-bit boundary. It wouldn't be a particularly interesting data structure except for two items: BCD (binary coded decimal) numbers and hexadecimal (base 16) numbers. It takes four bits to represent a single BCD or hexadecimal digit. With a nibble, we can represent up to 16 distinct values. In the case of hexadecimal numbers, the values 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F are represented with four bits. BCD uses ten different digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) and requires four bits. In fact, any sixteen distinct values can be represented with a nibble, but hexadecimal and BCD digits are the primary items we can represent with a single nibble. b3 b2 b1 b0
The Byte Without question, the most important data structure used by the 80x86 microprocessor is the byte. This is true since the ASCII code is a 7-bit non-weighted binary code that is used on the byte boundary in most computers. A byte consists of eight bits and is the smallest addressable datum (data item) in the microprocessor. Main memory and I/O addresses in the PC are all byte addresses. This means that the smallest item that can be individually accessed by an 80x86 program is an 8-bit value. To access anything smaller requires that you read the byte containing the data and mask out the unwanted bits. The bits in a byte are numbered from bit zero (b0) through seven (b7) as follows: b7 b6 b5 b4 b3 b2 b1 b0 Bit 0 is the low order bit or least significant bit, bit 7 is the high order bit or most significant bit of the byte. We'll refer to all other bits by their number. A byte also contains exactly two nibbles. Bits b0 through b3 comprise the low order nibble, and bits b4 through b7 form the high order nibble. Since a byte contains exactly two nibbles, byte values require two hexadecimal digits. Since a byte contains eight bits, it can represent 2^8, or 256, different values. Generally, we'll use a byte to represent: 1. unsigned numeric values in the range 0 => 255 2. signed numbers in the range -128 => +127 3. ASCII character codes 4. other special data types requiring no more than 256 different values. Many data types have fewer than 256 items so eight bits is usually sufficient. Since the PC is a byte addressable machine, it turns out to be more efficient to manipulate a whole byte than an individual bit or nibble. For this reason, most programmers use a whole byte to represent data types that require no more than 256 items, even if fewer than eight bits would suffice. For example, we'll often represent the boolean values true and false by 00000001 and 00000000 (respectively). Probably the most important use for a byte is holding a character code. Characters typed at the keyboard, displayed on the screen, and printed on the printer all have numeric values. To allow it to communicate with the rest of the world, the IBM PC uses a variant of the ASCII character set. There are 128 defined codes in the ASCII character set. IBM uses the remaining 128 possible values for extended character codes including European characters, graphic symbols, Greek letters, and math symbols.
The Word NOTE: The boundary for a Word is defined as either 16-bits or the size of the data bus for the processor, and a Double Word is Two Words. Therefore, a Word and a Double Word is not a fixed size but varies from system to system depending on the processor. However, for our discussion, we will define a word as two bytes. For the 8085 and 8086, a word is a group of 16 bits. We will number the bits in a word starting from bit zero (b0) through fifteen (b15) as follows: b15 b14 b13 b12 b11 b10 b9 b8 b7 b6 b5 b4 b3 b2 b1 b0 Like the byte, bit 0 is the LSB and bit 15 is the MSB. When referencing the other bits in a word use their bit position number. Notice that a word contains exactly two bytes. Bits b0 through b7 form the low order byte, bits 8 through 15 form the high order byte. Naturally, a word may be further broken down into four nibbles. Nibble zero is the low order nibble in the word and nibble three is the high order nibble of the word. The other two nibbles are "nibble one" or "nibble two". With 16 bits, you can represent 2^16 (65,536) different values. These could be the unsigned numeric values in the range of 0 => 65,535, signed numeric values in the range of -32,768 => +32,767, or any other data type with no more than 65,536 values. The three major uses for words are 1. 16-bit integer data values 2. 16-bit memory addresses 3. any number system requiring 16 bits or less The Double Word A double word is exactly what its name implies, two words. Therefore, a double word quantity is 32 bits. Naturally, this double word can be divided into a high order word and a low order word, four bytes, or eight nibbles. Double words can represent all kinds of different data. It may be 1. an unsigned double word in the range of 0 => 4,294,967,295, 2. a signed double word in the range -2,147,483,648 => 2,147,483,647, 3. a 32-bit floating point value 4. any data that requires 32 bits or less. Octal Number System The Octal Number Base System Although this was once a popular number base, especially in the Digital Equipment Corporation PDP/8 and other old computer systems, it is rarely used today. The Octal system is based on the binary system with a 3-bit boundary. The Octal Number System: uses base 8 includes only the digits 0 through 7 (any other digit would make the number an invalid octal number)
Octal (digits 0 to 7) Group three binary digits together and represent as base 8.
The weighted values for each position is as follows: 8^5 8^4 8^3 8^2 8^1 8^0 32768 4096 512 64 8 1 Binary to Octal Conversion It is easy to convert from an integer binary number to octal. This is accomplished by: 1. Break the binary number into 3-bit sections from the LSB to the MSB. 2. Convert the 3-bit binary number to its octal equivalent. For example, the binary value 1010111110110010 will be written: 001 010 111 110 110 010 1 2 7 6 6 2 Octal to Binary Conversion It is also easy to convert from an integer octal number to binary. This is accomplished by: 1. Convert the decimal number to its 3-bit binary equivalent. 2. Combine the 3-bit sections by removing the spaces. For example, the octal value 127662 will be written: 1 2 7 6 6 2 001 010 111 110 110 010 This yields the binary number 001010111110110010 or 00 1010 1111 1011 0010 in our more readable format. Octal to Decimal Conversion To convert from Octal to Decimal, multiply the value in each position by its Octal weight and add each value. Using the value from the previous example, 127662Q, we would expect to obtain the decimal value 44978. 1*8^5 2*8^4 7*8^3 6*8^2 6*8^1 2*8^0 1*32768 2*4096 7*512 6*64 6*8 2*1 32768 8192 3584 384 48 2 32768 + 8192 + 3584 + 384 + 48 + 2 = 44978 Decimal to Octal Conversion To convert decimal to octal is slightly more difficult. The typical method to convert from decimal to octal is repeated division by 8. While we may also use repeated subtraction by the weighted position value, it is more difficult for large decimal numbers. Repeated Division By 8 For this method, divide the decimal number by 8, and write the remainder on the side as the least significant digit. This process is continued by dividing he quotient by 8 and writing the remainder until the quotient is 0. When performing the division, the remainders which will represent the octal equivalent of the decimal number are written beginning at the least significant digit (right) and each new digit is written to the next more significant digit (the left) of the previous digit. Consider the number 44978. Division Quotient Remainder Octal Number 44978 / 8 5622 2 2 5622 / 8 702 6 62 702 / 8 87 6 662 87 / 8 10 7 7662 10 / 8 1 2 27662 1 / 8 0 1 127662 As you can see, we are back with the original number. That is what we should expect Hexadecimal Number System A big problem with the binary system is verbosity. To represent the value 202 requires eight binary digits. The decimal version requires only three decimal digits and, thus, represents numbers much more compactly than does the binary numbering system. This fact was not lost on the engineers who designed binary computer systems. When dealing with large values, binary numbers quickly become too unwieldy. The hexadecimal (base 16) numbering system solves these problems. Hexadecimal numbers offer the two features: • hex numbers are very compact • it is easy to convert from hex to binary and binary to hex. Since we'll often need to enter hexadecimal numbers into the computer system, we'll need a different mechanism for representing hexadecimal numbers since you cannot enter a subscript to denote the radix of the associated value. The Hexadecimal system is based on the binary system using a Nibble or 4-bit boundary. In Assembly Language programming, most assemblers require the first digit of a hexadecimal number to be 0, and we place an H at the end of the number to denote the number base. The Hexadecimal Number System: uses base 16 includes only the digits 0 through 9 and the letters A, B, C, D, E, and F
Group four binary digits together and represent as base 16.
Hexadecimal-to-decimal conversion Sum of powers method Converts from least significant to most significant digit:
Multiply and add method Converts from most significant to least significant digit:
In the Hexadecimal number system, the hex values greater than 9 carry the following decimal value: Binary Octal Decimal Hex 0000B 00Q 00 00H 0001B 01Q 01 01H 0010B 02Q 02 02H 0011B 03Q 03 03H 0100B 04Q 04 04H 0101B 05Q 05 05H 0110B 06Q 06 06H 0111B 07Q 07 07H 1000B 10Q 08 08H 1001B 11Q 09 09H 1010B 12Q 10 0AH 1011B 13Q 11 0BH 1100B 14Q 12 0CH 1101B 15Q 13 0DH 1110B 16Q 14 0EH 1111B 17Q 15 0FH 1 0000B 20Q 16 10H This table provides all the information you'll ever need to convert from one number base into any other number base for the decimal values from 0 to 16. To convert a hexadecimal number into a binary number, simply brake the binary number into 4-bit groups beginning with the LSB and substitute the corresponding four bits in binary for each hexadecimal digit in the number. For example, to convert 0ABCDh into a binary value, simply convert each hexadecimal digit according to the table above. The binary equivalent is: 0ABCDH = 0000 1010 1011 1100 1101 To convert a binary number into hexadecimal format is almost as easy. The first step is to pad the binary number with leading zeros to make sure that the the binary number contains multiples of four bits. For example, given the binary number 10 1100 1010, the first step would be to add two bits in the MSB position so that it contains 12 bits. The revised binary value is 0010 1100 1010. The next step is to separate the binary value into groups of four bits, e.g., 0010 1100 1010. Finally, look up these binary values in the table above and substitute the appropriate hexadecimal digits, e.g., 2CA. The weighted values for each position is as follows: 16^3 16^2 16^1 16^0 4096 256 16 1 Binary to Hex Conversion It is easy to convert from an integer binary number to hex. This is accomplished by: 1. Break the binary number into 4-bit sections from the LSB to the MSB. 2. Convert the 4-bit binary number to its Hex equivalent. For example, the binary value 1010111110110010 will be written: 1010 1111 1011 0010 A F B 2 Hex to Binary Conversion It is also easy to convert from an integer hex number to binary. This is accomplished by: 1. Convert the Hex number to its 4-bit binary equivalent. 2. Combine the 4-bit sections by removing the spaces. For example, the hex value 0AFB2 will be written: A F B 2 1010 1111 1011 0010 This yields the binary number 1010111110110010 or 1010 1111 1011 0010 in our more readable format. Hex to Decimal Conversion To convert from Hex to Decimal, multiply the value in each position by its hex weight and add each value. Using the value from the previous example, 0AFB2H, we would expect to obtain the decimal value 44978. A*16^3 F*16^2 B*16^1 2*16^0 10*4096 15*256 11*16 2*1 40960 3840 176 2 40960 + 3840 + 176 + 2 = 44978
Decimal to Hex Conversion To convert decimal to hex is slightly more difficult. The typical method to convert from decimal to hex is repeated division by 16. While we may also use repeated subtraction by the weighted position value, it is more difficult for large decimal numbers. Repeated Division By 16 For this method, divide the decimal number by 16, and write the remainder on the side as the least significant digit. This process is continued by dividing the quotient by 16 and writing the remainder until the quotient is 0. When performing the division, the remainders which will represent the hex equivalent of the decimal number are written beginning at the least significant digit (right) and each new digit is written to the next more significant digit (the left) of the previous digit. Consider the number 44978. Division Quotient Remainder Hex Number 44978 / 16 2811 2 2 2811 / 16 175 11 B2 175 / 16 10 15 FB2 10 / 16 0 10 0AFB2 As you can see, we are back with the original number. That is what we should expect. When you use hex numbers in an 8085 program, the Assembler usually requires the most significant hex digit to be 0 even if this number of digits exceed the size of the register. This is an Assembler requirement and your value will be assembled correctly. Hex addition Add as if decimal numbers except: • if individual digits are A through F, convert to decimal equivalents and add • if sum is greater than 16, replace sum with sum minus 16 and carry 1 • if sum is between 10 and 15 (decimal), replace sum with equivalent hexadecimal digit
D 13
+ C = + 12 $19 25
carries --> 1 1
DF6D
+ 246C
overflow --> 1 03D9
Remember:
Example from the text of binary and hex addition carries --> 11111
111011
+ 100111
overflow --> 1 100010
carries --> 1 1
11001
+ 01101
overflow --> 1 00110
1235
+ 567A
no overflow --> 68AF
carries --> 111
A9876
+ FDCA0
overflow --> 1 A7516
Conversion Between Different Number Systems Positional number systems Our decimal number system is known as a positional number system, because the value of the number depends on the position of the digits. For example, the number 123 has a very different value than the number 321, although the same digits are used in both numbers. (Although we are accustomed to our decimal number system, which is positional, other ancient number systems, such as the Egyptian number system were not positional, but rather used many additional symbols to represent larger values.) In a positional number system, the value of each digit is determined by which place it appears in the full number. The lowest place value is the rightmost position, and each successive position to the left has a higher place value. In our decimal number system, the rightmost position represents the "ones" column, the next position represents the "tens" column, the next position represents "hundreds", etc. Therefore, the number 123 represents 1 hundred and 2 tens and 3 ones, whereas the number 321 represents 3 hundreds and 2 tens and 1 one. The values of each position correspond to powers of the base of the number system. So for our decimal number system, which uses base 10, the place values correspond to powers of 10: ... 1000 100 10 1 ... 10^3 10^2 10^1 10^0 Converting from other number bases to decimal Other number systems use different bases. The binary number system uses base 2, so the place values of the digits of a binary number correspond to powers of 2. For example, the value of the binary number 10011 is determined by computing the place value of each of the digits of the number: 1 0 0 1 1 the binary number 2^4 2^3 2^2 2^1 2^0 place values So the binary number 10011 represents the value
(1 * 2^4) + (0 * 2^3) + (0 * 2^2) + (1 * 2^1) + (1 * 2^0)
= 16 + 0 + 0 + 2 + 1 = 19 The same principle applies to any number base. For example, the number 2132 base 5 corresponds to 2 1 3 2 number in base 5 5^3 5^2 5^1 5^0 place values So the value of the number is
(2 * 5^3) + (1 * 5^2) + (3 * 5^1) + (2 * 5^0)
= (2 * 125) + (1 * 25) + (3 * 5) + (2 * 1) = 250 + 25 + 15 + 2 = 292 Converting from decimal to other number bases In order to convert a decimal number into its representation in a different number base, we have to be able to express the number in terms of powers of the other base. For example, if we wish to convert the decimal number 100 to base 4, we must figure out how to express 100 as the sum of powers of 4. 100 = (1 * 64) + (2 * 16) + (1 * 4) + (0 * 1)
= (1 * 4^3) + (2 * 4^2) + (1 * 4^1) + (0 * 4^0)
Then we use the coefficients of the powers of 4 to form the number as represented in base 4: 100 = 1 2 1 0 base 4 One way to do this is to repeatedly divide the decimal number by the base in which it is to be converted, until the quotient becomes zero. As the number is divided, the remainders - in reverse order - form the digits of the number in the other base. Example: Convert the decimal number 82 to base 6: 82/6 = 13 remainder 4 13/6 = 2 remainder 1 2/6 = 0 remainder 2 The answer is formed by taking the remainders in reverse order: 2 1 4 base 6 Fixed length binary numbers: • Computer arithmetic is performed on data stored in fixed length memory locations, typically 8, 16, or 32 bits.
• No signed numbers (no sign bit) An unsigned 8-bit binary number:
Example conversions between number systems: decimal binary hex
255 1111 1111 FF
93 0101 1101 5D
Special problems occur in manipulating fixed length numbers. decimal binary hex
201 = 11001001 = C9
+ 79 = + 01001111 = + 4F
280 = 1 00011000 = 1 18
overflow overflow
The number 280 (base 10) is larger than the maximum 8-bit number; this results in a carry beyond 8 bits in the binary representation and a carry beyond two digits in the hexadecimal representation. When doing arithmetic using fixed length numbers, these carries are potentially lost. How do you do negative numbers? Signed magnitude Use one bit for sign, 7 bits for number Example: -1 (in an 8-bit system) could be 1000 0001 (base 2) 2's complement (most often used in computing) Example: the 2's complement number representing -1 (in an 8-bit system) would be 1111 1111 (base 2) ________________________________________ What are complement numbers? Consider odometer numbers on a bicycle:
Decimal examples Odometer numbers are useful for both addition and subtraction (complements) of signed numbers. - 2 + 998 + 3 + 003 + 1 1 001
In the second example, the correct result is just the +001; the overflow is ignored in fixed-length complement arithmetic. Do subtraction as addition by using complements, i.e. A - B = A + (-B) Important: It is easier to compute -B and add than to subtract directly. Example: - 005 + 995 + 003 + 997 + 008 1 992
Note that 995 and 997 were added in the normal fashion, the overflow was ignored, and the result was 992, which can be converted from the complement (or odometer) system back to -8, the correct answer.
signed 3-bit complement
+3 003
+2 002
+1 001
0 000
-1 999
-2 998
-3 997
-4 996
-5 995
-6 994
-7 993
-8 992
decimal 2's complement binary
+127 01111111
+126 01111110
+125 01111101
... ........
+2 00000010
+1 00000001
0 00000000
-1 11111111
-2 11111110
... ........
-127 10000001
-128 10000000
There are 256 numbers in an 8-bit fixed length 2's complement number system. Why are these numbers called 2's complement? M - N = M + (-N) where -N is the complement of N.
Example: decimal
+ 1 = 00000001
- 1 = + 11111111
0 = 1 00000000
which does not equal 2^8, or 256; ignore the overflow, and the correct answer is zero. Now we need an easy way to do 2's complement operations.
Example: What is the representation of -27 (base 10) in 2's complement 8-bit notation?
2^8 - 1 11111111
- 27 - 00011011
11100100 corresponds to flipping all the bits;
also known as 1's complement
add 1 + 00000001
result 11100101 -27 in 2's complement representation
This approach is necessary because: 1. Fixed-length nature of numbers stored in a computer 2. More computationally efficient to implement a fast adder than an adder and a subtractor ________________________________________ Examples of 2's complement number operations Addition and subtraction in 2's complement form • Addition: To compute N1 + N2, add N1 to N2 • Subtraction: To compute N1 - N2, add N1 to -N2 Examples: decimal binary hex
11 = 00001011 = 000B + 21 = + 00010101 = + 0015 32 = 00100000 = 0020
21 = 00010101 = 0015 - 11 = + 11110101 = + FFF5 10 = 00001010 = 000A
11 = 00001011 = 000B - 21 = + 11101011 = + FFEB - 10 = 11110110 = FFF6
- 11 = 11110101 = FFF5 - 21 = + 11101011 = + FFEB - 32 = 1 11100000 = FFE0
How we got the 2's complements of -11 and -21:
11 00001011
~11 - 11110100 1's complement + 1 + 00000001 add 1 -11 11110101 2's complement representation
Algorithm 1. Store N. 2. Obtain ~N, the 1's complement of N, by replacing (bit by bit) every 0 with a 1 and vice versa in the number's binary representation. 3. Add 1 and ignore any carry after the eighth bit. Note: This algorithm works in hex by replacing each digit x with its hex complement, i.e. 15 - x. Example: The hex equivalent of 11 is $000B; its hex complement is then $FFF4, where each digit was computed as $F - x. Adding 1 to $FFF4 gives the result $FFF5 for the 2's complement of 11. (Using a dollar sign ($) before a number indicates that it is base 16.) Example: In binary:
N 0000 0110 0100 0111
~N - 1111 1001 1011 1000 1's complement +1 + 0000 0000 0000 0001 add 1 -N 1111 1001 1011 1001 2's complement representation
In hex:
N 0647
~N - F9B8 1's complement +1 + 0001 add 1 -N F9B9 2's complement representation
A calculator will always give you the 2's complement directly. The Most Significant Bit (MSB) is the binary digit corresponding to the largest power of 2 and is always 1 for a negative 2's complement number. As a result it is often called the sign bit. In 2's complement, -0 = +0. Technically, 0 is the complement of itself.
N 00000000
~N - 11111111 1's complement +1 + 00000001 add 1 -N 00000000 2's complement representation
________________________________________ Problems with fixed-length arithmetic Overflow and underflow For a 16-bit fixed-length number system,
Adding signed numbers can easily exceed these limits. first digit
0011 $3000
0110 $6000
1001 $9000
This result, from adding two positive numbers in the number system, results in $9000, which is larger than $7FFF, the largest allowed positive number. In fact, $9000 equals 1001 0000 0000 0000, which is a negative number. The sign of the result is different from that of the operands. Rule: If there is a sign change in adding two positive 2's complement numbers, then overflow has occurred. We can generalize these rules to signed addition and subtraction.
Sign extension How about if numbers are of different length? decimal 2's complement binary
3-bit 4-bit 8-bit
+3 011 0011 00000011
+2 010 0010 00000010
+1 001 0001 00000001
0 000 0000 00000000
-1 111 1111 11111111
-2 110 1110 11111110
-3 101 1101 11111101
-4 100 1100 11111100
To extend a 2's complement number to a greater number of binary digits, you just continue the sign bit to the left. Examples: Extend $9B to 16 bits. $9B = 1001 1011 = 1111 1111 1001 1011 = $FF9B
Extend $5F to 16 bits. $5F = 0101 1111 = 0000 0000 0101 1111 = $005F
Adding two 2's complement numbers of different length 43A0 43A0
9B FF9B need to sign extend; you can't just add zeros.
???? 1 433B
Note that the 8-bit $9B and the 16-bit $FF9B both represent -101 in their respective number systems.
