ssd6-lecture4

Size: px

Start display at page:

Download "ssd6-lecture4"

默抛梁
5 years ago
Views:

1 SSD 6 4 Representation of Data

2 Representation of Data The Contents in icarnegie cover: 2.1 Bits and Bit Manipulation 2.2 Integers 2. Floating-Point Numbers 2.4 Structured Data

3 Representation of Data We will talk about: Numbering System Alphanumeric Expression Structured Data in Memory Logic Operation

4 Numbering System 十进制(Decimal)数字系统二进制(Binary)数字系统十六进制(Hexadecimal)数字系统

5 Numbering System 十进制(Decimal)数字系统以 0, 1, 2,, 4, 5, 6, 7, 8, 9 等十个不同符号(symbol)组成人类使用的数字系统: 人有十根指头超过九的数目就必须用多位数元(digits)表示如 : 9+1=10, 99+1=100

6 Numbering System 十进制(Decimal)数字系统以10为基底的数字系统(Base 10 number system) 不同位置数元代表不同的数量(quantity) 小数点左边第一位为 1, 第二位为10, 每个位置所代表的数量为其右边位置所代表的数量之10倍

7 Numbering System 十进制(Decimal)数字系统

8 Numbering System 二进制(Binary)数字系统以 0, 1 两个符号组成数字计算器使用的数字系统:电子开关(晶体管) 有两种状态(ON:1, OFF:0) 超过一的数目就必须用多位数元(digits)表示如 : 1+1=102, 11+1=1002 binary digit (二进制数元) 简称 bit (位)

9 Numbering System 二进制(Binary)数字系统以2为基底的数字系统(Base 2 number system) 不同位置数元代表不同的数量(quantity) 小数点左边第一位为 1, 第二位为2, 每个位置所代表的数量为其右边位置所代表的数量之2倍

10 Numbering System 二进制(Binary)数字系统

11 Numbering System 十六进制(Hexadecimal)数字系统以 0, 1, 2,, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F 等十六个符号组成符号A~F 代表10~15 超过十五的数目就必须用多位数元(digits)表示如 : F+1=1016, FF+1=10016

12 Numbering System 为何要谈十六进制数字系统 8个字节成一个字 (byte), 可表现256(28)种不同0/1组合可用十六进制法精简表示一个字的内容下图之内容以二进制表示为 ,以十六进制表示法为B216 B 2

13 Numbering System 十六进制(Hexadecimal)数字系统以16为基底的数字系统(Base 16 number system) 不同位置数元代表不同的数量(quantity) 小数点左边第一位为 1, 第二位为16, 每个位置所代表的数量为其右边位置所代表的数量之 16倍 1 F 5.4 C

14 Words & Virtual Address Space

15 Numbering System 十六进制(Hexadecimal)数字系统 1 F 5.4 C

16 Alphanumeric Data Expre. 字符型 (Alphanumeric)数字表示法 ASCII code EBCDIC code Unicode GB code BIG-5 code

17 Alphanumeric Data Expre. ASCII code American Standard Code for Information Interchange 目前最多计算机使用标准ASCII code使用7位来表示128(27)字符集编号 0~1, 127: 控制字符编号 2~64: 特殊字符(!,, #, $,..)及数字字符(0, 1, 9) 编号 65~90: 大写字母编号 97~122: 小写字母

18 Alphanumeric Data Expre. ASCII code table (7 bits) 例如 : A 的编号为 65: (4116) A

19 Alphanumeric Data Expre. 8 位 ASCII code 共256(28)个不同符号前128字符(编号0~127)为标准ASCII code, 利用编号 128~255描述各种不同字符集例如国际标准组织(ISO)制定标准(ISO )来表示西欧语言字母

20 Alphanumeric Data Expre. ASCII code 单词 Pen 需用三个字节表示内容若用十六进制表示为: E 每个字符均有一对应内码(编码), 计算机语言中常会对两字符比大小,此时是利用内码值相比右式会成立 : A < B, D < d

21 Alphanumeric Data Expre. EBCDIC code Extended Binary Code Decimal Interchange Code IBM公司制定目前IBM大型主机仍使用用8个位定义256种符号与一般计算机交换信息时需执行转码步骤 Pen 若以EBCDIC Code 表示为: D

22 Alphanumeric Data Expre. Unicode 1990后发展与推动的国际通用编码标准用2个字节定义符号, 最多可表示6556(216)个符号包含多个国家文字(汉语亦包括在内) Windows NT 及 2000 已支援Unicode 前256码与ASCII 相同 Pen 若以Unicode Code 表示为: E How to represent a Chinese word?

23 Alphanumeric Data Expre. 中文码简体字最常用为GB码繁体字最常用为BIG-5码 Unicode 汉字集(20902字)

带正负号表示法(Signed Integer) Java 1的补码表示法(1 s complement)

24 Numeric Data Expression 两个组合状态对应同一数值0 算术运算很难处理数值(Numeric)资料表示法整数表示法不带正负号表示法(Unsigned Integer) 带正负号表示法(Signed Integer) Java 1的补码表示法(1 s complement) supports only signed 2的补码表示法(2 s complement) numbers 浮点数(实数)表示法

25 Numeric Data Expression Sizes (in Bytes) of C Numeric Data Types. The number of bytes allocated varies with machine and compiler.

26 Numeric Data Expression Byte Representations of Different Data Values. Results for int and float are identical, except for byte ordering. Pointer values are machine-dependent.

27 Numeric Data Expression If we expand these hexadecimal patterns into binary and shift them appropriately, we find a sequence of 1 matching bits, indicated above by a box.

28 不带正负号表示法(Unsigned Integer) 直接将数值以二进制值表示放入位中若用n个位来表示一数则范围是0 ~ 2n-1 右图是以八位表示 unsigned Integer value n bits

29 Unsigned Addition

30 Unsigned (4-bit word) Addition

31 带正负号表示法(Signed Integer) 以最前面一位表示正负号(+:0, -:1) 将数值以二进制值表示放入其余位中若用n个位来表示一数则范围是+2n-1-1 ~ -(2n-1-1) s value n bits

32 带正负号表示法(Signed Integer) 右图是以八位表示signed Integer 注意:有+0, -0 s value n bits

33 Why need complement? 为了简化电路的设计可将减法运算转换成加法及补码 complement 运算来取代如 X-Y =X+(-Y) =X+(Y的補數)

34 Why need complement? 补码是一种表示负数的方式对每一 k 进位制的数字系统而言其补码有两种 1. k 的补码又称基数补码: radix complement 2. k-1 的补码又称基数减一补码: radix minus one complement

35 1的补码表示法(1 s complement)[或二进制反码] 1的补码运算(逐位not运算) 二进制数值中每一位分别作not运算(1->0, 0->1) 如对1101 执行 not 运算结果是的补码运算 0010

36 1的补码表示法(1 s complement) 正数最前面一位为 0 将数值以二进制值表示直接放入其余位中如用16位表示 +5 為 (000516)

37 1的补码表示法(1 s complement) 负数最前面一位为 1 将数值之正数以二进制值表示,对其执行1的补码运算后,再将结果放入其余位中

38 1的补码表示法(1 s complement) 范例: 用16位表示 -5 为 FFFA -5 < (15 bits) 1的补码运算 (16 bits)

39 1的补码表示法(1 s complement) 右图是以八位表示 1 s complement integer 注意:有+0, -0 若用n个位来表示一数则范围是 +2n-1-1 ~ -(2n-1-1)

40 2的补码表示法(2 s complement)[现代计算机用] 2的补码运算二进制数值中每一位分别作not运算后再加1(溢位忽略) 如0010 的2的补码是 1110 口诀: 2的补码=1的补码的补码 2的补码运算运算

41 2的补码表示法(2 s complement) 正數最前面一位为 0 将数值以二进制值表示放入其余位中与正数以1的补码表示法相同如用16位表示+5为 (000516)

42 2的补码表示法(2 s complement) 负数最前面一位为 1 将数值之正数以二进制值表示,对其执行2的补码运算后,再将结果放入其余位中

43 2的补码表示法(2 s complement) 范例:用16位表示 -5 为 FFFB -5 < (15 bits) 2的补码运算 (16 bits)

44 2的补码表示法(2 s complement) 右图是以八位表示 2 s complement integer 注意:没有+0, -0 若用n个位来表示一数则范围是 +2n-1-1 ~ -2n-1

45 You will also find: K s Complement 补码加法 (k 或 k-1 的补码) 有进位(正数) k 的补码? Ye s 去掉进位 No 进位加到右边进位? 无进位(负数) k 的补码? Ye s k 的补码 No k-1 的补码加上负号

46 １的补码的特点计算容易只需将０１１０即可有正零与负零两种表示法容易混淆以4bit为例 0000为正零 1111为负零利用１的补码执行减法运算时进位需做加法处理

47 2的补码的特点零的表示法只有一种范围较１的补码大计算２的补码的过程比计算１的补码复杂现代计算机使用

48 补码的性质范例: 对做2的补码运算, 对结果再做2的补码运算以八位之2的补码表示法是上式之2的补码运算结果是上式之2的补码运算结果是 (-) => +

49 范例: 1的补码表示法是代表何值? 第一位是1代表其值为负其余位需执行1的补码运算,以求其正值对执行1的补码运算之结果为 (2110) 因为1的补码运算结果是+21, 所以原式是代表 -21

50 范例: 2的补码表示法是代表何值? 第一位是1代表负值其余位需执行2的补码运算,以求其正值之2的补码运算(1的补码+1)结果为 (12810) 因为运算结果是+128 所以原式是代表 128 用八位的2的补码表示法范围 128 ~ +127

51 范例: 执行2的补码表示法结果为何? 执行2的补码运算(1的补码+1)得到忽略溢位(只有八个位)则得 (010) 由此亦可验证2的补码表示法并沒有+0, -0 之分

52 Conversation from 2 s complement to Unsigned

53 Conversation from Unsigned to 2 s complement

54 2 s complement negation

55 浮点数(实数)表示法 [previous] Fixed-Point Representations Some of the bits represent a fractional part-just as we use digits to the right of the decimal point to denote the fractional part of a number Each sample of digital audio is a 16-bit, fixedpoint binary number representing a fraction between -1 and +1

56 Positive side on Fix-Point formats: Allow fractions to be represented to any desired precision Negative side Precision lost in computations Worse, the problem is that in many computations the magnitudes vary widely: If you keep the decimal point in a fixed location, then any time you divide or multiply by a value that is not close to one, you will risk either overflow because the number becomes too large, or a loss of precision, because the number becomes too small

57 浮点数(实数)表示法 [at present] 克服以上缺点可表示有小数点之数值(fractional ) 表示的范围很大,但精度(有效位数)有限制不同计算机内使用的浮点数格式可能,视CPU设计而定考虑精确性多于考虑速度和效率

浮点数(实数)表示法 [examples] Decimal Binary 5 10 20 40 80

Floating-Point Exponent Mantissa 11.10100000 100.

58 浮点数(实数)表示法 [examples] Decimal Binary Floating-Point Exponent Mantissa

59 浮点数(实数)表示法原理[principles] The left-most bit of the mantissa is always one By keeping the mantissa shifted as far left as possible, it will always have the most room to the right and, therefore, the most precision Floating-point numbers are usually approximations, so we want to shift the mantissa left (and adjust the exponent accordingly) as much as possible. To skip the left most 1 makes room for one more bit of precision

60 Intel x86 CPU三种浮点数格式 IEEE规格(Institute of Electrical and Electronics Engineers) 单精度(Single Precision)格式 4 字节双精度(Double Precision)格式 8 字节扩展双精度(Extended Double Precision)格式 10 字节

61 IEEE 4 bytes浮点数格式组成及概念正负号(Sign)(b1) + : 0, - : 1 指数(Exponent)(b0...b2) 资料表示法 :unsigned 指数次方值(Pe) : powered by 2 指数偏差值(bias):127 底数(Mantissa) (b22 b0 ) 数值正规化假想小数点 : 1.

62 IEEE 4 bytes浮点数格式:指数部分(exponent) 长度:8个位资料表示法不带正负号整数(0~255) 指数次方值 (Pe) 指数是2的次方倍指数偏差值(bias) 以127为偏差值,所以真正的指数值是 -127 ~ +128

63 IEEE 4 bytes浮点数格式:底数部分(mantissa) 长度:2个位数值基底(Bm) :Base 2 数值正规化假想小数点 : 1.

64 正规化(Normalization) 用底数及指数方式表示一个实数并不唯一如限定小数点出现的位置则称正规化 IEEE 限定小数点出现在第一个1之后 0 的浮点数表示法为特例: 2 位元均為 0

65 -1^Sign * 2^(Exponent-127) * (1 + Mantissa * 2^-2) Sign is either 0 or 1. Exponent determines the general magnitude of the floating-point number To represent small numbers, Exponent is biased by -127 So, 2^-127, is about In any case, it is a very small number Mantissa, a 2-bit unsigned value, ranges from 0 to 2^2-1. And (Mantissa * 2^-2) ranges from 0 to almost 1 Finally, floating-point value varies from 2^-127 (10^8) to 2^128 (10^8).

范例: IEEE 4 bytes浮点数 41 8D 00 00 代表何值 0100 0000 1000 1100

66 范例: IEEE 4 bytes浮点数 41 8D 代表何值 S E M

67 范例: -66.5以IEEE 4 bytes 的浮点数格式表示 S= 1 正规化 M = E =110 = S E M C

68 How to represent π? (Archimedes, 250 B.C. ) 0x40490FDB

A story on Floating Point numbers On February 25, 1991, during the GulfWar, an American PatriotMissile battery in Dharan, Saudi Arabia, failed to intercept an incoming Iraqi Scud missile.

69 A story on Floating Point numbers On February 25, 1991, during the GulfWar, an American PatriotMissile battery in Dharan, Saudi Arabia, failed to intercept an incoming Iraqi Scud missile. The Scud struck an American Army barracks and killed 28 soldiers. The U. S. General Accounting Office (GAO) conducted a detailed analysis of the failure and determined that the underlying cause was an imprecision in a numeric calculation.

70 A story on Floating Point numbers The Patriot system contains an internal clock, implemented as a counter that is incremented every 0.1 seconds. To determine the time in seconds, the program would multiply the value of this counter by a 24-bit quantity that was a fractional binary approximation to 1/10. In particular, the binary representation of 1/10 is the nonterminating sequence: [0011] where the portion in2 brackets is repeated indefinitely. The computer approximated 0.1 using just the leading bit plus the first 2 bits of this sequence to the right of the binary point. Let us call this number x.

71 A story on Floating Point numbers 1. What is the binary representation of x 0.1? 2. What is the approximate decimal value of x 0.1?. The clock starts at 0 when the system is first powered up and keeps counting up from there. In this case, the system had been running for around 100 hours. What was the difference between the time computed by the software and the actual time?

72 A story on Floating Point numbers

73 How to represent 0? Zero is represented by an exponent of zero ("0") and a mantissa of zero ("0"). Sign bit can be either "0" or "1 : +0 and -0 Exponent 0? When the exponent is 0, the mantissa represents a number between 0 and 1 rather than between 1 and 2. These denormalized values are used when the magnitude is too small to be expressed by the exponent alone. Denormalized values can have magnitudes as small as 10^-45-but at reduced precision since some high-order bits of the mantissa will be zero.

74 Exponent An exponent of (binary) with a zero mantissa is used to represent plus or minus infinity, two special values that are reserved to indicate the result of an overflowing arithmetic operation. An Exponent of (binary) with a non-zero Mantissa denotes a special value called NaN (for "Nota-Number") for cases where a number cannot be determined, for example, the square root of -1.0.

75 DeNomornized Values Denormalized numbers serve two purposes First, they provide a way to represent numeric value 0, since with a normalized number we must always have M >= 1, and hence we cannot represent 0. With IEEE floating-point format, the values are +0 & -0 are considered different in some ways and the same in others. A second function of denormalized numbers is to represent numbers that are very close to 0.0.

76 Rounding Floating-point arithmetic can only approximate real arithmetic, since the representation has limited range and precision. Thus, for a value x, we generally want a systematic method of finding the closest matching value x that can be represented in the desired floatingpoint format.

77 Rounding (assuming a 2-bit int): From int to float, the number cannot overflow, but it may be rounded. From int or float to double, the exact numeric value can be preserved because double has both greater range (i.e., the range of representable values), as well as greater precision (i.e., the number of significant bits). From double to float, the value can overflow to + or -, since the range is smaller. Otherwise it may be rounded since the precision is smaller

78 Rounding (assuming a 2-bit int): From float or double to int the value will be truncated toward zero. For example will be converted to 1, while will be converted to -1. Note that this behavior is very different from rounding. Furthermore, the value may overflow. The C standard does not specify a fixed result for this case, but on most machines the result will either be TMaxw or TMinw, where w is the number of bits in an int. See double_number.dsw

79 A story on Rounding Converting large floating-point numbers to integers is a common source of programming errors. Such an error had particularly disastrous consequences for the maiden voyage of the Ariane 5 rocket, on June 4, Just 7 seconds after lift-off, the rocket veered off its flight path, broke up, and exploded. On board the rocket were communication satellites, valued at $500 million.

80 A story on Rounding A later investigation showed that the computer had sent invalid data to the computer controlling the engine nozzles. Instead of sending flight control information, it had sent a diagnostic bit pattern indicating that, in an effort to convert a 64-bit floating point number into a 16-bit signed integer, an overflow had been encountered. The value that overflowed measured the horizontal velocity of the rocket, which could be more than five times higher than that achieved by the earlier Ariane 4 rocket. In the design of the Ariane 4 software, they had carefully analyzed the numeric values and determined that the horizontal velocity would never overflow a 16-bit number. Unfortunately, they simply reused this part of the software in the Ariane 5 without checking the assumptions on which it had been based.

总结 Intel x86 CPU三种浮点数格式比较单精度双精度扩展双精度总字节数 2 64 80 底数字节数 2 52 6 有效位数 7

81 总结 Intel x86 CPU三种浮点数格式比较单精度双精度扩展双精度总字节数底数字节数有效位数指数字节数指数偏差值 ~ ~ ~10492 表示范围

82 Boolean Algebra From George Boole (1850), so as to Boolean Algebra Boolean Algebra(布尔代数) Boolean Variable(布尔变量): 0和1 true and false Logic operations AND, OR, XOR(Exclusive OR), NOT, etc.

83 Boolean Algebra Logic operation vs. propositional logic ~p Not p P&Q And PΛQ P Q Or PvQ P^Q Exclusive-Or PªQ

84 Boolean Algebra

85 Boolean Algebra Shared properties

86 Boolean Algebra Unique to RINGS Unique to Boolean algebras

87 Boolean Algebra AND(与):两数皆为1时结果为1 否则为 0 OR(或):两数有一为1时结果为1 否则为0 XOR(互斥):两数不相同时结果为1 否则为0 NOT(非): 1 s complement.

88 Bit-level operations in C

89 Bit-level operations in C void inplace_swap ( int *x, int *y) { *x = *x ^ *y; //step 1 *y = *x ^ *y; //step 2 *x = *x ^ *y; //step }

90 Logic Operation &&! >> << Logic operation treats any nonzero argument as representing TRUE and argument 0 as representing FALSE They return either 1 or 0, indicating a result either TRUE or FALSE 0x02 0xF7 0xFD 0x00 0x01 0x01 0x00 0x01 X=0x6 6 Y=0x9

91 Computing with floats Approximation Examples [2..2a] #include <iostream.h> #include <iomanip.h> using namespace std; void main() { float x = 1.2F; double y = x; cout << setprecision(20) << x << ", " << y << endl; cout << "1.2F == 1.2: " << (1.2F == 1.2) << endl; }

92 Computing with floats Equality Testing #include <iostream.h> #include <iomanip.h> using namespace std; void main() { double x = 1.; double y = 0.4; if (x + y!= 1.7) cout << "addition failed?" << endl; }

93 Computing with floats Losing Precision (An example) If we express the sum in four digits, we get We lost all but one digit of ! Rounded, that becomes But if we add the numbers one-at-atime, rounding after each addition, the result is 1.244, off by 0.004!

94 Strings and Arrays Preliminary Knowledge computer memory is organized as a sequence of 8-bit bytes Each byte has a unique integer address, and addresses are generally consecutive For efficiency, most processors can access more than one byte at a time in memory, for example, 4-bytes once

Strings and Arrays Arrays The compiler arranges array elements adjacent to one another in memory in increasing order C and C++ do not check whether an

95 Strings and Arrays Arrays The compiler arranges array elements adjacent to one another in memory in increasing order C and C++ do not check whether an array index is out of bounds For example, when an array is passed to a function as a parameter, the function receives the location, but not the size of the array

96 Strings and Arrays Accessing Arrays with Pointers C does not check array bounds, nor does it check that pointer arithmetic generates a legitimate pointer to data of the expected type Notice that when you add one to a pointer, you do not get a pointer to the next byte in memory. Instead, you get a pointer to the next element in memory-where "element" is whatever it is that the pointer points to

97 Strings and Arrays Strings Everything we have just learned about arrays applies to strings A string is an array of characters One important difference between strings and other arrays is that strings in C and C++ do have a length, by marking the end of a string with a zero. See 2..2b.sln

98 Strings Strings and Arrays

99 Strings and Arrays Records (structures)

bytes are simply "padding" to make the addresses come out right

100 Strings and Arrays Alignment Compiler is trying to place the 8-byte member d on a boundary that is a multiple of eight bytes The unused bytes are simply "padding" to make the addresses come out right Sizeof (mystruct) Align to the Maxinum 24is 8Component (here bytes) =

101 Strings and Arrays Alignment

102 Strings and Arrays Alignment with Microsoft Windows Microsoft Windows requires a stronger alignment requirement any k -byte (primitive) object must have an address that is a multiple of k. In particular, it requires that the address of a double be a multiple of 8. This requirement enhances the memory performance at the expense of some wasted space. The design decision made in Linux was probably good for the i86, back when memory was scarce and memory busses were only 4 bytes wide. With modern processors, Microsoft s alignment is a better design decision.

103 Next Time To be finished: All quizzes in Unit 1 Excise 1 Pre-Read: Memory Layout and Allocation.1 Several Uses of Memory.2 Memory Bugs

104 In the Lab Finish Excise 1: Do: Excise 2

Microsoft PowerPoint - STU_EC_Ch02.ppt

Microsoft PowerPoint - STU_EC_Ch02.ppt 樹德科技大學資訊工程系 Chapter 2: Number Systems Operations and Codes Shi-Huang Chen Sept. 2010 1 Chapter Outline 2.1 Decimal Numbers 2.2 Binary Numbers 2.3 Decimal-to-Binary Conversion 2.4 Binary Arithmetic 2.5