Hệ quản trị cơ sở dữ liệu - Chương 3:Biểu diễn dữ liệu trong máy tính

Nội dung text: Hệ quản trị cơ sở dữ liệu - Chương 3:Biểu diễn dữ liệu trong máy tính

1. ĐẠI HỌC DUY TÂN KHOA ĐIỆN TỬ VIỄN THÔNG CHƯƠNG 3 BIỂU DIỄN DỮ LIỆU TRONG MÁY TÍNH Nguyễn Văn Thọ Khoa Điện tử viễn thông Đại học Duy Tân – 2010 Nguyen Van Tho – Duy Tan University. Làm thế nào để biểu diễn trữ dữ liệu trong máy tính ? • Ở cấp thấp nhất, máy tính là 1 thiết bị điện tử • Hoạt động bằng cách điều khiển các dòng điện tử • works by controlling the flow of electrons • Có 2 trạng thái 1. Có điện áp : gọi là trạng thái ‘1” 2. Không có điện áp : gọi là trạng thái “0” • Có thế xác định trạng thái “0” hay “1” dựa vào giá trị điện áp
2. Nguyen Van Tho – Duy Tan University. Máy tính là một hệ thống số. Digital system: Binary (base two) system: • finite number of symbols • has two states: 0 and 1 • Đơn vị cơ sở của thông tin là số nhị phân (bit) • Tổ hợp nhiều bit sẽ cho nhiều trạng thái hơn • Tổ hợp của 2 bit cho ta 4 trạng thái : 00, 01, 10, 11 • Tổ hợp của 3 bit cho ta 8 trạng thái: 000, 001, 010, 011, 100, 101, 110, 111 • Tổ hợp của n bits cho ta 2n trạng thái. Nguyen Van Tho – Duy Tan University. Các loại dữ liệu cần biểu diễn? • Numbers – signed, unsigned, integers, floating point, complex, rational, irrational, • Text – characters, strings, • Images – pixels, colors, shapes, • Sound • Logical – true, false • Instructions • • Data type: • representation and operations within the computer • We’ll start with numbers
3. Nguyen Van Tho – Duy Tan University. Unsigned Integers (Số nguyên không dấu) • Trọng số của vị trí • Vídụ ký hiệu “329”trong hệ thập phân • “3” có gía trị là 300 trong khi “9” chỉ là 9 most least 329 significant 101 significant 102 101 100 22 21 20 3x100 + 2x10 + 9x1 = 329 1x4 + 0x2 + 1x1 = 5 Nguyen Van Tho – Duy Tan University. Unsigned Integers (cont.) • Một số n-bit kiểu unsigned integer có thể biểu diễn 2n giá trị : từ 0to 2n-1. 22 21 20 0 0 0 0 0 0 1 1 0 1 0 2 0 1 1 3 1 0 0 4 1 0 1 5 1 1 0 6 1 1 1 7
4. Nguyen Van Tho – Duy Tan University. Unsigned Binary Arithmetic • Base-2 addition – just like base-10! • add from right to left, propagating carry carry 10010 10010 1111 + 1001 + 1011 +1 11011 11101 10000 10111 + 111 Subtraction, multiplication, division, Nguyen Van Tho – Duy Tan University. Signed Integers (Số nguyên có dấu) • Với n bits, ta có 2n giá trị . • Sử dụng 1 nửa cho số dương (1 through 2n-1) và 1 nửa cho số âm (- 2n-1 through -1) • that leaves two values: one for 0, and one extra • Số nguyên dương • Bit MSB là bit 0 00101 = 5 • Số nguyên âm • Kiểu dấu-độ lớn : bít dấu =1 để biểu diễn số âm, độ lớn biểu diễn như số không dấu 10101 = -5 • Số bù 1 – flip every bit to represent negative 11010 = -5 • Trong cả 2 trường hợp , MSB biễu diễn dấu: 0=dương, 1=âm
5. Nguyen Van Tho – Duy Tan University. Số bù 2 • Hạn chế của 2 cách biểu diễn trên • Có 2 cách biểu diễn số 0 (+0 and –0) • Mạch tính toán phức tạp ¾ Làm thế nào để công 1 số có dấu và 1 số không dấu ? – Ví dụ : 2 + (-3) • Biểu diễn bằng số bù 2 giúp phát triển mạch số học dễ dàng hơn. • Với mỗi số dương (X) , chỉ có 1 giá trị âm (-X) thoã mãn X+ (-X) =0 với phép cộng bình thường (bỏ qua bit nhớ ngoài) 00101 (5) 01001 (9) + 11011 (-5) + (-9) 00000 (0) 00000 (0) Nguyen Van Tho – Duy Tan University. Biểu diễn số bù 2 • Nếu là số nguyên dương hoặc số 0 • Biểu diễn số nhị phân bình thường • Nếu là số âm • Bắt đầu với số dương tương ứng • Tính số bù 1 của số dương tương ứng (đảo bit) • Số bù 2 = Số bù 1 + 1 00101 (5) 01001 (9) 11010 (1’s comp) (1’s comp) +1 +1 11011 (-5) (-9)
6. Nguyen Van Tho – Duy Tan University. Two’s Complement Shortcut • To take the two’s complement of a number: • copy bits from right to left until (and including) the first “1” • flip remaining bits to the left 011010000 011010000 100101111 (1’s comp) (flip) (copy) +1 100110000 100110000 Nguyen Van Tho – Duy Tan University. Two’s Complement Signed Integers • MSB là bit dấu–nócótrọng số là –2n-1. • Phạm vi biểu diễn của số n-bit là : -2n-1 tới 2n-1 –1. • The most negative number (-2n-1) has no positive counterpart. -23 22 21 20 -23 22 21 20 0 0 0 0 0 1 0 0 0 -8 0 0 0 1 1 1 0 0 1 -7 0 0 1 0 2 1 0 1 0 -6 0 0 1 1 3 1 0 1 1 -5 0 1 0 0 4 1 1 0 0 -4 0 1 0 1 5 1 1 0 1 -3 0 1 1 0 6 1 1 1 0 -2 0 1 1 1 7 1 1 1 1 -1
7. Nguyen Van Tho – Duy Tan University. Chuyển đổi từ hệ 2 (Binary) sang hệ 10 (Decimal) 1. If leading bit is one, take two’s complement to get a positive number. 2. Add powers of 2 that have “1” in the n 2n corresponding bit positions. 0 1 1 2 3. If original number was negative, 2 4 add a minus sign. 3 8 4 16 5 32 X = 01101000two 6 64 6 5 3 7 128 =2+2 +2 = 64+32+8 8 256 = 104ten 9 512 10 1024 Assuming 8-bit 2’s complement numbers. Nguyen Van Tho – Duy Tan University. More Examples X = 00100111two =25+22+21+20 = 32+4+2+1 n 2n =39 0 1 ten 1 2 2 4 X = 11100110 3 8 two 4 16 -X = 00011010 5 32 =24+23+21 = 16+8+2 6 64 7 128 =26ten 8 256 X = -26 9 512 ten 10 1024 Assuming 8-bit 2’s complement numbers.
8. Nguyen Van Tho – Duy Tan University. Chuyển đổi từ hệ 10 sang hệ 2 • First Method: Division 1. Find magnitude of decimal number. (Always positive.) 2. Divide by two – remainder is least significant bit. 3. Keep dividing by two until answer is zero, writing remainders from right to left. 4. Append a zero as the MS bit; if original number was negative, take two’s complement. X = 104ten 104/2 = 52 r0 bit 0 52/2 = 26 r0 bit 1 26/2 = 13 r0 bit 2 13/2 = 6 r1 bit 3 6/2 = 3 r0 bit 4 3/2 = 1 r1 bit 5 X = 01101000two 1/2 = 0 r1 bit 6 Nguyen Van Tho – Duy Tan University. Chuyển đổi từ hệ 10 sang hệ 2 n 2n • Second Method: Subtract Powers of Two 0 1 1. Find magnitude of decimal number. 1 2 2 4 2. Subtract largest power of two 3 8 less than or equal to number. 4 16 5 32 3. Put a one in the corresponding bit position. 6 64 4. Keep subtracting until result is zero. 7 128 8 256 5. Append a zero as MS bit; 9 512 if original was negative, take two’s complement. 10 1024 X = 104ten 104 - 64 = 40 bit 6 40 - 32 = 8 bit 5 8 - 8 = 0 bit 3 X = 01101000two
9. Nguyen Van Tho – Duy Tan University. Phép toán: Số học và Logic • Recall: a data type includes representation and operations. • We now have a good representation for signed integers, so let’s look at some arithmetic operations: • Addition • Subtraction • Sign Extension • We’ll also look at overflow conditions for addition. • Multiplication, division, etc., can be built from these basic operations. • Logical operations are also useful: • AND • OR • NOT Nguyen Van Tho – Duy Tan University. Phép cộng • As we’ve discussed, 2’s comp. addition is just binary addition. • assume all integers have the same number of bits • ignore carry out • for now, assume that sum fits in n-bit 2’s comp. representation 01101000 (104) 11110110 (-10) + 11110000 (-16) + (-9) 01011000 (98) (-19) Assuming 8-bit 2’s complement numbers.
10. Nguyen Van Tho – Duy Tan University. Phép trừ • Negate subtrahend (2nd no.) and add. • assume all integers have the same number of bits • ignore carry out • for now, assume that difference fits in n-bit 2’s comp. representation 01101000 (104) 11110110 (-10) - 00010000 (16) - (-9) 01101000 (104) 11110110 (-10) + 11110000 (-16) + (9) 01011000 (88) (-1) Assuming 8-bit 2’s complement numbers. Nguyen Van Tho – Duy Tan University. Chú ý với số có dấu • Để cộng 2 số, ta phải biểu diễn số đó dưới dạng các số nhị phân có số bit như nhau. • Thêm 0 vào bên trái để đủ số bit 4-bit 8-bit 0100 (4) 00000100 (still 4) 1100 (-4) 00001100 (12, not -4) • Instead, replicate the MS bit the sign bit: 4-bit 8-bit 0100 (4) 00000100 (still 4) 1100 (-4) 11111100 (still -4)
11. Nguyen Van Tho – Duy Tan University. Tràn số • Nếu 2 toán hạng quá lớn, kết quả phép toán không chính xác. 01000 (8) 11000 (-8) + 01001 (9) + 10111 (-9) 10001 (-15) 01111 (+15) • Tràn số xảy ra nếu • Dấu của 2 toán hạng giống nhau và • Dấu của kết quả khác dấu 2 toán hạng. Nguyen Van Tho – Duy Tan University. Logical Operations • Operations on logical TRUE or FALSE • two states takes one bit to represent: TRUE=1, FALSE=0 A B A AND B A B A OR B A NOT A 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 • View n-bit number as a collection of n logical values • operation applied to each bit independently
12. Nguyen Van Tho – Duy Tan University. Examples of Logical Operations • AND 11000101 • useful for clearing bits AND 00001111 ¾AND with zero = 0 ¾AND with one = no change 00000101 • OR 11000101 • useful for setting bits ¾OR with zero = no change OR 00001111 ¾OR with one = 1 11001111 • NOT NOT • unary operation one argument 11000101 • flips every bit 00111010 Nguyen Van Tho – Duy Tan University. Hexadecimal Notation • It is often convenient to write binary (base-2) numbers as hexadecimal (base-16) numbers instead. • fewer digits four bits per hex digit • less error prone easy to corrupt long string of 1’s and 0’s Binary Hex Decimal Binary Hex Decimal 0000 0 0 1000 8 8 0001 1 1 1001 9 9 0010 2 2 1010 A 10 0011 3 3 1011 B 11 0100 4 4 1100 C 12 0101 5 5 1101 D 13 0110 6 6 1110 E 14 0111 7 7 1111 F 15
13. Nguyen Van Tho – Duy Tan University. Converting from Binary to Hexadecimal • Every four bits is a hex digit. • start grouping from right-hand side 011101010001111010011010111 3 A 8 F 4 D 7 This is not a new machine representation, just a convenient way to write the number. Nguyen Van Tho – Duy Tan University. Số thập phân : Dấu chấm tĩnh (Fixed-Point) • Làm thế nào để biễu diễn số thập phân? • Use a “binary point” to separate positive from negative powers of two just like “decimal point.” • 2’s comp addition and subtraction still work. ¾if binary points are aligned 2-1 = 0.5 2-2 = 0.25 2-3 = 0.125 00101000.101 (40.625) + 11111110.110 (-1.25) 00100111.011 (39.375) No new operations same as integer arithmetic.
14. Nguyen Van Tho – Duy Tan University. Số rất lớn và số rất nhỏ : Dấu chấm động (Floating-Point) • Giá trị lớn : 6.023 x 1023 cần 79 bits • Giá trị nhỏ : 6.626 x 10-34 cần >110 bits • Đưa về dạng biểu diễn : F x 2E • IEEE 754 Floating-Point ¾ Độ chính xác đơn : Single-precision (32-bits) ¾ Độ chính xác kép : Double-precision (64-bits) Nguyen Van Tho – Duy Tan University. Dấu chấm động • IEEE-754 format cho độ chính xác đơn (single-precision) 31 30 23 22 0 S biased exponent e fraction f of normalized mantissa 1 sign bit: 0 dương, 1 âm 8 bit biased exponent= exponent + 127 24 bit mantissa chuẩn hoá = 1 bit ẩn + 23 bit fraction Chuẩn hoá định trị :cógiátrị giữa 1 và 2 : 1.f N = (−1)S ×1.fraction × 2exponent−127, 1≤ exponent ≤ 254 N = (−1)S × 0.fraction × 2−126, exponent = 0
15. Nguyen Van Tho – Duy Tan University. Floating Point Example • Single-precision IEEE floating point number: • 10111111010000000000000000000000 sign exponent fraction • Sign is 1 – number is negative. • Exponent field is 01111110 = 126 (decimal). • Fraction is 0.100000000000 = 0.5 (decimal). • Value = -1.5 x 2(126-127) = -1.5 x 2-1 = -0.75. Ví dụ: biểu diễn 0.1011 dưới dạng IEEE-754 Sign bit s=0 chuẩn hoá : 0.1011=1.011*2-1 exponent: -1 + 127=126=01111110 IEEE format: 0 01111110 0110000000000000000000 Nguyen Van Tho – Duy Tan University. Dấu chấm động • IEEE-754 format cho độ chính xác kép (double-precision) 63 62 52 51 0 S biased exponent e fraction f of normalized mantissa 1 sign bit: 0 dương, 1 âm 11 bit biased exponent= exponent + 1023 53 bit mantissa chuẩn hoá = 1 bit ẩn + 52 bit fraction s e-127 single precision: (-1) x 2 x (1.f)2 s e-1023 double precision: (-1) x 2 x (1.f)2
16. Nguyen Van Tho – Duy Tan University. Text: ASCII Characters • ASCII: Maps 128 characters to 7-bit code. • both printable and non-printable (ESC, DEL, ) characters 00 nul 10 dle 20 sp 30 0 40 @ 50 P 60 ` 70 p 01 soh 11 dc1 21 ! 31 1 41 A 51 Q 61 a 71 q 02 stx 12 dc2 22 " 32 2 42 B 52 R 62 b 72 r 03 etx 13 dc3 23 # 33 3 43 C 53 S 63 c 73 s 04 eot 14 dc4 24 $ 34 4 44 D 54 T 64 d 74 t 05 enq 15 nak 25 % 35 5 45 E 55 U 65 e 75 u 06 ack 16 syn 26 & 36 6 46 F 56 V 66 f 76 v 07 bel 17 etb 27 ' 37 7 47 G 57 W 67 g 77 w 08 bs 18 can 28 ( 38 8 48 H 58 X 68 h 78 x 09 ht 19 em 29 ) 39 9 49 I 59 Y 69 i 79 y 0a nl 1a sub 2a * 3a : 4a J 5a Z 6a j 7a z 0b vt 1b esc 2b + 3b ; 4b K 5b [ 6b k 7b { 0c np 1c fs 2c , 3c 4e N 5e ^ 6e n 7e ~ 0f si 1f us 2f / 3f ? 4f O 5f _ 6f o 7f del Nguyen Van Tho – Duy Tan University. Interesting Properties of ASCII Code • What is relationship between a decimal digit ('0', '1', ) and its ASCII code? • What is the difference between an upper-case letter ('A', 'B', ) and its lower-case equivalent ('a', 'b', )? • Given two ASCII characters, how do we tell which comes first in alphabetical order? • Are 128 characters enough? ( No new operations integer arithmetic and logic.
17. Nguyen Van Tho – Duy Tan University. Other Data Types • Text strings • sequence of characters, terminated with NULL (0) • typically, no hardware support • Image • array of pixels ¾monochrome: one bit (1/0 = black/white) ¾color: red, green, blue (RGB) components (e.g., 8 bits each) ¾other properties: transparency • hardware support: ¾typically none, in general-purpose processors ¾MMX multiple 8-bit operations on 32-bit word • Sound • sequence of fixed-point numbers Nguyen Van Tho – Duy Tan University.