CSC231 Homework 4 Solutions -- 2010
--D. Thiebaut 21:54, 20 October 2010 (UTC)
- The answers are taken from Tiffany's, Angela T's, and Alec's homework answers.
Problem 1:
Option 1
The largest unsigned integer that can be represented using n bits is (2^n) - 1.
a) With 8 bits, we can represent values from 0 to (2^8) - 1 = 255. Thus we can
represent the following values in the fibonacci sequence: 1, 1, 2, 3, 5, 8,
13, 21, 34, 55, 89, 144, 233 -> 13 terms.
b) With 16 bits, we can represent values from 0 to (2^16) - 1 = 65,535. Thus we
can represent the following values in the fibonacci sequence: 1, 1, 2, 3, 5,
8, 13, 21,..., 46,368 -> 24 terms.
c) With 32 bits, we can represent values from 0 to (2^32) - 1 = 4,294,967,295.
Thus we can represent the following values in the fibonacci sequence: 1, 1,
3, 5, 8, 13, 21,..., 2,971,215,073 -> 47 terms.
d) With 64 bits, we can represent values from 0 to (2^64) - 1 =
18,446,744,073,709,551,615. Thus we can represent the following values in the fibonacci sequence: 1, 1, 3, 5, 8, 13, 21,..., 12,200,160,415,121,876,738
-> 93 terms.
Option 2
Fibonacci: 1,1,2,3,5,8,13...
* You could only be able to store up to 233. The next
value, 377, does not fit within 8 bits and will
instead be stored as 121. The max value for an 8bit
unsigned int is 255.
Number of terms: 13
* You can only store up to 46,368. The next value, 75,025,
is stored as 9,489. The max value for a 16bit unsigned
int is 65,535.
Number of terms: 24
* You can only store up to 2,971,215,073. The next value,
4,807,526,976 is stored as 512,559,680. The max value
for a 32bit unsigned int is 4,294,967,295.
Number of terms: 47
* You can only store up to 7,540,113,804,746,346,429. The
next value, 12,200,160,415,121,876,738 is stored as
-6,246,583,658,587,674,878. The max value for a 64bit
int (63bit unsigned int) is 9,223,372,036,854,775,807.
Number of terms: 92
Method:
----------------
Results were calculated with the following python code then
confirmed with windows calculatori (programmer view):
def fib(typ):
a = 1
b = 1
i = 2
while True:
v1 = a+b
v2 = typ(v1)
a = b
b = v1
i+=1
print "%d: %d %d" % (i, v1, v2.value)
if v1!=v2.value:
break
Output:
----------------------------
>>> from ctypes import *
>>> fib(c_uint8)
3: 2 2
4: 3 3
5: 5 5
6: 8 8
7: 13 13
8: 21 21
9: 34 34
10: 55 55
11: 89 89
12: 144 144
13: 233 233
14: 377 121
>>> fib(c_uint16)
3: 2 2
4: 3 3
5: 5 5
...snip...
23: 28657 28657
24: 46368 46368
25: 75025 9489
>>> fib(c_uint32)
3: 2 2
4: 3 3
5: 5 5
...snip...
46: 1836311903 1836311903
47: 2971215073 2971215073
48: 4807526976 512559680
>>> fib(c_int64)
3: 2 2
4: 3 3
5: 5 5
...snip...
91: 4660046610375530309 4660046610375530309
92: 7540113804746346429 7540113804746346429
93: 12200160415121876738 -6246583658587674878
Problem 2:
1) The unsigned integer x is initialized to the value of 3, which can be
representedin 4 bits as 0011. This initial value of x is printed before
entering the infinite while loop. Inside the loop, the previous value of x
gets stored in the unsigned itneger variable lastx. Then the value in x gets
multiplied by 2, which in binary means that all the bits get shifted to the
left by one. This process of storing the previous x value and shifting the
bits in x to the left continues until the value of x becomes less than the
value of lastx, in which case the respective values get printed and the
program breaks out of the loop. In this program, x becomes less than lastx
when when the most significant 1 gets shifted out of the bit sequence used to
to store integers. As such, the loop stopped when the previous value of x
(3,221,225,472), which is represented as
1100 0000 0000 0000 0000 0000 0000 0000 became
1000 0000 0000 0000 0000 0000 0000 0000 (2,147,483,648).
2) From the output it can be seen that in C++, 32 bits are used to store
integers.
3) By removing the word unsigned in front of int, the variables x and lastx are
now signed integers. using 2's complement, the most significant bit in the
32 bit sequence representing an integer controls the sign of the value
(0 = positive, 1 = negative). Thus, when the bits are shifted to the left by
one each time through the loop starting with the value of x = 3, the largest
positive value that can be stored in the integer is 1,610,612,736, which is
0110 0000 0000 0000 0000 0000 0000 0000. Once a 1 gets shifted into the
most significant bit, the value of x becomes negative, specifically,
-1,073,741,824, which is less than a positive integer, thus ending the loop.
4) In C++ 8 bits are used to store characters. It appears that when C++ converts
from a number to a character, the character value is treated as unsigned
(0110 0000 in unsigned binary = 96 in decimal = ` in char and 1100 0000 in
unsigned binary = 192 in decimal = capital A accent grave in char). However,
when char values are being compared as in if (x <= lastx), the character
variables are treated as signed since 1100 0000 would have to be equivalent
to -64 in order to be less than 0110 0000 (96) so that the loop could have
stopped.
Problem 3:
1) +---------+------------+-------------+
| Decimal | Binary | Hexidecimal |
+---------+------------+-------------+
| 0 | 0000 0000 | 00 |
+---------+------------+-------------+
| 10 | 0000 1010 | 0A |
+---------+------------+-------------+
| 16 | 0001 0000 | 10 |
+---------+------------+-------------+
| 127 | 0111 1111 | 7F |
+---------+------------+-------------+
| 128 |Not Possible| Not Possible|
+---------+------------+-------------+
| -128 | 1000 0000 | 80 |
+---------+------------+-------------+
| -127 | 1000 0001 | 81 |
+---------+------------+-------------+
| -16 | 1111 0000 | F0 |
+---------+------------+-------------+
| -10 | 1111 0110 | F6 |
+---------+------------+-------------+
2) +-------------+---------------------+---------+
| Hexidecimal | Binary | Decimal |
+-------------+---------------------+---------+
| FFFF | 1111 1111 1111 1111 | -1 |
+-------------+---------------------+---------+
| 8000 | 1000 0000 0000 0000 | -32,768 |
+-------------+---------------------+---------+
| 7FFF | 0111 1111 1111 1111 | 32,767 |
+-------------+---------------------+---------+
| 1111 | 0001 0001 0001 0001 | 4369 |
+-------------+---------------------+---------+
| 1000 | 0001 0000 0000 0000 | 4096 |
+-------------+---------------------+---------+
Problem 3 Question 3
3.
Any positive binary representation of the number one will be represented with
the least significant digit as one, and all of the digits to the left of it
as 0. This is true regardless of the number of bits in the binary
representation, because any other pattern of bits would change the number's
value.
In any "complement" number system that flips the bits of a binary
number, this pattern is reversed and the least significant bit is represented
as 0, while all of the padding digits to the left of it are represented as 1,
regardless of the number of bits in the representation.
The definition of the two's complement system tells us to take this process
one step further and add one to the number that results from flipping the
bits in order to make a number negative.
Since the least significant bit of binary 1 when flipped is always 0,
and 0 plus 1 is always 1, then the least significant bit of binary 1 is always
1. Concatenated with an arbitrary number of padding digits, which we have
shown above will all always be represented as 1,the result is a number
(-1) whose every digit will always be 1, regardless of its length.
