16：位運(yùn)算
16.1：位運(yùn)算概述
二進(jìn)制與位運(yùn)算
程序中的數(shù)據(jù)在內(nèi)存中，都是以二進(jìn)制的形式存在的闪湾。內(nèi)存中的數(shù)據(jù)都是0和1組成的序列冲甘。
位運(yùn)算：是直接對(duì)整數(shù)在內(nèi)存中的二進(jìn)制位進(jìn)行操作；直接對(duì)二進(jìn)制位進(jìn)行操作途样，使得位運(yùn)算比普通的運(yùn)算操作效率要高
學(xué)習(xí)位運(yùn)算江醇，首先要學(xué)習(xí)什么是二進(jìn)制位？
1. byte字節(jié)
2. bit位
位運(yùn)算操作符：
1. 與(and)：&
2. 或(or)：|
3. 取反(not)：~
4. 異或(xor)：^
5. 左移(shl)：<<
6. 右移(shr/sar)：>>
16.2：與(and)：&
與運(yùn)算：只有當(dāng)2個(gè)數(shù)對(duì)應(yīng)的位都為1何暇，該位運(yùn)算結(jié)果為1嫁审，否則運(yùn)算結(jié)果為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;
}
&應(yīng)用：
//1. 獲取一個(gè)整數(shù)的后n位:(如現(xiàn)實(shí)中子網(wǎng)掩碼)
獲取一個(gè)整數(shù)的后3位:
int a=100;
a&7(7的二進(jìn)制碼為0111)
2. 使用與運(yùn)算與取反和移位運(yùn)算相結(jié)合赖晶，將整數(shù)的某位置零:
a&(~(1<<n))//即可將x第n位置為零
#define CLEARFLAG(a, n) ((a) &= ~(1<<(n)))//把整數(shù)a中第n位置為0
3. 判斷a中第n位是否為1:
#define FLAGON(a,n) ((a)&(1<<(n)))//判斷整數(shù)a中第n位是否為1
4. 請(qǐng)出整數(shù)a二進(jìn)制中最右邊的1：
a&(a-1)
//計(jì)算整數(shù)有幾個(gè)二進(jìn)制1
int count_ones(int x) {
int count = 0;
while(x) {
count++;
x &= (x-1);
}
return count
}
16.3：或(or)：|
|：只有當(dāng)2個(gè)數(shù)對(duì)應(yīng)的位都為0，該位運(yùn)算結(jié)果為0辐烂，否則運(yùn)算結(jié)果為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;
}
|應(yīng)用：
//把整數(shù)a中的第n位置為1
#define SETFLAG(a,n) ((a) |= (1<<(n)))
16.4：取反(not)：~
~：?jiǎn)文窟\(yùn)算符；是將一個(gè)整數(shù)中位為1的變成0纠修，位為0的變成1胳嘲。
int main(void) {
int a = 10;//1010
int b = ~10;//0101
printf(“~10=%d\n”, b);//5
return 0;
}
~應(yīng)用：
1.
//取反運(yùn)算同與運(yùn)算結(jié)合，可以將一個(gè)整數(shù)的某位置0扣草，比如：
#define CLEARFLAG(a,n) ((a) &= ~(1<<(n)))//把整數(shù)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;
}
//異或運(yùn)算：
1. 置零
a^0=a
a^a=0//xor eax,eax
2. 兩數(shù)交換
#define SWAP(a,b) \
do{\
a=a^b;\
b=a^b;\
a=a^b;\
}while(0)
/*
證明：
假設(shè)：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
因此，通過(guò)上面的推導(dǎo)鹰祸，實(shí)現(xiàn)了a與b值的交換甫窟。
*/
3. 單指針實(shí)現(xiàn)雙鏈表
/*
可以用單個(gè)指針域來(lái)表示雙向鏈表：
有任意3個(gè)相鄰結(jié)點(diǎn)：PL， P蛙婴， PR
那么P->next = PL^PR
對(duì)于頭結(jié)點(diǎn)來(lái)說(shuō)：P沒(méi)有左邊的結(jié)點(diǎn)粗井，所以左結(jié)點(diǎn)為NULL
所以Head->next = NULL^PR
對(duì)于尾結(jié)點(diǎn)來(lái)說(shuō)：
尾結(jié)點(diǎn)沒(méi)有右邊的結(jié)點(diǎn)，所以PR為NULL
Tail->next = PL^NULL
按照上述規(guī)則生成鏈表之后街图，遍歷方法如下：
從左往右遍歷鏈表：
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：移位運(yùn)算左移(shl)：<<
<<：左移運(yùn)算符浇衬；將一個(gè)數(shù)a向左移動(dòng)n位記為：a<<n
將一個(gè)數(shù)左移N位相當(dāng)于將一個(gè)數(shù)乘以2^N
int main(void) {
int a = 10;
int b = a<<2;
printf(“b=%d\n”, b);//40
return 0;
}
16.7：移位運(yùn)算右移(shr/sar)：>>
>>：右移運(yùn)算符；將一個(gè)數(shù)a向右移動(dòng)n位記為：a>>n餐济。
右移動(dòng)運(yùn)算分為兩種右移：
- 邏輯右移耘擂，在移動(dòng)過(guò)程中，左邊位用0填充絮姆。（有符號(hào)數(shù)：10000011醉冤，對(duì)于邏輯右移，向右移動(dòng)3位滚朵，那么左邊用0填充冤灾，變成了：00010000。）
- 算術(shù)右移辕近，在移動(dòng)過(guò)程中韵吨，左邊用符號(hào)位來(lái)填充。（算術(shù)右移移宅，向右移動(dòng)3位归粉，那么左邊用1（1為符號(hào)位）填充，變成了11110000漏峰。而對(duì)于01000011糠悼，算術(shù)右移3位，那么左邊用0（0為符號(hào)位）填充浅乔，變成了00001000倔喂。）
在C語(yǔ)言中，右移運(yùn)算符為算術(shù)右移運(yùn)算符靖苇，即左邊用符號(hào)位來(lái)填充席噩。對(duì)于無(wú)符號(hào)數(shù)，而將一個(gè)數(shù)右移N位相當(dāng)于將這個(gè)數(shù)除以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補(bǔ)碼11111111 11111111 11111111 11111101(加一)
printf("a的16進(jìn)制:%x\n", a);//0Xfffffffd
int b = 10;
int c = a>>2;//
//-3補(bǔ)碼11111111 11111111 11111111 11111101>>2
//c補(bǔ)碼11111111 11111111 11111111 11111111
//c反碼11111111 11111111 11111111 11111110(減一)
//c原碼10000000 00000000 00000000 00000001(即-1)
printf("c的16進(jìn)制:%x\n", c);//0Xffffffff
int d = b>>1;//10/2^1=5
printf("a>>2=%d, b>>1=%d\n", c, d);
*/
16.8：位運(yùn)算綜合應(yīng)用：
1. 將第n位置1或者清零（n是從零開(kāi)始計(jì)算的）：
//把整數(shù)a中的第n位置為1
#define SETFLAGE(a, n) ((a)|(1<<(n)))
//把整數(shù)a中的第n位置為0
#define CLEARFLAG(a, n) ((a)&(~(1<<(n))))
//判斷整數(shù)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. 對(duì)稱加密：XOR
異或性質(zhì)：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])
}
}
常見(jiàn)的位運(yùn)算：
image.png
位運(yùn)算在實(shí)際項(xiàng)目中的運(yùn)用
//先將該整數(shù)右移24位悼枢，與0xFF做與運(yùn)算，即獲得該8位的值脾拆。高8位記錄了對(duì)文件的修改標(biāo)記：
ulDisposition = (lpIrpStack->Parameters.Create.Options >> 24) & 0xFF;
//清除或者判斷某些標(biāo)志:
#define FlagOn(_F, _SF) ((_F)&(_SF))//查看_F是否包含_SF
mov eax, CRO
add eax, 0FFFEFFFFh//相當(dāng)于CR0 &= 0xFFFEFFFF;
mov CRO, eax
mov eax, CRO
or eax, NOT OFFFEFFFFh//CR0 |= ~0xFFFEFFFF
mov CRO, eax
17：宏定義
預(yù)處理->編譯->鏈接->可執(zhí)行文件（預(yù)處理將由預(yù)處理程序負(fù)責(zé)完成）馒索。
程序在編譯預(yù)處理的階段莹妒，不僅提供了宏定義的功能，還提供了文件包含以及條件編譯的功能绰上。
宏在編譯前預(yù)處理階段旨怠，就已經(jīng)完成了替換
17.1：宏的定義
- 宏定義：指用一個(gè)標(biāo)志符代表一個(gè)字符串，該標(biāo)志符就稱為宏名渔期。
- 宏展開(kāi)：在程序編譯預(yù)處理階段运吓，所有宏名將會(huì)被替換為宏定義中的字符串的操作。
其定義格式如下(/其標(biāo)識(shí)符疯趟，稱為宏名)：
//1. 不帶參數(shù)格式：#define 標(biāo)識(shí)符 字符串
//2. 帶參數(shù)的格式：#define 標(biāo)識(shí)符(參數(shù)表) 字符串
//例子：
#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);
}
宏定義的優(yōu)缺點(diǎn)：
#define PI 3.14
1. 有意義
2. 減少修改
3. 無(wú)類型檢查
4. 無(wú)法調(diào)試
(宏不是變量拘哨，也沒(méi)有類型，不占內(nèi)存)
const float pi=3.14f;
1. 有意義
2. 減少修改
3. 有類型
4. 可調(diào)試
帶參數(shù)的宏與函數(shù)的優(yōu)缺點(diǎn)比較：
1. 宏的效率要高(inline)信峻，沒(méi)有了函數(shù)調(diào)用過(guò)程中的進(jìn)棧出棧傳參拷貝和出棧棧平衡倦青；
2. 宏無(wú)法調(diào)試
3. 宏無(wú)法做到類型檢查
4. 傳參的計(jì)算也不同，宏是簡(jiǎn)單的替換盹舞；函數(shù)先計(jì)算产镐，再傳參。
如：
#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：宏的應(yīng)用與注意事項(xiàng)
- 宏名一般用大寫
- 使用宏可提高程序的通用性和易讀性踢步，減少不一致性癣亚，減少輸入錯(cuò)誤和便于修改。例如：數(shù)組大小常用宏定義
- 預(yù)處理是在編譯之前的處理获印，而編譯工作的任務(wù)之一就是語(yǔ)法檢查述雾，預(yù)處理不做語(yǔ)法檢查。
- 定義末尾不加分號(hào)兼丰；
- 宏定義寫在函數(shù)的花括號(hào)外邊玻孟，作用域?yàn)槠浜蟮某绦颍ǔＴ谖募淖铋_(kāi)頭鳍征。
- 可以用#undef命令終止宏定義的作用域
- 宏定義允許嵌套
- 字符串" "中永遠(yuǎn)不包含宏
- 宏定義不分配內(nèi)存黍翎，變量定義分配內(nèi)存。
- 宏定義不存在類型問(wèn)題艳丛，它的參數(shù)也是無(wú)類型的匣掸。
1. #，宏把#的內(nèi)容當(dāng)做一個(gè)字符串替換
#define CAT(c) "123"#c ---> CAT(abc) "123""abc" ===> "123abc"
#define FDR(c) #c ---> FDR(a) ===> "a"
2. ##氮双，用于把兩側(cè)的參數(shù)合并為一個(gè)符號(hào)
#define combine(a, b, c) a##b##c ---> combine(1, 2, 3) ===> "123"
#define WIDE(str) L##str ---> WIDE("adb") ===> L"abc"
17.3：條件編譯
條件編譯：只有在符合條件下旺聚，代碼才能編譯進(jìn)程序。
預(yù)編譯格式：
1.
#ifdef 標(biāo)識(shí)符
程序段1
#else
程序段2
#endif
2.
#ifndef 標(biāo)識(shí)符
程序段1
#else
程序段2
#endif
3.
#if 常量表達(dá)式
程序段1
#else
程序段2
#endif
4.
#if 表達(dá)式1
語(yǔ)句段1
#elif 表達(dá)式2
語(yǔ)句段2
#else
語(yǔ)句段3
#endif
18：遞歸
遞歸：指某個(gè)函數(shù)直接或間接的調(diào)用自身眶蕉；
18.1：遞歸定義
如果確定遞歸：
- 遞歸首先需要有一個(gè)或者多個(gè)遞歸出口(即遞歸終止的條件) ，也就是最小子問(wèn)題的求解
- 遞歸需要一個(gè)遞歸式唧躲，這個(gè)遞歸式規(guī)定如何將原問(wèn)題劃分成子問(wèn)題(子問(wèn)題解決的對(duì)象和原問(wèn)題解決的對(duì)象性質(zhì)一樣)
//階乘
int fact(unsigned int n) {
if(n==0)
return 1;//遞歸出口
return n*fact(n-1);//n*Fact(n-1)就是遞歸式,將求n的階乘造挽，轉(zhuǎn)化為子問(wèn)題求n-1的階乘
}
int main(void) {
printf("10!=%d\n", fact(10));
return 0;
}
//斐波那契數(shù)列
//斐波那契數(shù)列指的是這樣一個(gè)數(shù)列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...這個(gè)數(shù)列從第三項(xiàng)開(kāi)始碱璃，每一項(xiàng)都等于前兩項(xiàng)之和。
因此可以寫出它的遞歸函數(shù)與遞歸出口：
/*
f(1) = 1;
f(2) = 1;
f(n) = f(n-1) + f(n-2) n > 2
最簡(jiǎn)子問(wèn)題（遞歸出口）：f(1),f(2)
子問(wèn)題轉(zhuǎn)化：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);
}
}
遞歸的優(yōu)缺點(diǎn)：
- 遞歸的時(shí)間復(fù)雜度和對(duì)應(yīng)的非遞歸差不多饭入，但遞歸的效率是低不少(主要原因：反復(fù)函數(shù)調(diào)用和進(jìn)棧出棧嵌器，各種終端等機(jī)制)。遞歸嵌套過(guò)甚過(guò)多消耗棧內(nèi)存谐丢，回造成棧溢出爽航。
- 內(nèi)核開(kāi)發(fā)不能使用遞歸，因?yàn)闂Ｖ挥袔譑
18.2：遞歸的應(yīng)用
//1. 不允許使用任何全局或局部變量編寫 int strlen(char *s)乾忱，計(jì)算字符串的長(zhǎng)度
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. 請(qǐng)反向的輸出一個(gè)字符串：比如”hello, world!”讥珍，打印出來(lái)是：”!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;
}
