·?二進(jìn)制補(bǔ)碼基礎(chǔ)

補(bǔ)碼用于在計(jì)算機(jī)內(nèi)表示負(fù)數(shù)， 負(fù)數(shù) 2的補(bǔ)碼表示法可以將加法運(yùn)算規(guī)則， 擴(kuò)展到整個(gè)整數(shù)集。

· 機(jī)器數(shù)：帶符號(hào)的二進(jìn)制碼字 ，比如，十進(jìn)制中的數(shù) +3 ，計(jì)算機(jī)字長(zhǎng)為8位，轉(zhuǎn)換成二進(jìn)制就是0000 0011。如果是 -3 ，就是 1111 1101 。那么，這里的 00000011 和 1111 1101 就是機(jī)器數(shù)。 機(jī)器數(shù)包含了符號(hào)和數(shù)值部分。

·真值：帶符號(hào)位的機(jī)器數(shù)對(duì)應(yīng)的真正數(shù)值，比如 -3，+3

·在計(jì)算機(jī)內(nèi)，有符號(hào)數(shù)有3種表示法：原碼、反碼和補(bǔ)碼。

? ???[+1] = [ 00000001 ]原碼 = [ 00000001 ]反碼 =?[ 00000001 ]補(bǔ)碼 ；?

? ? ?[-1]? = [ 10000001 ]原碼?= [ 11111110 ]反碼 = [11111111]補(bǔ)碼

????原碼第一位是符號(hào)位, 所以若是8位二進(jìn)制數(shù)，其取值范圍就是: [1111 1111 , 0111 1111]? 即[-127 , 127]?

? ??反碼表示法規(guī)定：正數(shù)的反碼與其原碼相同；負(fù)數(shù)的反碼是對(duì)其原碼逐位取反，但符號(hào)位除外。?

? ? 補(bǔ)碼：正數(shù)原碼一致，負(fù)數(shù)反碼加1，如-8= 0-8 （(１１１１１１１１-００００１０００)反碼??＋０００００００１）加1?=１１１１１０００?

C語(yǔ)言中變量以補(bǔ)碼形式存放在內(nèi)存中，正數(shù)的補(bǔ)碼與原碼相同，負(fù)數(shù)求補(bǔ)碼方式為（符號(hào)位不變，其余各位取反，最后末尾加1）；

32位機(jī)器：int 32位，short 16位。

x = 127，正數(shù)，原碼：0111 1111，補(bǔ)碼：0111 1111，擴(kuò)展到32位高位補(bǔ)0，結(jié)果為0000007FH;?

Y = -9，? 負(fù)數(shù)，原碼：1000 1001，補(bǔ)碼：1111 0111，擴(kuò)展到16位高位補(bǔ)1，結(jié)果為FFF7H；

z = x + y = 118，原碼：0111 0110，補(bǔ)碼：0111 0110，擴(kuò)展到32位高位補(bǔ)0，結(jié)果為00000076H。? 注意：擴(kuò)展時(shí)，符號(hào)位不變。

·?哈夫曼編碼

在處理字符串序列時(shí)，如果對(duì)每個(gè)字符串采用相同的二進(jìn)制位表示，則稱這種編碼方式為定長(zhǎng)編碼。若允許對(duì)不同的字符采用不等長(zhǎng)的二進(jìn)制位進(jìn)行表示，那么這種方式稱為可變長(zhǎng)編碼?？勺冮L(zhǎng)編碼其特點(diǎn)是對(duì)使用頻率高的字符采用短編碼，而對(duì)使用頻率低的字符則采用長(zhǎng)編碼的方式。這樣我們就可減少數(shù)據(jù)的存儲(chǔ)空間，從而起到壓縮數(shù)據(jù)的效果。而通過(guò)哈夫曼樹形成的哈夫曼編碼是一種有效的數(shù)據(jù)壓縮編碼。?

·?KMP算法及next數(shù)組求解

對(duì)于正常的字符串模式匹配，主串長(zhǎng)度為m，子串為n，時(shí)間復(fù)雜度會(huì)到達(dá)O（m*n），空間復(fù)雜度為O（1），而如果用KMP算法，復(fù)雜度將會(huì)減少線型時(shí)間O（m+n），由于涉及到next數(shù)組的存儲(chǔ)，空間復(fù)雜度O（n）。

· next數(shù)組求解：以從1開始，next[1]=0,next[2]=1,next[n] ：將前面n-1個(gè)字符，計(jì)算從首尾開始組成最大的相同子串的長(zhǎng)度，如果找到，那么next值是該長(zhǎng)度加1，否則next值是1。

· kmp及next數(shù)組實(shí)現(xiàn)：代碼

· 錯(cuò)題總結(jié)：

1、strlen：字符串長(zhǎng)度，不包含‘結(jié)束符\0’? ? ? ? 轉(zhuǎn)義字符：\\=\ ; \123=S; \t=Tab鍵； \0表示后面字符為八進(jìn)制，‘\09’為非法字符。

2、 廣義表L=(A,B,C),表頭是A，表尾是（B,C) 。tail()表示取字符串的尾部，head()表示取字符串的頭。

3、 printf("格式控制字符串"， 輸出列表)；printf("%s", string);? putchar（字符數(shù)據(jù)）char? a_c=‘h’；putchar（a_c）；puts（字符串）； puts（“hello girl”）? ；

4、?結(jié)構(gòu)體內(nèi)存原則： 對(duì)齊原則：每一成員需對(duì)齊為后一成員類型的倍數(shù)// 補(bǔ)齊原則：最終大小補(bǔ)齊為成員類型最大值的倍數(shù)

5、 %s格式輸出直到'\0'的字符串，字符串尾數(shù)字0為‘\0’結(jié)束符，%c對(duì)應(yīng)的是單個(gè)字符,%d是十進(jìn)制整數(shù)型輸出。

6、65536?相當(dāng)于?unsigned?short??的0值。如 65537：1 00000000 00000001，(2字節(jié))short i = 65537時(shí)，發(fā)生了溢出取16bit，為1。

7、單線程運(yùn)行效率： String<< StringBuffer（ 線程安全 ）< StringBuilder（ 非線程安全 ）?