C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)第10章 位算

1、位運(yùn)算位運(yùn)算102l掌握基本位運(yùn)算的形式掌握基本位運(yùn)算的形式l掌握位運(yùn)算的一般性計(jì)算方法掌握位運(yùn)算的一般性計(jì)算方法 310.1 幾個(gè)基本概念幾個(gè)基本概念 l【問(wèn)題】我們知道任何信息在計(jì)算機(jī)中都是以【問(wèn)題】我們知道任何信息在計(jì)算機(jī)中都是以二進(jìn)制形式表示，而我們?nèi)粘Ｉ钪惺褂玫氖嵌M(jìn)制形式表示，而我們?nèi)粘Ｉ钪惺褂玫氖鞘M(jìn)制，由于位運(yùn)算是指進(jìn)行二進(jìn)制位的運(yùn)算，十進(jìn)制，由于位運(yùn)算是指進(jìn)行二進(jìn)制位的運(yùn)算，因此在學(xué)習(xí)位運(yùn)算之前我們有必要了解與回顧因此在學(xué)習(xí)位運(yùn)算之前我們有必要了解與回顧一下計(jì)算機(jī)內(nèi)數(shù)據(jù)組織與存儲(chǔ)形式。一下計(jì)算機(jī)內(nèi)數(shù)據(jù)組織與存儲(chǔ)形式。410.1.1 字節(jié)與位字節(jié)與位 l 字節(jié)字節(jié)（byte

2、）是計(jì)算機(jī)中的存儲(chǔ)單元。一個(gè)字節(jié)）是計(jì)算機(jī)中的存儲(chǔ)單元。一個(gè)字節(jié)可以存放一個(gè)英文字母或符號(hào)，一個(gè)漢字通常要可以存放一個(gè)英文字母或符號(hào)，一個(gè)漢字通常要用兩個(gè)字節(jié)來(lái)存儲(chǔ)。每一個(gè)字節(jié)都有自己的編號(hào)，用兩個(gè)字節(jié)來(lái)存儲(chǔ)。每一個(gè)字節(jié)都有自己的編號(hào)，叫做叫做“地址地址”。1個(gè)字節(jié)由個(gè)字節(jié)由8個(gè)二進(jìn)制位（位的英個(gè)二進(jìn)制位（位的英文是文是bit）構(gòu)成，每位的取值為）構(gòu)成，每位的取值為0或或1。最右端的那。最右端的那1位稱為位稱為“最低位最低位”，編號(hào)為，編號(hào)為0；最左端的那；最左端的那1位稱位稱為為“最高位最高位”，而且從最低位到最高位順序，依，而且從最低位到最高位順序，依次編號(hào)。次編號(hào)。7 6 5 4 3 2

3、 1 0510.1.1 字節(jié)與位字節(jié)與位l我們把若干字節(jié)組成一個(gè)單元，叫做我們把若干字節(jié)組成一個(gè)單元，叫做“字字”（word）。一個(gè)字可以存放一個(gè)數(shù)據(jù)或指令。）。一個(gè)字可以存放一個(gè)數(shù)據(jù)或指令。至于一個(gè)字由幾個(gè)字節(jié)組成，取決于計(jì)算機(jī)的至于一個(gè)字由幾個(gè)字節(jié)組成，取決于計(jì)算機(jī)的硬件系統(tǒng)。一般由硬件系統(tǒng)。一般由1個(gè)、個(gè)、2個(gè)或個(gè)或4個(gè)字節(jié)組成，個(gè)字節(jié)組成，所對(duì)應(yīng)的計(jì)算機(jī)也被稱為所對(duì)應(yīng)的計(jì)算機(jī)也被稱為“8位機(jī)、位機(jī)、16位機(jī)或位機(jī)或32位機(jī)位機(jī)”。目前微機(jī)以。目前微機(jī)以16位機(jī)或位機(jī)或32位機(jī)為主。位機(jī)為主。在本書中作為原理講述的是在本書中作為原理講述的是8位機(jī)。位機(jī)。610.1.2 原碼原碼 l把最高

4、位留做表示符號(hào)，其他把最高位留做表示符號(hào)，其他7位表示二進(jìn)制位表示二進(jìn)制數(shù)，這種編碼方式叫做數(shù)，這種編碼方式叫做原碼原碼。最高位為。最高位為“0”表表示正數(shù)，為示正數(shù)，為“1”表示負(fù)數(shù)。例如：表示負(fù)數(shù)。例如：l00000011表示表示 +3l10000011表示表示 - 3l顯然，這樣可以表示的數(shù)值范圍在顯然，這樣可以表示的數(shù)值范圍在+127到到-127之之間。間。l這種表示方法有一個(gè)缺陷，數(shù)值這種表示方法有一個(gè)缺陷，數(shù)值0會(huì)出現(xiàn)歧義：會(huì)出現(xiàn)歧義：l00000000表示表示 +0l10000000表示表示 - 0710.1.3 反碼反碼 l對(duì)于正數(shù)，反碼與原碼相同。例如：對(duì)于正數(shù)，反碼與原碼相

5、同。例如：l00000011表示表示 +3。l 所謂所謂“反碼反碼”是指與是指與“原碼原碼”在表示負(fù)數(shù)時(shí)相在表示負(fù)數(shù)時(shí)相反：符號(hào)位（最高位）為反：符號(hào)位（最高位）為“1”表示負(fù)數(shù)。但其余表示負(fù)數(shù)。但其余位的值相反。例如，位的值相反。例如，11111100表示表示-3。顯然，這。顯然，這樣可以表示的數(shù)值范圍在樣可以表示的數(shù)值范圍在+127到到-127之間。之間。l 這種表示方法仍然有一個(gè)缺陷，數(shù)值這種表示方法仍然有一個(gè)缺陷，數(shù)值0會(huì)出現(xiàn)歧會(huì)出現(xiàn)歧義：義：l00000000表示表示 +0l11111111表示表示 - 0810.1.4 補(bǔ)碼補(bǔ)碼 l對(duì)于對(duì)于正數(shù)正數(shù)，補(bǔ)碼與原碼相同。，補(bǔ)碼與原碼相同

6、。l0的補(bǔ)碼為的補(bǔ)碼為00000000。這樣，。這樣，0的表示唯一。的表示唯一。l對(duì)于對(duì)于負(fù)數(shù)負(fù)數(shù)，可以從原碼得到補(bǔ)碼。步驟如下：，可以從原碼得到補(bǔ)碼。步驟如下：l符號(hào)位不變符號(hào)位不變,其余各位取反；其余各位取反；l整個(gè)數(shù)加整個(gè)數(shù)加1。l已知補(bǔ)碼，求原碼：已知補(bǔ)碼，求原碼：l符號(hào)位不變符號(hào)位不變,其余各位取反其余各位取反l整個(gè)數(shù)加整個(gè)數(shù)加1。910.1.4 補(bǔ)碼補(bǔ)碼l例如，已知補(bǔ)碼為例如，已知補(bǔ)碼為11111001，求原碼。，求原碼。l符號(hào)位為符號(hào)位為“1”，表示是一個(gè)負(fù)數(shù)，所以該位不變，表示是一個(gè)負(fù)數(shù)，所以該位不變，仍為仍為“1”；l其余其余7位位1111001取反后為取反后為0000110

7、；再加；再加1，所以，所以是是10000111(-7)。l計(jì)算機(jī)中的數(shù)據(jù)都采用補(bǔ)碼。原因是計(jì)算機(jī)中的數(shù)據(jù)都采用補(bǔ)碼。原因是:l使用補(bǔ)碼，可以將符號(hào)位和其它位統(tǒng)一處理；同時(shí)，使用補(bǔ)碼，可以將符號(hào)位和其它位統(tǒng)一處理；同時(shí)，減法也可按加法來(lái)處理。如減法也可按加法來(lái)處理。如-3+4可以變成可以變成-3的補(bǔ)碼的補(bǔ)碼與與+4的補(bǔ)碼相加的補(bǔ)碼相加l兩個(gè)用補(bǔ)碼表示的數(shù)相加時(shí)，如果最高位（符號(hào)位）兩個(gè)用補(bǔ)碼表示的數(shù)相加時(shí)，如果最高位（符號(hào)位）有進(jìn)位，則進(jìn)位被舍棄。有進(jìn)位，則進(jìn)位被舍棄。 1010.2 位運(yùn)算符和位運(yùn)算位運(yùn)算符和位運(yùn)算 l位運(yùn)算表位運(yùn)算表1110.2.1 按位取反按位取反 l【運(yùn)算符】【運(yùn)算符】【

8、格式】【格式】x【功能】各位翻轉(zhuǎn)，即原來(lái)為【功能】各位翻轉(zhuǎn)，即原來(lái)為1的位變成的位變成0，原，原來(lái)為來(lái)為0的位變成的位變成1?！局饕猛尽块g接地構(gòu)造一個(gè)數(shù)，以增強(qiáng)程序【主要用途】間接地構(gòu)造一個(gè)數(shù)，以增強(qiáng)程序的可移植性。的可移植性?！臼纠咳纭臼纠咳鐇=83，y=x，則，則y=172。83(01010011) 83(01010011) 172(10101100) 1210.2.2 按位與按位與 【運(yùn)算符】【運(yùn)算符】&【格式】【格式】x&y【功能】當(dāng)兩個(gè)操作對(duì)象二進(jìn)制數(shù)的相同位都為【功能】當(dāng)兩個(gè)操作對(duì)象二進(jìn)制數(shù)的相同位都為1時(shí)，時(shí)，結(jié)果數(shù)值的相應(yīng)位為結(jié)果數(shù)值的相應(yīng)位為1，否則為相

9、應(yīng)位是，否則為相應(yīng)位是0?！局饕猛尽咳　局饕猛尽咳?或保留或保留)1個(gè)數(shù)的某個(gè)數(shù)的某(些些)位，其余各位置位，其余各位置0。【示例】如【示例】如x=146，y=222，z=x&y，則，則z=146。1310.2.3 按位或按位或 【運(yùn)算符】【運(yùn)算符】|【格式】【格式】x | y【功能】當(dāng)兩個(gè)操作對(duì)象二進(jìn)制數(shù)的相同位都為【功能】當(dāng)兩個(gè)操作對(duì)象二進(jìn)制數(shù)的相同位都為0時(shí)，時(shí)，結(jié)果數(shù)值的相應(yīng)位為結(jié)果數(shù)值的相應(yīng)位為0，否則為相應(yīng)位是，否則為相應(yīng)位是1?！局饕猛尽繉ⅰ局饕猛尽繉?個(gè)數(shù)的某個(gè)數(shù)的某(些些)位置位置1，其余各位不變。，其余各位不變?！臼纠咳纭臼纠咳鐇=146，y=222，z

10、=x | y，則，則z=222。1410.2.4 按位異或按位異或 【運(yùn)算符】【運(yùn)算符】【格式】【格式】x y【功能】當(dāng)兩個(gè)操作對(duì)象二進(jìn)制數(shù)的相同位的值相同時(shí)，【功能】當(dāng)兩個(gè)操作對(duì)象二進(jìn)制數(shù)的相同位的值相同時(shí)，結(jié)果數(shù)值的相應(yīng)位為結(jié)果數(shù)值的相應(yīng)位為0，否則為相應(yīng)位是，否則為相應(yīng)位是1。【主要用途】使【主要用途】使1個(gè)數(shù)的某個(gè)數(shù)的某(些些)位翻轉(zhuǎn)位翻轉(zhuǎn)(即原來(lái)為即原來(lái)為1的位變的位變?yōu)闉?，為，為0的變?yōu)榈淖優(yōu)?)，其余各位不變。，其余各位不變?！臼纠咳纭臼纠咳鐇=146，y=222，z=x y，則，則z=76 1510.2.5 左位移左位移 【運(yùn)算符】【運(yùn)算符】 【格式】【格式】x要位移的位

11、數(shù)要位移的位數(shù)【功能】把操作對(duì)象的二進(jìn)制數(shù)向左移動(dòng)指定【功能】把操作對(duì)象的二進(jìn)制數(shù)向左移動(dòng)指定的位，并在右面補(bǔ)上相應(yīng)的的位，并在右面補(bǔ)上相應(yīng)的0，高位溢出。，高位溢出。【示例】如【示例】如x=01010011，y=x 【格式】【格式】x要位移的位數(shù)要位移的位數(shù)【功能】把操作對(duì)象的二進(jìn)制數(shù)向右移動(dòng)指定的位【功能】把操作對(duì)象的二進(jìn)制數(shù)向右移動(dòng)指定的位，移出的低位舍棄；高位：，移出的低位舍棄；高位：(1) 對(duì)無(wú)符號(hào)數(shù)和有符號(hào)中的正數(shù)，補(bǔ)對(duì)無(wú)符號(hào)數(shù)和有符號(hào)中的正數(shù)，補(bǔ)0；(2) 有符號(hào)數(shù)中的負(fù)數(shù)，取決于所使用的系統(tǒng)：補(bǔ)有符號(hào)數(shù)中的負(fù)數(shù)，取決于所使用的系統(tǒng)：補(bǔ)0的稱為的稱為“邏輯右移邏輯右移”，補(bǔ)，補(bǔ)1

12、的稱為的稱為“算術(shù)右移算術(shù)右移”?！臼纠咳纭臼纠咳鐇=01010011,y=x2,則則y=00010100【注意】右移會(huì)引起數(shù)據(jù)的變化，具體說(shuō)，右移一【注意】右移會(huì)引起數(shù)據(jù)的變化，具體說(shuō)，右移一位相當(dāng)于對(duì)原來(lái)的數(shù)值除以位相當(dāng)于對(duì)原來(lái)的數(shù)值除以2。右移。右移n位相當(dāng)于對(duì)原位相當(dāng)于對(duì)原來(lái)的數(shù)值除以來(lái)的數(shù)值除以2 n17說(shuō) 明lx、y和和“位數(shù)位數(shù)”等操作數(shù)，都只能是整型或字符型數(shù)據(jù)。等操作數(shù)，都只能是整型或字符型數(shù)據(jù)。除按位取反為單目運(yùn)算符外，其余均為雙目運(yùn)算符。除按位取反為單目運(yùn)算符外，其余均為雙目運(yùn)算符。l參與運(yùn)算時(shí)，操作數(shù)參與運(yùn)算時(shí)，操作數(shù)x和和y都必須首先轉(zhuǎn)換成二進(jìn)制形式，都必須首先轉(zhuǎn)

13、換成二進(jìn)制形式，然后再執(zhí)行相應(yīng)的按位運(yùn)算。例如：然后再執(zhí)行相應(yīng)的按位運(yùn)算。例如：l5220即即10125即即101001000101 。l 復(fù)合賦值運(yùn)算符復(fù)合賦值運(yùn)算符l除按位取反運(yùn)算外除按位取反運(yùn)算外,其余其余5個(gè)位運(yùn)算符均可與賦值運(yùn)算符一個(gè)位運(yùn)算符均可與賦值運(yùn)算符一起起,構(gòu)成復(fù)合賦值運(yùn)算符構(gòu)成復(fù)合賦值運(yùn)算符: &=、|+、=、=。例如，。例如，a & = b相當(dāng)于相當(dāng)于 a = a & b。a =2相當(dāng)于：相當(dāng)于：a = a 2。l不同長(zhǎng)度數(shù)據(jù)間的位運(yùn)算不同長(zhǎng)度數(shù)據(jù)間的位運(yùn)算低字節(jié)對(duì)齊，短數(shù)的高字節(jié)按低字節(jié)對(duì)齊，短數(shù)的高字節(jié)按最高位補(bǔ)位：最高位補(bǔ)位：l對(duì)無(wú)符號(hào)數(shù)和有

14、符號(hào)中的正數(shù)，補(bǔ)對(duì)無(wú)符號(hào)數(shù)和有符號(hào)中的正數(shù)，補(bǔ)0；l有符號(hào)數(shù)中的負(fù)數(shù)，補(bǔ)有符號(hào)數(shù)中的負(fù)數(shù)，補(bǔ)1。 1810.3 程序舉例程序舉例 l【例【例10-1】取一個(gè)整數(shù)】取一個(gè)整數(shù)a從右端開(kāi)始的從右端開(kāi)始的47位。位。 #include void main()unsigned a,b,c,d; scanf(%o,&a); b=a4;c=(04); d=b&c; printf(%o,%dn%o, %dn,a,a,d,d);19【例【例10-2】從鍵盤上輸入一個(gè)正整數(shù)】從鍵盤上輸入一個(gè)正整數(shù)給給int變量變量num，按二進(jìn)制位輸出該數(shù)。，按二進(jìn)制位輸出該數(shù)。 #include “stdio

15、.h“void main() int num, mask, i; printf(”input a integer number:”); scanf(“%d”,&num); mask = 115; printf(“%d=” , num); for(i=1; i=16; i+) putchar(num&mask ? 1: 0); num = 1; if( i%4=0 ) putchar(,); printf(bbn);20l本章介紹的位運(yùn)算在系統(tǒng)軟件開(kāi)發(fā)與計(jì)算機(jī)用于檢測(cè)本章介紹的位運(yùn)算在系統(tǒng)軟件開(kāi)發(fā)與計(jì)算機(jī)用于檢測(cè)和控制領(lǐng)域中有重要應(yīng)用，也是和控制領(lǐng)域中有重要應(yīng)用，也是c語(yǔ)言的特色

16、之一。語(yǔ)言的特色之一。重點(diǎn)要求讀者掌握位運(yùn)算符及其應(yīng)用。重點(diǎn)要求讀者掌握位運(yùn)算符及其應(yīng)用。l學(xué)好本章必須了解計(jì)算機(jī)內(nèi)數(shù)據(jù)的組織與存儲(chǔ)形式，學(xué)好本章必須了解計(jì)算機(jī)內(nèi)數(shù)據(jù)的組織與存儲(chǔ)形式，二進(jìn)制的原理是關(guān)鍵。二進(jìn)制的原理是關(guān)鍵。l本章介紹的位運(yùn)算包括按位與（本章介紹的位運(yùn)算包括按位與（&）、按位或（）、按位或（|）、）、按位異或（按位異或（）、按位取反（）、按位取反（）、左移（）、左移（），實(shí)質(zhì)上都是），實(shí)質(zhì)上都是1和和0的變換或者移動(dòng)，學(xué)好的變換或者移動(dòng)，學(xué)好本章對(duì)今后計(jì)算機(jī)系統(tǒng)的編程很有好處。本章對(duì)今后計(jì)算機(jī)系統(tǒng)的編程很有好處。 21l編寫一個(gè)函數(shù)編寫一個(gè)函數(shù)getbits，從一個(gè)，從一個(gè)16位的單元中取出某位的單元中取出某幾位（即該幾位保留原值，其余位為幾位（即該幾位保留原值，其余位為0）。函數(shù)調(diào)用）。