(The material in this lab was taken in part from a laboratory exercise developed by Paul Gough for G6015 Computer Architectures, a course offered at the University of Sussex.)
In this lab, you will work with the three main number systems used in most kinds of digital design. They are the Decimal (d), Binary (0b) and Hexadecimal (0x). You will learn how to perform conversions between these three number systems and how to perform simple arithmetic operations including subtraction using the two's complement method.
All number systems commonly used today are positional systems, i.e. a number is represented by a
string of digits, where each digit position has an associated weight. The value of a number is a weighted sum of the digits.
In decimal systems,
each weight is a power of 10 corresponding to the digit's position. In this case, the
base of the number system is 10 and the system is known as decimal (d).
For example:
1734(d) = 1 × 1000 + 7 × 100 + 3 × 10 + 4 × 1
or, if you prefer
1734(d) = 1 × 103 + 7 × 102 + 3 × 101 + 4 × 10
A decimal point allows negative as well as positive powers of 10 to be
used.
235.78(d) = 2 × 100 + 3 × 10 + 5 × 1 + 7 × 0.1 + 8 × 0.01
235.78(d) = 2 × 102 + 3 × 101 + 5 × 100 + 7 × 10-1 + 8 × 10-2
The number of possible values of each digit is equal to the value of the base. These values start with 0 and go up to one less than the base. Consequently, in the case of decimal (base 10) numbers, the digits are from 0 to 9.
Binary digits (bits) are the digits of a number system where the base is 2. Hence the
possible values are only 0 and 1.
For example, in the binary number system,
(0b)10111001 = 1 × 27
+ 0 × 26
+ l × 25
+ l × 24
+ l × 23
+ 0 × 22
+ 0 × 21
+ 1 × 20 = l85(d)
Of course, you can just omit the 0 terms to compute this number as
(0b)10111001 = 1 × 27
+ l × 25
+ l × 24
+ l × 23
+ 1 × 20 = l85(d)
The leftmost bit of a binary number contributes the most to the number and is therefore called the Most Significant Bit (MSB). The rightmost bit is called the Least Significant Bit (LSB).
In standard number notation (but not in C or Java programs), leading zeros are often omitted since they contribute nothing to the sum. So, in binary 101 and 00101 are the same, and in decimal 007 and 7 are the same. However, in actual hardware the leading digits are almost always stored someplace.
By the way, Java 7 adds a new notation for literals expressed
as binary numbers. This allows the decimal number 185 to be written
as 0b10111001 in your Java programs.
Hexadecimal (or hex for short) is the positional number system where the base is l6, and hence the digits can have one of
a possible l6 values.
These sixteen digits cannot be represented by the ten usual digits,
so the six letters from A to F are used for digits numbered from 10 to 15.
The means that C as a hex digit has the value 12.
For example,
(0x)B9 = 11 × 16 + 9 × 1 = l85(d)
Both C and Java allow literals to be written in
hexadecimal. They allow the decimal number 185 to be written
as 0xB9.
The procedure to follow to correctly convert a decimal number to any other number system is tedious at best. Several successive divisions of the original number by the base of the system is required to convert a number.
Assume the number we wish to convert to binary is 84(d).
The conversion will then be: 84(d) = (0b)1010100.
Similarly for Hex we have, assuming we wish to convert 108(d).
Hence, the conversion will be: 108(d) = (0x)6C.
It is very simple to convert a binary number to hex. This is because four bits represent one hex digit. This is also the reason for the common use of hex numbers as a shorthand for binary.
| Show your show your solutions to your instructor. |
Binary addition is based on the same principle as decimal addition, namely that of adding corresponding digits, and moving across the carry. However, whether a carry or not is generated is based on the following rules:
| 0 | 0 | 1 |
| +0 | +1 | +1 |
| 0, no carry | 1, no carry | 0, carry 1 |
For example:
(0b)11001
+ (0b)01100
(0b)100101
Add the following, and convert the result to decimal:
| Show your show your solutions to your instructor. |
If you subtract 17 from 3, you'll get -14. Before looking into subtraction, we need to figure out how to represent negative numbers, such as -14, with bits. Perhaps the most obvious solution would be to set aside the first bit as the sign. For example, if the MSB is 0, the number is positive and, if the MSB is 1, the number is negative.
However, that's not how it's done. Today computers represent signed integers with two's complement notation. In two's complement notation a word, a fixed number of bits, is set aside to represent signed integers. Usually the word size is 32; but in our examples we'll use 8, because that's 75% smaller.
In two's complement notation, the MSB is 0 for positive numbers and 1 for negative numbers. The two's complement representation of a positive numbers is the same as the unsigned binary representation that we learned above. But in two's complement representation we must be sure to add enough leading zeros to fill the word. So in 8-bit two's complement, 17(d) is (0b)00010001 and 3(d) is (0b)00000011.
To find the representation of a negative number, such as -17(d), start with the bits for the absolute value of the number. In this case that would be (0b)00010001. Next invert all those bits to obtain ths one's complement. Here this gives us (0b)11101110. Now, add one to this number to obtain the two's complement. In this case, (0b)11101111.
Just for fun add 17(d) (or (0b)00010001) to -17(d) (or (0b)11101111). This will give you a 9-bit result, but you must throw away the 9th bit because it exceed the capacity of our 8-bit word.
00010001 17
+ 11101111 + -17
-------- -----
00000000 0
It is comforting to get 0! Now let's try adding 3(d) to -17(d) and then let's add 14(d) to that result. We better get 0 again. let's
00000011 3
+ 11101111 + -17
-------- -----
11110010 ??
+ 00001110 + 14
-------- -----
00000000 0
It is worthwhile to make an important distinction here. The 8-bit two's complement representation of 107(d) is (0b)01101011. But we can also refer to two's complement as an operation, as in, "what's the two's complement of that number." Referring now to the two's complement operation, the 8-bit two's complement of (0b)01101011 is (0b)10010101. The 8-bit two's complement representation of -107(d) is (0b)10010101. The 8-bit two's complement (i.e., an operation) of (0b)10010101 is (0b)01101011.
Binary subtraction requires a minuend, the number we're subtracted from, and a subtrahend. In computers this is done by adding the minuend to the two's complement of the subtrahend. The subtraction then follows the rules of a simple binary addition, though you do discard that extra-bit.
Suppose you are going to compute 100(d) - (-1(d)) in a system that uses 8-bit two's complement representation. The two's complement representation of 100(d) is (0b)01101000 and the two's complement representation of -1(d) is (0b)11111111. (Remember, that one. No matter how many bits are in a word; in two's complement representation, when all the bits are 1, the word represents -1.) The two's complement of (0b)11111111 is (0b)00000001. (0b)01101000 + (0b)00000001 is (0b)01101001, or 101(d).
The Java language specification requires that integers be stored in two's complement representation.
Consequently, in Java, -x is the two's complement of the
int variable x. In Java, the one's complement of x is ~x.
If you wish to be obscure, you can write the integer subtraction
17-x as 17+~x+1, since
~x+1 is -x.
| Show your solutions to your instructor. |
Arithmetic overflow occurs when the magnitude of the numeric value to be stored is greater than that which can be represented in the number of bits provided.
In an unsigned binary representation, the maximum numeric value that can be represented in
N bits is 2N -1. For example:
8 bits: maximum representable value 28 - 1 = 255
16 bits: maximum representable value 216 - 1 = 65,535
32 bits: maximum representable value 232 - 1 = 4,294,967,295 (the most common width for personal computers as of 2005),
64 bits: maximum representable value 264 - 1 = 18,446,744,073,709,551,615
128 bits: maximum representable value 2128 - 1 = 340,282,366,920,938,463,463,374,607,431,768,211,455
In an unsigned binary representation, overflow occurs when there is a carry out of the MSB.
In a two's complement representation, the values expressed in N bits must include
both positive and negative numbers. An N-bit two's-complement representation can express every integer in the range
-2N-1 to 2N-1-1.
The rules for detecting overflow in a two's complement representation during addition are simple:
In an unsigned binary representation, a carry out of the MSB is equivalent to overflow. In a two's complement representation, a carry out of the MSB does not identify overflow. Overflow in a two's complement representation occurs when the carry into the MSB is different than the carry out of the MSB.
A negative number added to a positive number cannot create overflow, because their sum is between the addends. Since both of the addends fit within the allowable range of numbers, and their sum is between them, it must fit as well.
As mentioned above, the integer data type is a signed number and therefore uses a two's complement representation. In this section of the lab, we'll look at two complement overflow in the C programming language. We'll use the Netbeans IDE to write and run C programs because that's the IDE used in CSCI 202.
1. Launch Netbeans by opening a terminal window under Linux and entering the command: Netbeans &
2. Open the New Project wizard by choosing File > New Project.
3. In the wizard, select the C/C++ category. The wizard gives you a choice of several types of new projects. Select C/C++ Application and click Next.
4. Create a new C/C++ Application project from the wizard using the defaults. You can choose the name of the project and the location of the project
or go with the default.
Be sure to also specify that the main file is in C. The default is C++.
This is done with the pull-down box on the right as shown below.
5. Click Finish to exit the wizard.
6. Select the Files tab on the left-hand side of the IDE window. This window shows the physical view of your project. It displays files and folders as they are stored on disk.
7. Double-click on the file entitled, main.c to open it in the editor window.
The numeric range of the integer data type varies, but typical ranges are listed on Wikipedia Integer page.
Your job is to verify the range of integers in our implementation of C; identify both the smallest and largest number that can be represented as an integer in your C program. Be prepared to show your instructor the output of your program demonstrating your findings. The program below is provided as a helpful example.
| Show your program demonstrating the range of integers to your instructor. |