学步园

第 1章 C语言

1 指针

C语言中定义字符串的两种形式：

char a[]="hello world";

char *b="hello world";

对于这两种形式的区别和联系可以使用下面的操作进行区别：

（1）sizeof(a)=strlen(a)+1;//主要是C语言中对于字符串的存储特点，会自动的以'\0'作为结束标志。

sizeof(b)=4;

（2）strlen(a)==strlen(b);//因为a和b其实都是定义了一个字符串。

(3)从实现的本质上看，a是一个数组，在进行程序编译之后是一个存在于符号表中，其对应的数组内存是在静态区分配的，而b是一个指针，应该是存储在静态区的，它指向的字符串应该作为一个不可改变的数据存储的。

非常重要的一点是：a作为一个数组，他的内容是改变的，而b的内容是不能改变的，强行改变会在运行时出错。

2. sizeof总结

siezof是一个操作符，它不是函数

（1）其参数可以作为数据类型或者为一般变量

例如：sizeof(int),sizeof(double)

(2) 参数可以是数组或指针

但是，需要注意的一点是当数组作为函数参数的时候会退化为指针，这时再在函数中使用sizeof的话就是测试指针的大小了

（3）参数可以是结构或类

需要注意两点：结构或类中的静态成员不对结构或者类的大小产生影响，因为静态变量的存储位置与结构或类的实例地址无关。第二，没有任何成员的结构或类的大小为1，因为必须保证结构或类的每一个实例在内存中都有唯一的地址。第三类中函数对类的大小没有影响。

3. 野指针
野指针不是NULL指针，而是指向“垃圾”内存的指针。野指针很危险，它可能造成不该访问的数据或不该修改的数据被访问或者篡改。在应用free或delete释放了指针指向的内存之后，应该将指针重新初始化为NULL，这样就可以防止野指针。

4. 位运算
(1). 异或运算
异或运算的逆运算就是其本身，所以两次异或同一个数的结果不变，即a^b^b=a
定义两个运算#和@，且互为逆运算，同时#满足交换律，那么下面实现x和y的交换：
x=x#y;
y=x@y;
x=x@y;
加法和减法是逆运算，并且加法满足交换律，所以一种可能是#为加法，@为减法。
异或运算是逆运算并且满足交换律，所以#和@同时为异或运算。

(2)常见二进制位变换

 去掉最后一位 (101101->10110) x>>1
在最后加一个0　 (101101->1011010) x<<1
在最后加一个1　 (101101->1011011) (x<<1)+1
把最后一位变成1　 (101100->101101) x|1
把最后一位变成0　 (101101->101100) (x|1)-1
最后一位取反 (101101->101100) x^1
把右数第k位变成1 (101001->101101,k=3) x|(1<<(k-1))
把右数第k位变成0 (101101->101001,k=3) x&~(1<<(k-1))
右数第k位取反　 (101001->101101,k=3) x^(1<<(k-1))
取末三位 (1101101->101) x&7
取末k位　 (1101101->1101,k=5) x&((1<<k)-1)
取右数第k位　 (1101101->1,k=4) x>>(k-1)&1
把末k位变成1　 (101001->101111,k=4) x|((1<<k)-1)
末k位取反 (101001->100110,k=4) x^((1<<k)-1)
去掉整数最右边的1 (100101111->100101110) x&(x-1)
把右边连续的1变成0 (100101111->100100000) x&(x+1)
把右起第一个0变成1 (100101111->100111111) x|(x+1)
把右边连续的0变成1 (11011000->11011111) x|(x-1)
去掉右起第一个1的左边 (100101000->1000) x&(x^(x-1))
取右边连续的1 (100101111->1111) (x^(x+1))>>1

（3）将第n位置位或清零

置位：a|=(0x1<<n)

清零：a&=~(0x1<<n)

清除整数a最右边的1：a&(a-1)

将一个整数对齐到n：a=(a+n-1)&~(n-1)

常用位运算记录（参考：http://blog.chinaunix.net/uid-20561882-id-2793594.html）：

1) 判断int型变量a是奇数还是偶数
a & 1 = 0 偶数 （与1相加能进位说明个位是1,个位为0）
a & 1 = 1 奇数 （与1相加不能进位说明个位是0,个位为1）
或者
a&1
判断奇偶也就是判断个位上的数
a = 10010001
b=1
a&b = 0 != b 说明第1位因为是1，所以可进位，所以a的值改变
b=10 a&b = a 说明第二位是0，因为每进位  
 a&b = b 说明判断为是0，因为 0&b = b  
(2) 取int型变量a的第k位 (k=0,1,2……sizeof(int))，即a> > k& 1
因为我要取第k位，那么把第k位移到第0位，然后擦掉其他位  
(3) 将int型变量a的第k位清0，即a=a& ~(1< < k)  
(4) 将int型变量a的第k位置1， 即a=a|(1< < k)  
(5) int型变量循环左移k次，即a=a< < k|a> > 16-k (设sizeof(int)=16)
因为限定是16的循环，那么左移很可能移出去，但是就像地球是圆的一样，从左边跑可以跑到，从右边跑也可以跑到，所以向左移多少就是向右移多少的补 （k+16-k = 16 就是跑了一圈），所以思想是当向左跑跑出界了的话，那么就把向右跑给插入进去吧。。。。  
(6) int型变量a循环右移k次，即a=a> > k|a< < 16-k (设sizeof(int)=16)  
定理1：设a，b为两个二进制数，则a+b = a^b + (a&b)<<1。
证明：a^b是不考虑进位时加法结果。当二进制位同时为1时，才有进位，因此 (a&b)<<1是进位产生的值，称为进位补偿。将两者相加便是完整加法结果。
定理2：使用定理1可以实现只用位运算进行加法运算。
证明：利用定理1中的等式不停对自身进行迭代。每迭代一次，进位补偿右边就多一位0，因此最多需要加数二进制位长度次迭代，进位补偿就变为0，这时运算结束。  
(7)整数的平均值
对于两个整数x,y，如果用 (x+y)/2 求平均值，会产生溢出，因为 x+y 可能会大于INT_MAX，但是我们知道它们的平均值是肯定不会溢出的，我们用如下算法：
int average(int x, int y) //返回X,Y 的平均值 {
        return (x& y)+((x^y)> > 1);
}  
x+y = x^y+(x&y)<<1;
x*2 = x<<1;
x/2 = x>>1;
所以(x+y)/2 = (x^y + x&y<<1)>>1 = x^y>>1 + x&y 
512 * 7 = 512 * (4 + 2 + 1) = 512 * 4 + 512 * 2 + 512
= 512 << 2 + 512 << 1 + 51  
512/7 因为不能约分，又不是2的倍数，所以除不尽，所以只能近似
512/8 = 512>>3

5. 内存对齐

常见的内存对齐问题包括两个：自然对齐和强制对齐。

各个类型的自然对齐是其内存地址必须是其类型本身的整数倍。结构体对齐到其中成员最大长度类型的整数倍。

计算机中内存空间按照字节划分，从理论上讲似乎对任何类型的变量地址访问可以从任何地址开始，但实际情况是在访问特定类型变量的时候经常在特定的内存地址访问，这就需要各类型数据按照一定的规则在空间上排列，而不是顺序地一个接一个第的排放，这就是对齐。

如果不按照适合其平台要求对数据存放进行对齐，一般会带来效率上的损失。比如，有些平台每次读都是从偶地址开始，如果一个int型存放在偶地址开始的地 方，那么一个读周期就可以读出，而如果存放在奇地址开始的地方，就需要2个读周期，并对两次读的结果的高低字节进行拼凑才能得到该数据。

6. 浮点数

单浮点数float和双浮点符double

浮点数存储中涉及的是符号位，阶码（指数）和尾数

对于float是4个字节中32位：8位阶码，23位尾数

对于double是8个字节中64位：16位解码，47位尾数

具体如下：

 

 

 

其内存结构采用代码描述如下：

typedef strtuct _float{

bool sign:1;

char expon:8;

unsinged int mant:23;

}float

7.整数存储

整数编码常见的有原码，反码和补码

原码：在数值面前增加一个符号位

反码：正数的反码是其本身，负数的反码是对其绝对值逐位取反。

补码：正数的补码与原码相同，负数的补码是取模（计算方法是对其绝对值取反加1）

原码无法满足运算要求，所以对除符号位外的其余逐位取反就产生了反码。反码与原码的取值空间是一一对应的。但是在进行反码减法运算的时候出现了正零（0x00）和负零(0x80)

补码设计的目的：

（1）使符号位能与有效值部分一起参加运算，从而简化运算规则。

（2）使减法运算转化为加法运算，进一步简化计算机中运算器的电路设计。

补码的范围是[-128,127],-128没有对应的原码和反码。

8. 字符编码

常见的字符编码是ASCII码和UNICODE码

常见ASCII码的大小规则：0<..<9<A<..<Z<a<..z

A:65, 0x41

a:97,0x61

 0:48, 0x30

' ':32,0x20

在C语言中，要区分多字节字符串与宽字符字符串的区别。在多字节字符串中，每个字符的编码宽度都不等，可以是一个字节，也可以是多个字节。

char* str="Hello world! 你好，世界！";

这就是一个多字节字符串，英文占一个字节，中文占两个字节。

wchar_t *wstr=L"Hello world!你好！世界！";

这个是宽字节字符串，其中的所有字符都是占2个字节

9. 溢出问题

溢出是C语言中最常见的漏洞。主要包括数组溢出，数溢出，缓冲区溢出，指针溢出和栈溢出。由于系统存在着各种溢出漏洞，就给病毒和恶意程序提供了传播和攻击的可能。比如冲击波病毒，就是利用了windows系统中的缓冲区溢出漏洞。

数组溢出就是常见的数组越界

缓冲区溢出是一个比较容易被攻击的问题。比如下面的一个小程序：

#include <stdio.h>
#include <stdlib.h>
void func(){
printf("Hacked by me\n");
exit(1);
}
int main(){
int buf[1];
buf[2]=(int)func;
return 0;
}

这个程序运行之后会输出：Hacked by me

这儿就是利用了缓冲区溢出的问题。buf[2]=(int)func;这一句发生了缓冲区溢出，利用func的地址覆盖了buf+2处的内存内容。如果对 函数运行栈比较熟悉的话，会发现被覆盖的正好就是main函数的返回地址。所以将main函数的返回地址变成了func的入口地址。