16：位运算

16.1：位运算概述

二进制与位运算

程序中的数据在内存中，都是以二进制的形式存在的。内存中的数据都是0和1组成的序列。

位运算：是直接对整数在内存中的二进制位进行操作；直接对二进制位进行操作，使得位运算比普通的运算操作效率要高

学习位运算，首先要学习什么是二进制位？
1. byte字节
2. bit位

位运算操作符：
1. 与(and)：&
2. 或(or)：|
3. 取反(not)：~
4. 异或(xor)：^
5. 左移(shl)：<<
6. 右移(shr/sar)：>>

16.2：与(and)：&

与运算：只有当2个数对应的位都为1，该位运算结果为1，否则运算结果为0。

int main(void) {
    int a = 15;//1111
    int b = 10;//1010
    int c = 15&10;//1010
    printf(“a&b=%d\n”, c);//a&b=10
    
    return 0;
}

&应用：

//1. 获取一个整数的后n位:(如现实中子网掩码)
获取一个整数的后3位:
int a=100;
a&7(7的二进制码为0111)

2. 使用与运算与取反和移位运算相结合，将整数的某位置零:
a&(~(1<<n))//即可将x第n位置为零
#define CLEARFLAG(a, n) ((a) &= ~(1<<(n)))//把整数a中第n位置为0

3. 判断a中第n位是否为1:
#define FLAGON(a,n) ((a)&(1<<(n)))//判断整数a中第n位是否为1

4. 请出整数a二进制中最右边的1：
a&(a-1)
//计算整数有几个二进制1
int count_ones(int x) {
    int count = 0;
    
    while(x) {
        count++;
        x &= (x-1);
    }
    
    return count
}

16.3：或(or)：|

|：只有当2个数对应的位都为0，该位运算结果为0，否则运算结果为1。

int main(void) {
    int a = 15;//1111
    int b = 10;//1010
    int c = 15|10;//1111
    printf(“a|b=%d\n”, c);//a|b=15
    
    return 0;
}

|应用：
//把整数a中的第n位置为1
#define SETFLAG(a,n)  ((a) |= (1<<(n)))

16.4：取反(not)：~

~：单目运算符；是将一个整数中位为1的变成0，位为0的变成1。

int main(void) {
    int a = 10;//1010
    int b = ~10;//0101
    printf(“~10=%d\n”, b);//5
    
    return 0;
}

~应用：

1.
//取反运算同与运算结合，可以将一个整数的某位置0，比如：
#define CLEARFLAG(a,n) ((a) &= ~(1<<(n)))//把整数a中第n位置为0

16.5：异或(xor)：^

^：相同为0，不同为1。

int main(void) {
    int a = 15;//1111
    int b = 10;//1010
    int c = 15^10;//0101
    printf(“a^b=%d\n”, c);//a^b=5
    
    return 0;
}

//异或运算：
1. 置零
a^0=a
a^a=0//xor eax,eax

2. 两数交换
#define SWAP(a,b) \
do{\
a=a^b;\
b=a^b;\
a=a^b;\
}while(0)
/*
证明：
假设：a和b的初始值：a=a0,b=b0;
第一句：a=a^b即a为a0^b0
第二句：b=a^b即(a0^b0)^b0=》a0^(b0^b0)=》a0^0=》a0
第三句：a=a^b即a0^b0^a0=》a0^a0^b0=》0^b0=》b0
因此，通过上面的推导，实现了a与b值的交换。
*/

3. 单指针实现双链表
/*
可以用单个指针域来表示双向链表：
有任意3个相邻结点：PL， P， PR
那么P->next = PL^PR
对于头结点来说：P没有左边的结点，所以左结点为NULL
所以Head->next = NULL^PR

对于尾结点来说：
尾结点没有右边的结点，所以PR为NULL
Tail->next = PL^NULL

按照上述规则生成链表之后，遍历方法如下：
从左往右遍历链表：
pl=NULL;
p=Head;

while(p!=Tail) {
    pr=pl^(p->next);
    pl=p;
    p=pr;
}

从右往左遍历链表：
pr=NULL;
p=Tail;

while(p!=Head) {
    pl=pr^(p->next);
    pr=p;
    p=pl;
}
*/

单指针双链表

image.png

16.6：移位运算左移(shl)：<<

<<：左移运算符；将一个数a向左移动n位记为：a<<n

将一个数左移N位相当于将一个数乘以2^N

int main(void) {
       int a = 10;
       int b = a<<2;
       printf(“b=%d\n”, b);//40

       return 0;

}

16.7：移位运算右移(shr/sar)：>>

>>：右移运算符；将一个数a向右移动n位记为：a>>n。

右移动运算分为两种右移：

1. 逻辑右移，在移动过程中，左边位用0填充。（有符号数：10000011，对于逻辑右移，向右移动3位，那么左边用0填充，变成了：00010000。）
2. 算术右移，在移动过程中，左边用符号位来填充。（算术右移，向右移动3位，那么左边用1（1为符号位）填充，变成了11110000。而对于01000011，算术右移3位，那么左边用0（0为符号位）填充，变成了00001000。）

在C语言中，右移运算符为算术右移运算符，即左边用符号位来填充。对于无符号数，而将一个数右移N位相当于将这个数除以2^N

int main(void) {
    int a = -3;
    int b = 10;
    int c = a>>2;//
    int d = b>>1;//10/2^1=5
    printf(“a>>2=%d, b>>1=%d\n”, c, d);
    
    return 0; 
}
//证明：
/*
    int a = -3;
    //-3原码10000000 00000000 00000000 00000011
    //-3反码11111111 11111111 11111111 11111100
    //-3补码11111111 11111111 11111111 11111101(加一)
    printf("a的16进制:%x\n", a);//0Xfffffffd
    int b = 10;
    int c = a>>2;//
    //-3补码11111111 11111111 11111111 11111101>>2
    //c补码11111111 11111111 11111111 11111111
    //c反码11111111 11111111 11111111 11111110(减一)
    //c原码10000000 00000000 00000000 00000001(即-1)
    printf("c的16进制:%x\n", c);//0Xffffffff
    int d = b>>1;//10/2^1=5
    printf("a>>2=%d, b>>1=%d\n", c, d);
*/

16.8：位运算综合应用：

1. 将第n位置1或者清零（n是从零开始计算的）：
//把整数a中的第n位置为1
#define SETFLAGE(a, n) ((a)|(1<<(n)))
//把整数a中的第n位置为0
#define CLEARFLAG(a, n) ((a)&(~(1<<(n))))
//判断整数a中第n位是否为1
#define FLAGON(a, n) ((a)&(1<<(n)))

#define BIT(n) (1<<n)
//置1：
a |= BIT(n);
//置0：
a &= ~BIT
//判断：
a & BIT(n)

2. 对称加密：XOR
异或性质：A^0==A, A^A==0
A为明文，B为密文
加密：B=A^key
解密：A=B^key

void func(char *data, int datalen, char *key, int keylen) {
    int i = 0;
    
    for (i=0; i<datalen; i++) {
        data[i] = (char)(data[i] ^ key[i%keylen])
    }
}

常见的位运算：

image.png

位运算在实际项目中的运用

//先将该整数右移24位，与0xFF做与运算，即获得该8位的值。高8位记录了对文件的修改标记：
ulDisposition = (lpIrpStack->Parameters.Create.Options >> 24) & 0xFF;

//清除或者判断某些标志:
#define FlagOn(_F, _SF) ((_F)&(_SF))//查看_F是否包含_SF

mov eax, CRO
add eax, 0FFFEFFFFh//相当于CR0 &= 0xFFFEFFFF;
mov CRO, eax

mov eax, CRO
or  eax, NOT OFFFEFFFFh//CR0 |= ~0xFFFEFFFF
mov CRO, eax 

17：宏定义

预处理->编译->链接->可执行文件（预处理将由预处理程序负责完成）。

程序在编译预处理的阶段，不仅提供了宏定义的功能，还提供了文件包含以及条件编译的功能。

宏在编译前预处理阶段，就已经完成了替换

17.1：宏的定义

1. 宏定义：指用一个标志符代表一个字符串，该标志符就称为宏名。
2. 宏展开：在程序编译预处理阶段，所有宏名将会被替换为宏定义中的字符串的操作。

其定义格式如下(/其标识符，称为宏名)：

//1. 不带参数格式：#define 标识符 字符串
//2. 带参数的格式：#define 标识符(参数表) 字符串

//例子：
#define PI 3.14
float calccirclearea(float r) {
       return PI*r*r;
}

#define MAX(X, Y) (X) > (Y) ? (X) : (Y)
void main(void) {
       int a = 10;
       int b = 11;
       int c = MAX(a, b);

       printf(“max = %d\n”, c);
}

宏定义的优缺点：

#define PI 3.14
1. 有意义
2. 减少修改
3. 无类型检查
4. 无法调试
(宏不是变量，也没有类型，不占内存)

const float pi=3.14f;
1. 有意义
2. 减少修改
3. 有类型
4. 可调试

带参数的宏与函数的优缺点比较：

1. 宏的效率要高(inline)，没有了函数调用过程中的进栈出栈传参拷贝和出栈栈平衡；
2. 宏无法调试
3. 宏无法做到类型检查
4. 传参的计算也不同，宏是简单的替换；函数先计算，再传参。

如：
#define MAX(a, b) ((a)>(b)?(a):(b))

int getMax(int x, int y) {
    return x>y?x:y;
}

MAX(1+2, value)-->((1+2)>(value)?(1+2):(value));
getMax(1+2, value);

17.2：宏的应用与注意事项

1. 宏名一般用大写
2. 使用宏可提高程序的通用性和易读性，减少不一致性，减少输入错误和便于修改。例如：数组大小常用宏定义
3. 预处理是在编译之前的处理，而编译工作的任务之一就是语法检查，预处理不做语法检查。
4. 定义末尾不加分号；
5. 宏定义写在函数的花括号外边，作用域为其后的程序，通常在文件的最开头。
6. 可以用#undef命令终止宏定义的作用域
7. 宏定义允许嵌套
8. 字符串" "中永远不包含宏
9. 宏定义不分配内存，变量定义分配内存。
10. 宏定义不存在类型问题，它的参数也是无类型的。

1. #，宏把#的内容当做一个字符串替换
#define CAT(c) "123"#c ---> CAT(abc) "123""abc" ===> "123abc"
#define FDR(c) #c ---> FDR(a) ===> "a"

2. ##，用于把两侧的参数合并为一个符号
#define combine(a, b, c) a##b##c ---> combine(1, 2, 3) ===> "123"
#define WIDE(str) L##str ---> WIDE("adb") ===> L"abc"

17.3：条件编译

条件编译：只有在符合条件下，代码才能编译进程序。

预编译格式：

1.
#ifdef  标识符
  程序段1
#else
  程序段2
#endif

2.
#ifndef  标识符
  程序段1
#else
  程序段2
#endif

3.
#if 常量表达式
    程序段1
#else 
    程序段2
#endif

4.
#if 表达式1
    语句段1
#elif 表达式2
    语句段2
#else
    语句段3
#endif

18：递归

递归：指某个函数直接或间接的调用自身；

18.1：递归定义

如果确定递归：

1. 递归首先需要有一个或者多个递归出口(即递归终止的条件) ，也就是最小子问题的求解
2. 递归需要一个递归式，这个递归式规定如何将原问题划分成子问题(子问题解决的对象和原问题解决的对象性质一样)

//阶乘
int fact(unsigned int  n) {
    if(n==0)
        return 1;//递归出口
    return n*fact(n-1);//n*Fact(n-1)就是递归式,将求n的阶乘，转化为子问题求n-1的阶乘
}

int main(void) {
     printf("10!=%d\n", fact(10));
     return 0;
}

//斐波那契数列
//斐波那契数列指的是这样一个数列  1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...这个数列从第三项开始，每一项都等于前两项之和。
因此可以写出它的递归函数与递归出口：
/*
f(1) = 1;
f(2) = 1;
f(n) = f(n-1) + f(n-2) n > 2
最简子问题（递归出口）：f(1),f(2)
子问题转化：f(n)=f(n-1)+f(n-2) n>2
*/

unsigned long feibo(unsigned int n) {
    if (n==1 || n==2) {
        return 1;
    } else {
        return feibo(n-1) + feibo(n-2);
    }
}

递归的优缺点：

1. 递归的时间复杂度和对应的非递归差不多，但递归的效率是低不少(主要原因：反复函数调用和进栈出栈，各种终端等机制)。递归嵌套过甚过多消耗栈内存，回造成栈溢出。
2. 内核开发不能使用递归，因为栈只有几K

18.2：递归的应用

//1. 不允许使用任何全局或局部变量编写 int strlen(char *s)，计算字符串的长度
size_t strlen(const char *s) {
    if(s==NULL || *s==’\0’) {
        return 0;
    }

    return 1+strlen(s+1);
}

size_t strlen(const char* s) {
    return (s==NULL||*s==’\0’)?0:1+strlen(s+1);
}

//2. 请反向的输出一个字符串：比如”hello, world!”，打印出来是：”!dlrow, olleh”。
void inverse_print(char *s) {
    if(*s=='\0'||s==NULL )
         return;

    inverse_print(s+1);//先递归反向打印s的子串s+1

    printf( "%c", *s);
}

//3. 字符串逆置
void reverse_str(char *str，size_t len) {
    if(str==NULL || len==1||len==0)
        return;

    reverse_str(str+1,len-2);//先逆置子串
    char tmp=*str;//再交换主串最左边与最右边的字符
    *str=*(str+len-1)
    *(st+len-1)=tmp;
}