Question Source
2017W2/slides/RepresentingValues-4up.pdf
2018S/slides/121-04-number-rep-ckh4up.pdf
Q1 module formula proof
examples:
3 ≡ 7 (mod 2) is true since 3 / 2 = 1 ... 1 and 7 / 2 = 1 ... 1
9 ≡ 99 (mod 10) is true since 9 / 10 = 0 ... 9 and 99 / 10 = 9... 9
11999 ≡ 1 (mod 10) is true since 11999 / 10 = ? ... 1 and 1 / 10 = 0... 1
If a ≡ b mod m and c ≡ d mod m, then, proof
(1) ac ≡ bd mod m
a ≡ b mod m -> a = b + mq (q is Integer)
c ≡ d mod m -> c = d + mr (r is Integer)
then,
(a+c) – (b+d)
=((b + mq) + (d + mr)) – (b+d)
=(b + d + mq + mr) - b – d
=mq + mr
=m(q + r) , a multiple
∴ (a + c) ≡ (b+d) (mod m)
(2) a+c ≡ (b+d) mod m
a ≡ b mod m -> a = b + mq (q is some Integer)
c ≡ d mod m -> c = d + mr (r is some Integer)
then,
ac – bd
=(b + qm) ( d + rm) – bd
=bd + brm + qmd +qrm – bd
=m(br + qd + qrm)
Divisible by m,
so ac ≡ bd (mod m)
-
Q2 clock problem
Imagine the time is currently 15:00(3:00PM, that is). How can you quickly answer the following two questions without using a calculator:
(1)What time was it 8 * 21 hours ago?
(2)What time will it be 13 * 23 hours from now?
In arithmetic modulo, we seek to express any x = qc+r, where r must be a non-negative integer.
for example −100 mod 8=4. This is because −100 = 8 x (−13) + 4. The remainder is 4. so,
−3 mod 24= 21, since -3 = 24 x (-1) + 21.
−1 mod 24= 23, since -1 = 24 x (-1) + 23.
And also, 21 mod 24 = 21.
(1)
So, -3 ≡ 21 (mod 24) (check question 1 for the meaning of (a ≡ b mod m))
15 - 8 * 21 ≡ 15 - 8 * (-3) = 15 + 24 = 39 ≡ 15
(2)
15 + 13 * 23 ≡ 15 + 13 * (-1) = 15 - 13 = 2
-
Q3 binary number
convert 729 to binary.
729 / 2 result 364 remainder 1 b0
364 / 2 result 182 remainder 0 b1
182 / 2 result 91 remainder 0 b2
91 / 2 result 45 remainder 1 b3
45 / 2 result 22 remainder 1 b4
22 / 2 result 11 remainder 0 b5
11 / 2 result 5 remainder 1 b6
5 / 2 result 2 remainder 1 b7
2 / 2 result 1 remainder 0 b8
1 / 2 result 0 remainder 1 b9
Read the remainders from bottom to top.
72910 = 10110110012
how about negative decimal numbers?
Any number can be treated as signed or unsigned.
If a number is treated as signed, then the highest bit indicates the sign. 1 = negative, 0 = positive
Let's use a three bits example
We can find out that for any positive integer X, the (-X) binary representation is equal to the (2n - X).
For example,
X = 1 , -x = -1 = 23 - 1 = 7(111) (111 is the -1 in above binary table)
If you think of module -1 ≡ 7 (mod 8) is true since -1 / 8 = 1 ... 7 and 7 / 8 = 1 ... 7
Y = 2n - X, where Y has the same binary representation as -X
-
Q4 two's complement
Based on the rule Y = 2n - X, where Y has the same binary representation as -X
There is a method called two's complement for calculating the -X in binary by given positive X in decimal
The purpose of two's complement is to make the transfer easier(just flip and add 1).
Lets use -1 as an example
Step 1: convert 1 to binary 001
Step 2: Flip bits from 0 to 1 and from 1 to 0 110 (2^3 - 1 - 1 = 6, as the above formula shows)
Step 3: add 1 to the value 111
001(1) + 111(-1) = 1000, as there only 3 bits, 1000 is just 000, so 001(1) + 111(-1) = 000(0)
-
Q5 signed binary to decimal
Proof:
Based on the rule Y = 2n - X, where Y has the same binary representation as -X form Q3 to prove.
Y = 2n - X -> -X = Y - 2n
Assume Y is in binary form (bn−1 bn−2 ... b2 b1 b0) in a n bits binary system
-X = Y - 2n =(bn−1 x 2n-1 + bn−2 x 2n-1+ ... b1 x 21 + b0) - 2n
since it is a negative number bn−1 is 1
(bn−1 x 2n-1 + bn−2 x 2n-2+ ... b1 x 21 + b0) - 2n
=(2n-1 + bn−2 x 2n-2+ ... b1 x 21 + b0) - 2n
=(2n-1 - 2n) + (bn−2 x 2n-2+ ... b1 x 21 + b0)
;;2n-1 - 2n = 1 x 2n-1 - 2 x 2n-1 = - 2n-1
=- 2n-1 + (bn−2 x 2n-2+ ... b1 x 21 + b0)
;; - 2n-1 = - 1 x bn−1 = - bn−1 x 2n-1
=- bn−1 x 2n-1 + (bn−2 x 2n-2+ ... b1 x 21 + b0)
proved
How to use? below is an example
-
Q6 binary representing Character
How do computers represent characters?
People map specific character to specific binary values.
ASCII: American Standard Code for Information
Interchange 7-bit per character, sufficient for upper/lowercase, digits, punctuation and a few special characters.
UNICODE:
16+ bits, extended ASCII for languages other than English
What does the 8-bit binary value 11111000 represent?
a) -8
b) The character “ø”
c) 248
d) More than one of the above
e) None of the above.
11111000 (check Q3 for binary ↔ decimal translation)
8 bit unsigned: 248
8 bit signed: -8
8 bit in UNICODE is “ø” since 248 in UNICODE represents LATIN SMALL LETTER O WITH STROKE
Every thing for computer is binary, what it represents depends on how we interpret the information.
-
Q7 binary representing Real numbers
Binary -> Floating-Point
Floating-Point -> Binary
How does 0.1 represent in this form 0.000110011001100110011...?
1.Multiply by two
2.take decimal as the digit
3.take the fraction as the starting point for the next step
4.repeat until you either get to 0 or a periodic number
5.read the number starting from the top - the first result is the first digit after the comma
0.1 * 2 = 0.2 -> 0
0.2 * 2 = 0.4 -> 0
0.4 * 2 = 0.8 -> 0
0.8 * 2 = 1.6 -> 1
0.6 * 2 = 1.2 -> 1
0.2 * 2 = 0.4 -> 0
0.4 * 2 = 0.8 -> 0
0.8 * 2 = 1.6 -> 1
0.6 * 2 = 1.2 -> 1
Result: 0.00011(0011) periodic.
For a full step check this video
-
Q8 Hexdecimal
Binary numbers tend to be very long and cumbersome.
Hexadecimal numbers are often used to abbreviate binary numbers.
The hexadecimal number system has 16 digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F.
The letters A, B, C, D, E, and F correspond to the decimal numbers 10, 11, 12, 13, 14, and 15.
