二進(jìn)制與編碼江蘇省句容高級中學(xué)

二進(jìn)制與編碼江蘇省句容高級中學(xué)2011信息學(xué)奧賽基礎(chǔ)知識（進(jìn)制與編碼）一、進(jìn)制轉(zhuǎn)換四種常用的數(shù)制及它們之間的相互轉(zhuǎn)換：進(jìn)制基數(shù)符號基數(shù)個數(shù)權(quán)進(jìn)數(shù)規(guī)律十進(jìn)制0、1、2、3、4、5、6、7、8、9D1010i逢十進(jìn)一二進(jìn)制0、1B22i逢二進(jìn)一八進(jìn)制0、1、2、3、4、5、6、7O88i逢八進(jìn)一十六進(jìn)制0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、FH1616i逢十六進(jìn)一二進(jìn)制數(shù)、八進(jìn)制數(shù)、十六進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)的方法：按權(quán)展開求和法十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)、八進(jìn)制數(shù)、十六進(jìn)制數(shù)的方法：整數(shù)部分短除法—逆向取余，小數(shù)部分—正向取整1．二進(jìn)制與十進(jìn)制間的相互轉(zhuǎn)換：（1）二進(jìn)制轉(zhuǎn)十進(jìn)制方法：“按權(quán)展開求和”例：（1011.01）2＝（1×23＋0×22＋1×21＋1×20＋0×2－1＋1×2－2）10＝（8＋0＋2＋1＋0＋0.25）10＝（11.25）10規(guī)律：個位上的數(shù)字的次數(shù)是0，十位上的數(shù)字的次數(shù)是1，......，依次遞增，而十分位的數(shù)字的次數(shù)是-1，百分位上數(shù)字的次數(shù)是-2，......，依次遞減。注意：不是任何一個十進(jìn)制小數(shù)都能轉(zhuǎn)換成有限位的二進(jìn)制數(shù)。（2）十進(jìn)制轉(zhuǎn)二進(jìn)制十進(jìn)制整數(shù)轉(zhuǎn)二進(jìn)制數(shù)：“除以2取余，逆序排列”（短除反取余法）例：（89）10＝（1011001）2289244 ……1222 ……0211 ……025 ……122 ……121 ……00 ……1十進(jìn)制小數(shù)轉(zhuǎn)二進(jìn)制數(shù)：“乘以2取整，順序排列”（乘2順取整法）2．八進(jìn)制與二進(jìn)制的轉(zhuǎn)換：二進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)：從小數(shù)點開始，整數(shù)部分向左、小數(shù)部分向右，每3位為一組用一位八進(jìn)制數(shù)的數(shù)字表示，不足3位的要用“0”補足3位，就得到一個八進(jìn)制數(shù)。八進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)：把每一個八進(jìn)制數(shù)轉(zhuǎn)換成3位的二進(jìn)制數(shù)，就得到一個二進(jìn)制數(shù)。例：將八進(jìn)制的37.416轉(zhuǎn)換成二進(jìn)制數(shù)：4、補碼加減法計算機中實際上只有加法，減法運算轉(zhuǎn)換成加法運算進(jìn)行，乘法運算轉(zhuǎn)換成加法運算進(jìn)行，除法運算轉(zhuǎn)換成減法運算進(jìn)行。用補碼可以很方便的進(jìn)行這種運算。1、補碼加法[X+Y]補=[X]補+[Y]補【例7】X=+0110011,Y=-0101001，求[X+Y]補[X]補=00110011[Y]補=11010111[X+Y]補=[X]補+[Y]補=00110011+11010111=00001010注：因為計算機中運算器的位長是固定的，上述運算中產(chǎn)生的最高位進(jìn)位將丟掉，所以結(jié)果不是100001010，而是00001010。2、補碼減法[X-Y]補=[X]補-[Y]補=[X]補+[-Y]補其中[-Y]補稱為負(fù)補，求負(fù)補的方法是：對補碼的每一位（包括符號位）求反，最后末位加“1”【例8】X=+0111001,Y=+1001101，求[X-Y]補[X]補=00111001[Y]補=01001101[-Y]補=10110011[X-Y]補=[X]補+[-Y]補=00111001+10110011=111011005、數(shù)的表示范圍通過上面的學(xué)習(xí)，我們就可以知道計算機如果用一個字節(jié)表示一個整數(shù)的時候，如果是無符號數(shù)，可以表示0~255共256個數(shù)（00000000~11111111），如果是有符號數(shù)則能表示-128~127共256個數(shù)（10000000~01111111）。如果兩個字節(jié)表示一個整數(shù)，則共有65536個數(shù)可以表示，大部分程序設(shè)計語言中整數(shù)的范圍都是-32768~32767的原因，可以看出這種整數(shù)類型是16位的有符號數(shù)，而且是補碼表示的。帶符號數(shù)的機器碼表示方法，n位范圍是-2n-1到2n-1-1。下表列出的8位二進(jìn)制原碼，反碼和補碼并將補碼用十六進(jìn)制表示。真值原碼（B）反碼（B）補碼（B）補碼（H）+1270111111101111111011111117F+3900100111001001110010011127+000000000000000000000000000-010000000111111110000000000-39101001111101100011011001D9-12711111111100000001000000181-128無法表示無法表示1000000080從上可看出，真值+0和-0的補碼表示是一致的，但在原碼和反碼表示中具有不同形式。8位補碼機器數(shù)可以表示-128，但不存在+128的補碼與之對應(yīng)，由此可知，8位二進(jìn)制補碼能表示數(shù)的范圍是-128——+127。還要注意，不存在-128的8位原碼和反碼形式。三、奇偶校驗計算機中數(shù)據(jù)在進(jìn)行存儲和傳輸過程中可能會發(fā)生錯誤。為了及時發(fā)現(xiàn)和糾正這類錯誤，在數(shù)據(jù)傳輸（存儲）過程中要進(jìn)行校驗，常用的校驗方法就是奇偶校驗。奇偶校驗?zāi)馨l(fā)現(xiàn)一位或奇數(shù)位錯誤，且不能糾正錯誤。一般以字節(jié)（八位二進(jìn)制）為單位加1位奇偶校驗位。奇偶校驗分奇校驗和偶校驗兩種。奇校驗：一個字節(jié)前面加一位校驗位使得“1”的個數(shù)保持為奇數(shù)，若八位二進(jìn)制數(shù)中“1”的個數(shù)為偶數(shù)，則校驗位為“1”；若八位二進(jìn)制數(shù)中“1”的個數(shù)為奇數(shù)，則校驗位為“0”?！纠?】給1001100101101101加奇校驗結(jié)果為110011001001101101偶校驗：一個字節(jié)前面加一位校驗位使得“1”的個數(shù)保持為偶數(shù)，若八位二進(jìn)制數(shù)中“1”的個數(shù)為偶數(shù)，則校驗位為“0”；若八位二進(jìn)制數(shù)中“1”的個數(shù)為奇數(shù)，則校驗位為“1”?！纠?】給1001100101101101加偶校驗結(jié)果為010011001101101101四、信息存貯（一）定點數(shù)（Fixed-PointNumber）計算機處理的數(shù)據(jù)不僅有符號，而且大量的數(shù)據(jù)帶有小數(shù)，小數(shù)點不占有二進(jìn)制一位而是隱含在機器數(shù)里某個固定位置上（實際不存在）。通常采取兩種簡單的約定：一種是約定所有機器數(shù)的小數(shù)的小數(shù)點位置隱含在機器數(shù)的最低位之后，叫定點純整機器數(shù)，簡稱定點整數(shù)。另一種約定所有機器數(shù)的小數(shù)點隱含在符號位之后、有效部分最高位之前，叫定點純小數(shù)機器數(shù)，簡稱定點小數(shù)。無論是定點整數(shù)，還是定點小數(shù)，都可以有原碼、反碼和補碼三種形式。（二）浮點數(shù)（Floating-PointNumber）計算機多數(shù)情況下采用作浮點數(shù)表示數(shù)值，它與科學(xué)計數(shù)法相似，把一個二進(jìn)制數(shù)通過移動小數(shù)點位置表示成階碼和尾數(shù)兩部分： 其中：E——N的階碼（Expoent），是有符號的整數(shù) S——N的尾數(shù)（Mantissa），是數(shù)值的有效數(shù)字部分，一般規(guī)定取二進(jìn)制定點純小數(shù)形式。例：1011101B=2+7*0.1011101，101.1101B=2+3*0.1011101，0.01011101B=2-1*0.1011101 浮點數(shù)的格式如下：E0E1E2……………En

E0E1E2……………En階符階尾符尾數(shù)浮點數(shù)由階碼和尾數(shù)兩部分組成，底數(shù)2不出現(xiàn)，是隱含的。階碼的正負(fù)符號E0，在最前位，階反映了數(shù)N小數(shù)點的位置，常用補碼表示。二進(jìn)制數(shù)N小數(shù)點每左移一位，階增加1。尾數(shù)是這點小數(shù)，常取補碼或原碼，碼制不一定與階碼相同，數(shù)N的小數(shù)點右移一位，在浮點數(shù)中表現(xiàn)為尾數(shù)左移一位。尾數(shù)的長度決定了數(shù)N的精度。尾數(shù)符號叫尾符，是數(shù)N的符號，也占一位。例：寫出二進(jìn)制數(shù)-101.1101B的浮點數(shù)形式，設(shè)階碼取4位補碼，尾數(shù)是8位原碼。-101.1101=-0.1011101*2+3浮點形式為：階碼0011尾數(shù)11011101補充解釋：階碼0011中的最高位“0”表示指數(shù)的符號是正號，后面的“011”表示指數(shù)是“3”；尾數(shù)11011101的最高位“1”表明整個小數(shù)是負(fù)數(shù)，余下的1011101是真正的尾數(shù)。例：計算機浮點數(shù)格式如下，寫出x=0.0001101B的規(guī)格化形式，階碼是補碼，尾數(shù)是原碼。x=0.0001101=0.1101*10-3又[-3]補=[-001B]補=[1011]補=1101B110101101000所以浮點數(shù)形式是‘0‘0’―48

‘A’―65

‘a(chǎn)’―漢字信息編碼1．漢字輸入碼（外碼）漢字輸入方法大體可分為：區(qū)位碼（數(shù)字碼）、音碼、形碼、音形碼?！^(qū)位碼：優(yōu)點是無重碼或重碼率低，缺點是難于記憶；·音碼：優(yōu)點是大多數(shù)人都易于掌握，但同音字多，重碼率高，影響輸入的速度；·形碼：根據(jù)漢字的字型進(jìn)行編碼，編碼的規(guī)則較多，難于記憶，必須經(jīng)過訓(xùn)練才能較好地掌握；重碼率低；·音形碼：將音碼和形碼結(jié)合起來，輸入漢字，減少重碼率，提高漢字輸入速度。2．漢字交換碼漢字交換碼是指不同的具有漢字處理功能的計算機系統(tǒng)之間在交換漢字信息時所使用的代碼標(biāo)準(zhǔn)。自國家標(biāo)準(zhǔn)GB2312－80公布以來，我國一直沿用該標(biāo)準(zhǔn)所規(guī)定的國標(biāo)碼作為統(tǒng)一的漢字信息交換碼。GB2312－80標(biāo)準(zhǔn)包括了6763個漢字，按其使用頻度分為一級漢字3755個和二級漢字3008個。一級漢字按拼音排序，二級漢字按部首排序。此外，該標(biāo)準(zhǔn)還包括標(biāo)點符號、數(shù)種西文字母、圖形、數(shù)碼等符號682個。由于GB2312－80是80年代制定的標(biāo)準(zhǔn)，在實際應(yīng)用時常常感到不夠，所以，建議處理文字信息的產(chǎn)品采用新頒布的GB18030信息交換用漢字編碼字符集，這個標(biāo)準(zhǔn)繁、簡字均處同一平臺，可解決兩岸三地間GB碼與BIG5碼間的字碼轉(zhuǎn)換不便的問題。3．字形存儲碼字形存儲碼是指供計算機輸出漢字（顯示或打印）用的二進(jìn)制信息，也稱字模。通常，采用的是數(shù)字化點陣字模。一般的點陣規(guī)模有16×16，24×24，32×32，64×64等，每一個點在存儲器中用一個二進(jìn)制位（bit）存儲。例如，在16×16的點陣中，需16×16bit=32byte的存儲空間。在相同點陣中，不管其筆劃繁簡，每個漢字所占的字節(jié)數(shù)相等。為了節(jié)省存儲空間，普遍采用了字形數(shù)據(jù)壓縮技術(shù)。所謂的矢量漢字是指用矢量方法將漢字點陣字模進(jìn)行壓縮后得到的漢字字形的數(shù)字化信息。五、運算法則二進(jìn)制的算術(shù)運算1、加法運算規(guī)則：0+0=00+1=11+0=11+1=102、減法運算規(guī)則：0-0=00-1=1（向高位借1）1-0=11-1=03、乘法運算規(guī)則：0×0=00×1=01×0=01×1=1Pascal的運算符表達(dá)式是用運算符號或小括號將常量、變量、函數(shù)連接成的式子。Pascal表達(dá)式中只有小括號。運算符也稱為算符，算符的操作對象稱為操作數(shù)。運算符按帶操作數(shù)的個數(shù)分為兩類：單目運算符：對一個操作數(shù)操作。-（負(fù)號），+（正號）雙目運算符：對兩個操作數(shù)操作。根據(jù)運算符運算的意義不同分為算術(shù)運算、布爾運算、邏輯運算、關(guān)系運算。根據(jù)運算符的優(yōu)先級可以將運算符分為單目運算、“乘”的關(guān)系運算、“和”的關(guān)系運算、關(guān)系運算。算術(shù)運算符一共有8個。操作數(shù)都是數(shù)值型，結(jié)果也是數(shù)值型。單目運算符有（＋）取正、（－）取負(fù)。雙目運算符有（＋）加、（－）減、（＊）乘、（/）除、（DIV）取商、（Mod）取余。“/”左右的操作數(shù)是數(shù)值型，結(jié)果是實型數(shù)。Div左右的操作數(shù)是整型，結(jié)果是整型（兩數(shù)之商）。Mod左右的操作數(shù)是整型數(shù)，結(jié)果是整型數(shù)（兩數(shù)相除之余）。在PASCAL只有上面8種數(shù)學(xué)運算。其它的就只能利用這8種運算的組合通過語句來實現(xiàn)。如a^2（a的平方）可以化成a*a。XY可寫成exp(y*ln(X))關(guān)系運算符系運算是指同一類型的兩個數(shù)據(jù)進(jìn)行比較，結(jié)果是一個布爾類型值。用小括號、>、<、>=、<=、=、<>將兩個算術(shù)表達(dá)式連接起來的式子就稱為關(guān)系表達(dá)式（比較式）。如：3+7>8,x+y<10,2*7<=13等都是關(guān)系表達(dá)式。布爾運算符布爾運算是對布爾型數(shù)據(jù)進(jìn)行運算，即操作數(shù)都是布爾型數(shù)據(jù)，結(jié)果是布爾型。布爾型運算符共有4個：not(取反)and(與)or(或)xor(異或)not：結(jié)果是與操作數(shù)相反的布爾值and：兩個操作數(shù)都為真，結(jié)果為真，否則為假or：兩個操作有一個為真，結(jié)果為真，否則為假Xor:兩個操作數(shù)不一樣為真,否則為假運算符的優(yōu)先級內(nèi)層小括號先計算函數(shù)先求值單目運算符（＋,－,not）乘的關(guān)系雙目運算符（*,/,div,mod,and）加的關(guān)系雙目運算符（＋,－,or）關(guān)系運算符（<,<=,>,>=,=,<>）在同級運算中，按從左到右的順序計算位運算

程序中的所有數(shù)在計算機內(nèi)存中都是以二進(jìn)制的形式儲存的。位運算說穿了，就是直接對整數(shù)在內(nèi)存中的二進(jìn)制位進(jìn)行操作。比如，and運算本來是一個邏輯運算符，但整數(shù)與整數(shù)之間也可以進(jìn)行and運算。舉個例子，6的二進(jìn)制是110，11的二進(jìn)制是1011，那么6and11的結(jié)果就是2，它是二進(jìn)制對應(yīng)位進(jìn)行邏輯運算的結(jié)果（0表示False，1表示True，空位都當(dāng)0處理）：

按位與參與運算的量，如果相對應(yīng)的兩位都為1，則該位的結(jié)果值為1，否則為0，即：0and0=00and1=01and0=01and1=1a0001001000110100andb0000000011111111c0000000000110100按位或參與運算的量，如果相對應(yīng)的兩位都為0，則該位的結(jié)果值為0，否則為1，即：0or0=00or1=11or0=11or1=1a0001001000110100orb0000000011111111c0001001011111111按位異或如果相對應(yīng)的兩位相異，則該位的結(jié)果為1，否則為0，即：0xor