下篇-C语言本质

计算机中数的表示

1、二进制小数可以这样定义： (0.A1A2A3...)2=A1×2-1+A2×2-2+A3×2-3+... 这个定义同时也是从二进制小数到十进制小数的换算公式。从本节讲的十进制转二进制的推导过程出发类比一下，十进制小数换算成二进制小数应该怎么算？

每次乘2取整。和除2反序取余的证明过程类似

2、再类比一下，八进制（或十六进制）与十进制之间如何相互换算

不过是把基数换成8或16

例如-1表示成10000001,+1表示成00000001。思考一下,N个bit的Sign and Magnitude表示法能够表示的最大整数和最小整数分别是多少?请写出算式。

最小整数 -2^(N-1) 最大整数 2^(N-1)-1

数据类型详解

运算符详解

1、下面两行 printf 打印的结果有何不同?请读者比较分析一下。 int i = 0xcffffff3; printf("%x\n", 0xcffffff3>>2); printf("%x\n", i>>2);

第一个printf里的是无符号数，而第二个里的i则是有符号数，有符号数字右移时，与无符号数的差异是负数。当是负数时，最高位移入1还是0是不确定的(Implementation-defined)。因为0xcffffff3最高位是1,所以是负数，区别如上。

1、统计一个无符号整数的二进制表示中1的个数，函数原型是int countbit(unsigned int x);。

    int countbit(unsigned int x)
    {
        int i = 31, count = 0;
        for(; i>-1; --i)
            if((x>>i)&1==1)
                ++count;
        return count;
    }

2、用位操作实现无符号整数的乘法运算，函数原型是unsigned int multiply(unsigned int x, unsigned int y);。例如：(11011)2×(10010)2=((11011)2<<1)+((11011)2<<4)。

test

3、对一个32位无符号整数做循环右移，函数原型是 unsigned int rotate_right(unsigned int x);。所谓循环右移就是把低位移出的部分补到高位上去，例如rotate_right(0xdeadbeef, 8)的值应该是0xfdeadbee。

test

1、请在网上查找有关RAID（Redundant Array of Independent Disks，独立磁盘冗余阵列）的资料，理解其实现原理，其实就是利用了本节的性质3和4。

这题可以讲一讲。

本节可以让学生根据教材附录做UTF-8和Unicode编码的相互转换

有一段代码:

#include <stdio.h>
int array[] = {123, 43, 21, 171, 42, 99, 216};
#define LEN (sizeof(array) / sizeof(array[0]))
int main(void){
    int i, sum = 0;
    for(i=0; i<LEN; i++)
        sum += array[i];
    printf("%d\n", sum);
    return 0;
}

如果把for循环写成这样:

    for(i=-1; i<LEN-1; i++)
        sum += array[i+1];

结果和原来是否相同?

不. 结果会变成0. 因为sizeof求出的结果类型为unsigned int, 当int i=-1与unsigned int进行比较时, 会进行隐式类型提升, int 提升到unsigned int, 此时-1的二进制解读为unsigned int, 会变成非常大的大数, 比LEN-1要大. (参见CSAPP): 尽可能不使用unsigned int, 因为坑非常多.

以下代码得到的sum是0xfff, 对吗?
int i = 0;
unsigned int sum = 0;
for(; i<16; i++)
    sum = sum + 1U<<i;

不对. 因为符号+的优先级高于<<, 所以代码不能正常工作.

以下代码定义了指针变量p并把它放在一个表达式中参与运算:
char *p = "hello";
size_t n = sizeof (int) * p;
虽然还没有学到指针类型, 但现在我们不关心运算结果, 而是关心表达式的语法解析. sizeof (int) p这个表达式应该怎么理解呢? 一种理解是sizeof(int)乘以p, 另一种理解是, 号, (int)和sizeof是依次作用于p的前缀运算符. 动手试验一下看看编译器是怎么理解的, 想想为什么编译器会这样理解.

编译器是理解为sizeof(int) 乘以p的.

1、以下代码查找和打印0~1024之间所有256的倍数,对吗? int i = 0; for (; i <= 1024; ++i) { if (i & 0xff == 0) { printf("%d\n",i); } }

不对;优先级错误，if应该改成if( (i&0xff) == 0) 修改后符合if判断的有0x0, 0x100等，因为0x100根据二进制转换可知0x100=2^8=256, 。随后的后八位是0x00的数都是256的2的倍数。如：

0x100 = 2^8 = 256
0x1000 = 2^82 = 2562 - 512
0x1100 = 2^8+2^82 = 256+2562 = 256+512 = 768
0x11100 = 2^8+2^82+2^84= 256+2562+2564 = 256+512+1024 等，都是加上256的2的倍数，根据乘法原理，256加上n个256其实就是256的n+1倍。所以可以打印出所有256的倍数。

计算机体系结构基础

x86汇编程序基础

*1、把本节例子中的 int $0x80 指令去掉,汇编、链接也能通过,但是执行的时候出现段错误。你能解释其原因吗?

如果把int $0x80去掉，CPU在执行完指令movl $4, %ebx之后要取下一条指令上来执行，而程序中没有写下一条指令，就要从程序被加载的内存位置之后取指令上来执行，结果是未知的：也许执行了未知的指令，也许存在那里的数据不是合法的指令格式，也许那个内存地址根本没有映射到物理地址。如果有int $0x80指令，CPU执行到这里就会进内核去执行，并且再也不会回来了，就不会取到后面的未知指令。

汇编与C之间的关系

1、在第 2 节 “自定义函数”讲过，Old Style C风格的函数声明可以不指定参数个数和类型，这样编译器不会对函数调用做检查，那么如果调用时的参数类型不对或者参数个数不对会怎么样呢？比如把本节的例子改成这样： int foo(); int bar(); int main(void) { foo(2, 3, 4); return 0; } int foo(int a, int b) { return bar(a); } int bar(int c, int d) { int e = c + d; return e; } main函数调用foo时多了一个参数，那么参数a和b分别取什么值？多的参数怎么办？foo调用bar时少了一个参数，那么参数d的值从哪里取得？请读者利用反汇编和gdb自己分析一下。

调用foo(2, 3, 4)，a和b的取值是2和3，多的参数未使用，调用时压栈，返回时出栈，并没有什么影响；如果调用bar(a)，则参数d的值是从栈帧上强行取来的，结果是未知的。

1、编写一个程序，测试运行它的平台是大端还是小端字节序。
union {
    int n;
    unsigned char byte[4];
} a;

链接详解

预处理

Makefile基础

指针

1、对照本节的描述，像图 23.1 “指针的基本概念”那样画图理解函数的调用和返回过程。在下一章我们会看到更复杂的参数和返回值形式，在初学阶段对每个程序都要画图理解它的运行过程，只要基本概念清晰，无论多复杂的形式都应该能正确分析。

2、现在回头看第 3 节 “形参和实参”的习题1，那个程序应该怎么改？

int a

1、想想以下定义中的 const 分别起什么作用?编写程序验证你的猜测。 const char p; char const p; char const p;

1.char *p为常量 2.p为常量，指向char * 3.p

分析以下复杂声明 char (*(*x(void))[3])(void);

函数接口

1、定义以下变量:

char a[4][3][2] = {{{'a', 'b'}, {'c', 'd'}, {'e', 'f'}},
{{'g', 'h'}, {'i', 'j'}, {'k', 'l'}},
{{'m', 'n'}, {'o', 'p'}, {'q', 'r'}},
{{'s', 't'}, {'u', 'v'}, {'w', 'x'}}};
char (*pa)[2] = &a[1][0];
char (*ppa)[3][2] = &a[1];

要想通过 pa 或 ppa 访问数组 a 中的 'r' 元素,分别应该怎么写?

pa[5][1] ppa[1][2][1]

strcpy中还强调了 src 和 dest 所指向的内存空间不能有重叠。凡是有指针参数的C标准库函数基本上都有这条要求,每个指针参数所指向的内存空间互不重叠,例如这样调用是不允许的: char buf[10] = "hello"; strcpy(buf, buf+1);

可是我的程序却没有错误。

自己实现一个 strcpy 函数,尽可能简洁,你能用三行代码写出函数体吗?

    /* 我的实现 */
    char *my_strcpy(char *dest, const char*src)
    {
        char *temp = dest;
        while(*src)
            *dest++ = *src++;
        return temp;
    }

    /* linux的实现 参照：http://www.chinaunix.net/old_jh/23/25356.html */
    char * strcpy(char * strDest,const char * strSrc)
    {
        if ((strDest==NULL)||(strSrc==NULL)) //[1]
                throw "Invalid argument(s)"; //[2]
        char * strDestCopy=strDest;  //[3]
        while ((*strDest++=*strSrc++)!='\0'); //[4]
        return strDestCopy;
    }

编一个函数,输入一个字符串,要求做一个新字符串,把其中所有的一个或多个连续的空白字符都压缩为一个空格。这里所说的空白包括空格、'\t'、'\n'、'\r'。例如原来的字符串是: This Content hoho ok? file system uttered words ok ok end. is ok ? 压缩了空白之后就是: This Content hoho is ok ok? file system uttered words ok ok ? end. 实现该功能的函数接口要求符合下述规范: char shrink_space(char dest, const char *src, size_t n); 各项参数和返回值的含义和 strncpy 类似。完成之后,为自己实现的函数写一个Man Page。

    char *my_strcpy(char *dest, const char*src)
    {
        char *temp = dest;
        while((*dest++ = *src++) != '\0')
            /* do nothing */;
        return temp;
    }
    bool is_space(char c)
    {
        if(c==' ' || c=='\t' || c=='\n' || c=='\r')
            return true;
        else
            return false;
    }
    char *shrink_space(char *dest, const char *src, size_t n)
    {
        size_t i=0, j=0;
        while(i<n && src[i]) {
            if(is_space(src[i])) {
                dest[j++] = ' ';
                while(is_space(src[++i]))
                    ; 
            }else
                dest[j++] = src[i++];
        }
        /* my implementation                  https://github.com/YongHaoWu/algorithm_and_datastruct/blob/master/algorithms/my_strcpy.c
        size_t i, j;
        for(j=0,i=0; i<n && src[i]!='\0'; ++i) {
            if(is_space(src[i]) && is_space(src[i+1])) {
                continue;
            }else {
                dest[j] = src[i];
                ++j;
            }
        }
        */
        for(; i<n; ++i)
            dest[i] = '\0';
        return dest;
    }

1、[K&R]的5.6节有一个qsort函数的实现，可以对一组任意类型的对象做快速排序。请读者仿照那个例子，写一个插入排序的函数和一个折半查找的函数。

generics.c

1、实现一个功能更完整的printf，能够识别%，能够处理%d、%f对应的整数参数。在实现中不许调用printf(3)这个Man Page中描述的任何函数。

我的实现，思路基于wine开源项目，比宋老师的实现要好：https://github.com/YongHaoWu/algorithm_and_datastruct/blob/master/algorithms/myprintf.c 其实要完美实现%f打印，难度是非常高的。我自己比较好的实现是在： https://github.com/YongHaoWu/algorithm_and_datastruct/blob/master/algorithms/my_sprintf.c 但是还是不正确的。更多资料请查阅Dragon4算法或Grisu算法。

C标准库

在系统头文件中找到各种错误码的宏定义

用fgets/fputs编写一个拷贝文件的程序, 根据本节对fgets函数的分析, 这个程序应该只能拷贝文本文件, 试试用它拷贝二进制文件会出现什么问题.

用scanf读入一个字符串, 然后自己编写代码将它转换成整数, 你能给出什么办法?

本节的函数全都要求学生自己实现一遍
memset
strlen
memcpy和memmove，restrict关键字，strdup
strcat和strncat
memcmp，strcmp和strncmp，strcasecmp和strncasecmp
strchr和strrchr，strstr

example

1、出于练习的目的，strtok和strtok_r函数非常值得自己动手实现一遍，在这个过程中不仅可以更深刻地理解这两个函数的工作原理，也为以后理解“可重入”和“线程安全”这两个重要概念打下基础。

    char *mystrtok(char *str, const char *delim)
    {
        char *head = str;
        static char *saver;
        if(str)
            saver = str;
        else
            head = saver;
        if(! *saver)
            return NULL;
        for(; *saver!=*delim; ++saver) {
            if(! *(saver+1)) {
                ++saver;
                break;
            }
        }
        while(*saver == *delim) {
            *saver = '\0';
            ++saver;
        }
        return head;
    }

    char *mystrtok_r(char *str, const char *delim, char **saveptr)
    {
        char * head = str;
        if(! *str)
            return NULL;
        for(; *str!=*delim; ++str) {
            if(! *(str+1)) {
                ++str;
                break;
            }
        }
        while(*str == *delim) {
            *str = '\0';
            ++str;
        }
        *saveptr = str;
        return head;
    }

2、解析URL中的路径和查询字符串。动态网页的URL末尾通常带有查询，例如：
http://www.google.cn/search?complete=1&hl=zh-CN&ie=GB2312&q=linux&meta=
http://www.baidu.com/s?wd=linux&cl=3
比如上面第一个例子，http://www.google.cn/search是路径部分，?号后面的complete=1&hl=zh-CN&ie=GB2312&q=linux&meta=是查询字符串，由五个“key=value”形式的键值对（Key-value Pair）组成，以&隔开，有些键对应的值可能是空字符串，比如这个例子中的键meta。

现在要求实现一个函数，传入一个带查询字符串的URL，首先检查输入格式的合法性，然后对URL进行切分，将路径部分和各键值对分别传出，请仔细设计函数接口以便传出这些字符串。如果函数中有动态分配内存的操作，还要另外实现一个释放内存的函数。完成之后，为自己设计的函数写一个Man Page。

    int parse_url(char *url, char **buffer)
    {
        int i = 0;
        char *saveptr = NULL;
        //char *result = mystrtok(url, "?");
        char *result = mystrtok_r(url, "?", &saveptr);
        if(result == NULL)
            printf("NULL\n");

        while(1) {
            buffer[i] = malloc(100);
            memset(buffer[i], 0, 100);
            //result = mystrtok(NULL, "&");
            result = mystrtok_r(saveptr, "&", &saveptr);
            if(result == NULL)
                break; 
            memmove(buffer[i++], result, strlen(result));
        }
        return i;
    }

    void release_url(char **buffer, int num)
    {
        int i;
        for(i=0; i<num; ++i)
            free(buffer[i]);
    }

1、在系统头文件中找到各种错误码的宏定义。

man errno

2、做几个小练习,看看 fopen 出错有哪些常见的原因。打开一个没有访问权限的文件。 fp = fopen("/etc/shadow", "r"); if (fp == NULL) { perror("Open /etc/shadow"); exit(1); } fopen 也可以打开一个目录,传给 fopen 的第一个参数目录名末尾可以加 / 也可以不加 / ,但只允许以只读方式打开。试试如果以可写的方式打开一个存在的目录会怎么样呢? fp = fopen("/home/akaedu/", "r+"); if (fp == NULL) { perror("Open /home/akaedu"); exit(1); } 请读者自己设计几个实验,看看你还能测试出哪些错误原因?

    FILE *file1;
    if(!(file1 = fopen("dir1","r+")))
        perror("open dir read\n");
    if(!(file1 = fopen("dir1","w+")))
        perror("open dir write\n");
    if(!(file1 = fopen("dir2/file2","w+")))
        perror("open dir only excute flie\n");
    if(!(file1 = fopen("dir2/fi","r+")))
        perror("open dir not exisits flie\n");
    if(!(file1 = fopen("/etc/shadow","r+")))
        perror("open right\n");

1、编写一个简单的文件复制程序。 $ ./mycp dir1/fileA dir2/fileB 运行这个程序可以把 dir1/fileA 文件拷贝到 dir2/fileB 文件。注意各种出错处理

    #include <stdio.h>
    #include <stdlib.h>
    int main(void)
    {
        FILE *file1, *file2;
        int ch;
        if(!(file1 = fopen("dir1/fileA","r+"))) {
            perror("open file1\n");
            exit(1);
        }
        if(!(file2 = fopen("dir2/fileB","w+"))) {
            perror("open file2\n");
            exit(1);
        }
        while((ch=fgetc(file1)) != EOF)
            fputc(ch, file2);
        fclose(file1);
        fclose(file2);
        return 0;
    }

2、虽然我说 getchar要读到换行符才返回,但上面的程序并没有提供证据支持我的说法,如果看成每敲一个键 getchar 就返回一次,也能解释程序的运行结果。请写一个小程序证明 getchar 确实是读到换行符才返回的。

    #include <stdio.h>
    int main(void)
    {
        while(1)
            printf("%c\n", getchar());
        return 0;
    }

1、用 fgets / fputs 写一个拷贝文件的程序,根据本节对 fgets 函数的分析,应该只能拷贝文本文件,试试用它拷贝二进制文件会出什么问题

乱码。

    #include <stdio.h>
    #include <stdlib.h>
    int main(void)
    {
        FILE *file1, *file2;
        if(!(file1 = fopen("a.out","r+"))) {
            perror("open file1\n");
            exit(1);
        }
        if(!(file2 = fopen("dir2/file2","w+"))) {
            perror("open file2\n");
            exit(1);
        }

        char *s = (char*)malloc(100);
        fgets(s, 100, file1);
        fputs(s, stdout);

        fclose(file1);
        fclose(file2);
        return 0;
    }

小练习:编写一个小程序让它耗尽系统内存。观察一下,分配了多少内存后才会出现分配失败?内存耗尽之后会怎么样?会不会死机?

如果有函数接口 void func(const int p); 这里的 const 有意义吗?

没有

这里的参数指针是 const char ** ,有 const 限定符,却不是传入参数而是传出参数,为什么?如果是传入参数应该怎么表示?

传入参数：char const **

为什么在 main 函数中不能直接调用 free(p) 释放内存,而要调用 free_unit(p) ?为什么一层指针的函数接口 void alloc_unit(unit_t *p); 不能分配内存,而一定要用两层指针的函数接口?

Nope

    #include <stdio.h>
    #include <string.h>
    static const char *msg[] = {"Sunday", "Monday",
        "Tuesday", "Wednesday",
        "Thursday", "Friday",
        "Saturday"};
    char *get_a_day(int idx)
    {
        static char buf[20];
        strcpy(buf, msg[idx]);
        return buf;
    }
    int main(void){
        printf("%s %s\n", get_a_day(0), get_a_day(1));
        return 0;
    }

这个程序的运行结果是 Sunday Monday 吗?请读者自己分析一下不是，是Sunday Sunday。因为在函数里的buf是static类型，所以它的内存地址固定不变。当使用printf时，因为参数的压栈出栈会从右到左运行函数（即先运行get_a_day(1)) ，再调用的是get_a_day(0),所以buf变成了Sunday，而两个get_a_day函数都是返回buf的地址，所以结果都是Sunday。 注意: : 在mac(clang)上, 压栈出栈是从左到右, 结果是两个Monday. 结果取决于函数默认调用是什么. linux上(gcc), 默认是用_cdecl约定, 按从右至左的顺序压参数入栈. 苹果上(clang) 不知道是什么约定, 从左到右的, 被它坑了. 我还以为跟linux上一样, 一直在想, 究竟是入栈的时候调用函数还是出栈.

现在确定了是入栈的时候就调用了

[K&R]的5.6节有一个 qsort 函数的实现,可以对一组任意类型的对象做快速排序。请读者仿照那个例子,写一个插入排序的函数和一个折半查找的函数。

code

1、编程读写一个文件 test.txt ,每隔1秒向文件中写入一行记录,类似于这样: 1, 2, 2007-7-30 15:16:42 2007-7-30 15:16:43 该程序应该无限循环,直到按Ctrl-C终止。下次再启动程序时在 test.txt 文件末尾追加记录,并且序号能够接续上次的序号,比如: 1, 2, 3, 4, 5, 2007-7-30 2007-7-30 2007-7-30 2007-7-30 2007-7-30 15:16:42 15:16:43 15:19:02 15:19:03 15:19:04 这类似于很多系统服务维护的日志文件,例如在我的机器上系统服务进程 acpid 维护一个日志文件 /var/log/acpid ,就像这样: $ cat /var/log/acpid [Sun Oct 26 08:44:46 2008] logfile reopened [Sun Oct 26 10:11:53 2008] exiting [Sun Oct 26 18:54:39 2008] starting up ... 每次系统启动时 acpid 进程就以追加方式打开这个文件,当有事件发生时就追加一条记录,包括事件发生的时刻以及事件描述信息。获取当前的系统时间需要调用 time(2) 函数,返回的结果是一个 time_t 类型,其实就是一个大整数,其值表示从UTC(Coordinated Universal Time)时间1970年1月1日00:00:00(称为UNIX系统的Epoch时间)到当前时刻的秒数。然后调用 localtime(3) 将 time_t 所表示的UTC时间转换为本地时间(我们是+8区,比UTC多8个小时)并转成 struct tm 类型,该类型的各数据成员分别表示年月日时分秒,具体用法请查阅Man Page。调用 sleep(3) 函数可以指定程序睡眠多少秒。

code

2、INI文件是一种很常见的配置文件,很多Windows程序都采用这种格式的配置文件, 在Linux系统中Qt程序通常也采用这种格式的配置文件。比如: ;Configuration of http [http] domain=www.mysite.com port=8080 cgihome=/cgi-bin ;Configuration of db [database] server = mysql user = myname password = toopendatabase 一个配置文件由若干个Section组成,由[]括号括起来的是Section名。每个Section下面有若干个 key = value 形式的键值对(Key-value Pair),等号两边可以有零个或多个空白字符(空格或Tab),每个键值对占一行。以;号开头的行是注释。每个Section结束时有一个或多个空行, 空行是仅包含零个或多个空白字符(空格或Tab)的行。INI文件的最后一行后面可能有换行符也可能没有。现在XML兴起了,INI文件显得有点土。现在要求编程把INI文件转换成XML文件。上面的例子经转换后应该变成这样:

<!-- Configuration of http -->
<http>
<domain>www.mysite.com</domain>
<port>8080</port>
<cgihome>/cgi-bin</cgihome>
</http>
<!-- Configuration of db -->
<database>
<server>mysql</server>
<user>myname</user>
<password>toopendatabase</password>
</database>

code

3、实现类似 gcc 的 -M 选项的功能,给定一个 .c 文件,列出它直接和间接包含的所有头文件,例如有一个 main.c 文件:

    #include <errno.h>
    #include "stack.h" 
    int main()
    {
    return 0;
    }

你的程序读取这个文件,打印出其中包含的所有头文件的绝对路径: $ ./a.out main.c /usr/include/errno.h /home/akaedu/stack.h: cannot find /usr/include/features.h /usr/include/bits/errno.h /usr/include/linux/errno.h ...... 如果有的头文件找不到,就像上面例子那样打印 /home/akaedu/stack.h: cannot find 。首先复习一下第 2.2 节 “头文件”讲过的头文件查找顺序,本题目不必考虑 -I 选项指定的目录,只文件所在的目录以及系统目录 /usr/include 中查找。

下篇-C语言本质

下篇-C语言本质

计算机中数的表示

数据类型详解

运算符详解

计算机体系结构基础

x86汇编程序基础

汇编与C之间的关系

链接详解

预处理

Makefile基础

指针

函数接口

C标准库

results matching ""

No results matching ""