FIT1047 Tutorial 2
Topics
• 2’s complement, floating point
• Boolean logic, logic gates, logisim
Instructions
• The tasks are supposed to be done in groups. In some tasks, it might be useful to have different roles for people in the group.
Task 1: 2’s complement
1.a Assume you have 8 bits to represent binary numbers. What decimal value does the binary number 10110101 have in the different notations?
(i) unsigned binary number
In unsigned binary number, all the bits represent the number.
101101012 = 1×27 +0×26 +1×25 +1×24 +0×23 +1×22 +0×21 +1×20 = 18110
(ii) sign-magnitude notation
In this notation, the left bit represents the sign of the number: 0 for positive and 1 for negative. Thus, the number is negative. The actual value of the number is then just the binary representation of the remaining 7 bits:
101001012 = −(0×26 +1×25 +1×24 +0×23 +1×22 +0×21 +1×20 = −5310
(iii) 1’s complement
Let N = given number 101101012.
The 1 in the most significant bit indicates that N is a negative number. Thus, the number was derived by flipping all bits of the positive number with the same magni- tude. 1’s complement of N will give this corresponding positive number (i.e. flipping all 1s to 0s and 0s to 1s).
1’s complement of N is 01001010.
010010102 = 0×27 +1×26 +0×25 +0×24 +1×23 +0×22 +1×21 +0×20 = 7410 Thus, the actual value is −74.
(iv) 2’s complement
Let N = given number 101101012.
The 1 in the most significant bit indicates that N is a negative number. Calculating 2’s complement of N backwards (which is the same operation as the 2’s complement) will give the corresponding positive number (i.e. flipping all bits and then adding one bit, just discarding any carry bit).
2’s complement of N is 01001010 + 1 = 01001011.
FIT1047-Lab-Week2-solution 1
010110112 = 0×27 +1×26 +0×25 +0×24 +1×23 +0×22 +1×21 +1×20 = 7510 Thus, the actual value is −75.
1.b Create a table with all possible 4-bit binary values in one column and the decimal they represent in the different notations.
4-bit binary
unsigned int
sign-magnitude
1’s complement
2’s complement
0000
0
+0
+0
0
0001
1
1
1
1
0010
2
2
2
2
0011
3
3
3
3
0100
4
4
4
4
0101
5
5
5
5
0110
6
6
6
6
0111
7
7
7
7
1000
8
-0
-7
-8
1001
9
-1
-6
-7
1010
10
-2
-5
-6
1011
11
-3
-4
-5
1100
12
-4
-3
-4
1101
13
-5
-2
-3
1110
14
-6
-1
-2
1111
15
-7
-0
-1
1.c Assume you want to use a bit-wise approach to add 2 n-bit 2’s complement numbers x+y=z. You need to check for overflow.
Use the following notation:
x = xnxn−1xn−2…x1
y = ynyn−1yn−2…y1
z = znzn−1zn−2…z1
You can use a bit-wise + operator with one bit result and one bit for the carry: 0 + 0 = 0 with carry bit 0
0 + 1 = 1 with carry bit 0
1 + 0 = 1 with carry bit 0
1 + 1 = 0 with carry bit 1
For i = 1,..,n the carry bit is denoted by ci.
(i) For the actual addition, what do you need to do in steps i = 1, …, n? Foreachstepaddxi,yi andci−1 togetci andzi. Fori=1youneedtoassumethat
c0 = 0 and cn is just discarded.
(ii) In which steps do you need to check for overflow conditions? What do you need to
check?
– Ifxn =yn =0(botharepositive)weneedtocheckinstepnifzn =0. Ifzn =1, we have an overflow.
– IFxn =yn =1(botharenegative)weneedtocheckinstepn−1ifcn−1 =1. If cn−1 = 0, we have an overflow.
FIT1047-Lab-Week2-solution 2
Task 2: More on 2’s compliment & Floating-Point Representation
Represent the number −92 in
a) 8-bit signed magnitude
SOLUTION:
Just convert +92 to binary (getting 01011100) and put sign bit 1 out the front to get −92 (11011100).
Note: Here we don’t need to pad with leading 0s, but the students are reminded the need for that; i.e. in order to get required number of bits.
b) 8-bit 2’s complement
SOLUTION:
Again, start with +92 in 8 bits. (For positive numbers, signed magnitude is same as 2’s complement. For NEGATIVE numbers, they are quite different.)
Then negate, by complementing each bit then numerically adding 1.
10100011+1 = 10100100
c) 8-bit excess-k
SOLUTION:
k = 27− 1 = 127 −92 + 127 = 35 Result: 00100011
Calculate, using binary arithmetic with 8-bit 2’s complement representation:
a) 33+92
SOLUTION:
Same algorithm (ordinary “school” addition method, adapted to binary) regardless of signs.
92 01011100 33 00100001 —————-
01111101
SOLUTION:
Compute 33 – 92 by negating 92 (which we did in 1(b)) and finding 33 + (-92) by addition.
-92 10100100 33 00100001 —————-
11000101
What happens if you try to calculate 92+92?
SOLUTION:
92 + 92 gives integer overflow.
FIT1047-Lab-Week2-solution 3
b) 33-92
Convert the following numbers to 6-bit 2’s complement notation and add them:
Note: if carry in bit == carry out bit in MSB, then there’s no overflow. a) -16+11
SOLUTION:
-16 = 110000; 11 = 001011
110000 001011 ——- 111011
b) 16-11
SOLUTION:
16 = 010000; -11= 110100+1 = 110101
010000
110101
——-
000101
(Note that the “overflow” 1 isn’t really overflow, as we are subtracting)
c) 17+15
SOLUTION:
17 = 010001; 15 = 001111
010001
001111
——-
100000
(This is real overflow, as we cannot represent 32 in 6-bit 2’s complement)
d) -5-8
SOLUTION:
-5 = 111011; -8 = 111000
111011
111000
——-
110011
(This is also not real overflow; when you add two negative numbers and there is overflow, then you get a positive)
FIT1047-Lab-Week2-solution 4
Data Representation – Floating Point
(a)Give the 23-bit mantissa and the 8-bit exponent of the IEEE 754 standard floating-point representation of the decimal number 176. What is the sign bit of its IEEE standard floating-point representation?
SOLUTION:
• 176 = 10110000 in binary = 1.011 × 27
• 176 is a positive number, hence sign bit = 0
• 24-bit mantissa =1.01100000000000000000000
o Most significant bit not stored (always 1).
o So, stored bits are:01100000000000000000000
• Exponent = 7.
o In 8-bit excess-127, this is:10000110.
(b)Convert to scientific notation the following floating-point number stored according to the IEEE
standard. 1 00111001 01011100000000000000000
SOLUTION:
• •
• •
Sign is negative, because sign bit = 1. Exponent 00111001 in excess-k:
o 25+ 24+ 23+ 20= 32 + 16 + 8 + 1 = 57 o k = 127 ⇒ 57 − 127 = −70
o Exponent is −70
Mantissa gives 1.010111, which yields:
20+ 2−2+ 2−4+ 2−5+ 2−6= 1 + 0.25 + 0.0625 + 0.03125 + 0.015625 = 1.359375
The final result is −1.359375 × 2−70
(c) Give the IEEE standard floating-point representation of the binary number 1.11101101 × 2-5.
SOLUTION:
• Sign bit 0
• Exponent in excess-127 notation:
represent -5 as binary representation of (-5) + 127 = 122 = 01111010
• Mantissa is already there, except you drop the leading 1 and pad with 0s on the right-end.
ANSWER:
FIT1047-Lab-Week2-solution 5
Sign bit
Exponent bits
Mantissa bits
0
01111010
111011010000 0000 0000 000
Task 3: Boolean logic, logic gates, logisim
3.a
• try some combinations of gates
3.c In addition to AND, OR and NOT, there are a number of other Boolean logic operators.
Examples are XOR, the exclusive or, and NAND, a negated AND. Their truth tables are shown in the tables.
Build XOR and NAND in logisim only using AND, OR, and NOT gates. Use the simulation to test your result.
3.b
• Download logisim evolution from Moodle
• Start logisim by clicking on the file or executing java -jar logisim-evolution.jar
2.b Make yourself familiar with logisim by doing a few very easy tasks:
• place one AND gate, 2 inputs and one output • connect them
• poke the inputs to try simulation
• do the same with OR and NOT
A
B
AB
0 0 1 1
0 1 0 1
1 1 1 0
A
B
A⊕B
0 0 1 1
0 1 0 1
0 1 1 0
(a) XOR (b) NAND
FIT1047-Lab-Week2-solution
6
3.d (Additional advanced task:) Use logisim and only AND, OR and NOT to build a circuit for the following function:
F (A, B, C) = A ̄B ̄C + A ̄BC + AB ̄C ̄ + AB ̄C + ABC
How many gates do you need? Simplify the function first, e.g. by using k-maps.
One possible solution would need 3 gates: = C + AB ̄
FIT1047-Lab-Week2-solution 7