系统级程序设计笔记(3)

Representation of Data


前言

本篇博客整理了系统级程序设计课程中的lecture4.

相关材料见:SLP-Notes

待更新

  • 浮点数
  • 布尔代数
  • 位运算的实例:交换

Numbering System

  • 十进制
  • 二进制
  • 十六进制

Alphanumeric Expression

1

  • ASCII code

    • American Standard Code for Information Interchange

    • Standard ASCII code uses 7-digits to express 128 (2^7) characters

      A = 65

    • man ascii

      1

  • gb2312 / gbk / gb18030 / big5

    如汉字

  • Unicode

    • UCS

      UCS-2 / UCS-4

    • UTF

      • for transportation
      • UTF-7 / UTF-8 / UTF-16 / UTF-32
  • Quoted-printable: Base64/32/16

    1

    • [简答题] 为什么使用base64?

      One reason is that transferring images on web pages to base64 encoding makes images loaded prior to contents, decreasing http requests, and lowering server’s overload.

  • URL code

    use % + ascii

    Eg: http://www.wr.com/?file=%2e%2e%2f%2e%2e%2fpasswd

  • HTML code

    use &#+decimal number or &#x+hexdecimal number

    Eg: <p>ab</p> -> <p>&#97;&#x63;</p>


Number Expression

  • 整数表示法

    • +0 与 -0

      Unsigned Integer

      Signed Integer

      1’s complement

      2’s complement

    • 补码

      • [简答题] 为什么需要补码?

        为了简化电路的设计,可将减法运算转换成加法及补码(complement)运算来取代。

      • 补码是一种表示负数的方式

      • 对每一 k 进位制的数字系统而言,其补码有两种:

        “k”的补码

        “k-1”的补码

    • 1’s complement & 2’s complement

      • 在8位表示的整数下:
        1’s complement 2’s complement
      0000 0000 +0 0
      1111 1111 -0 -1
      max 0111 1111 = +127 0111 1111 = +127
      min 1000 0000 = -127 1000 0000 = -128
      • [简答题] 为什么2’s complement没有 +0 和 -0 的区分?
    • ???P68 图

  • 浮点数表示法

    详见教材:《深入理解计算机系统》(第三版)

    • 符号:S

      尾数:M

      阶码:E

    • P78 图2-33

      规格化的值

      非规格化的值

      无穷大

      NaN

    • P80 图2-34

    • P82 图2-36

    • 舍入 (rounding)

      P83 图2-37

    • 不同数据类型之间的转换

      P86 int / float / double

  • 练习题

    • 教材P77 2.46
    • 教材P81 2.47
    • 教材P82 2.48

Boolean Algebra

  • 位级运算
  • 逻辑运算
  • 移位运算

Bit Operations

  • Bit operations must be done between two INT operands!

  • 详见博客:C语言中补码的整数运算特性 .

  • 交换函数

    void inplace_swap (int *x, int *y) {
      *x = *x ^ *y;
      *y = *x ^ *y;
      *x = *x ^ *y;
    }
    

    x == y时,此交换函数无效.

  • 判断一个数是无符号数 / 有符号数

    How to check if a number SIGNED or UNSIGNED by bit operation?

    以4字节整数为例,使此数与 0xffffffff或运算,故得到其变换后的整数 (0xffffffff) 位表示。由于 0xffffffff 在无符号数中表示max,在有符号数中表示-1,因此加以判断即可。

    例如:

    #include <stdio.h>
    
    void determine(signed int signed_num, unsigned int unsigned_num){
        signed int signed_old_num = signed_num;
        unsigned int unsigned_old_num = unsigned_num;
          
        signed_num = signed_num | 0xffffffff;
        unsigned_num = unsigned_num | 0xffffffff;
          
        if (signed_num < 0) {
            printf("%d is a signed_num\n", signed_old_num);
        }
          
        if (unsigned_num > 0) {
            printf("%d is a unsigned_num\n", unsigned_old_num);
        }
    }
    
    int main(int argc, char **argv)
    {
        signed int signed_num;
        unsigned int unsigned_num;
          
        /* both is positive */
        signed_num = 10;
        unsigned_num = 20;
        determine(signed_num, unsigned_num);
          
        /* signed integer is negative */
        signed_num = -10;
        determine(signed_num, unsigned_num);
          
        return 0;
    }
    

    Output:

    10 is a signed_num
    20 is a unsigned_num
    -10 is a signed_num
    20 is a unsigned_num
    
  • 有符号数与无符号数的转换

    #include <stdio.h>
    
    #define TOTAL_ELEMENTS (sizeof(array) / sizeof(array[0]))
    
    int array[] = { 23, 34, 12, 17, 204, 99, 16 };
    
    void main()
    {
      int d = -1, x;
      if (d <= TOTAL_ELEMENTS-2)
        x = array[d + 1];
      else x = 0;
        
      printf("%d\n",x);
    }
    

    Output: 0

    原因:

    sizeof()返回类型为size_t,为一无符号数,又有:

    C语言中有符号数和无符号数进行运算(包括逻辑运算和算术运算)默认会将有符号数看成无符号数进行运算,其中算术运算默认返回无符号数,逻辑运算返回0或1。

    因此,-1的位表示为0xffffffff,是无符号数中的最大数,故条件不成立,x = 0.