位運(yùn)算的威力

2019-11-08 02:45:51

字體：大中小

供稿：網(wǎng)友

一、有關(guān)位運(yùn)算的基礎(chǔ)知識(shí)總結(jié)位運(yùn)算包括：&(與)、|(或)、^(異或)、~(取反)、>>(右移)、<<(左移)環(huán)境預(yù)設(shè)：32位機(jī)下面，int占2個(gè)字節(jié)，有符號(hào)int a = 11;int b = 1000;(a)2 = (00000000 00001011 )2 //a的二進(jìn)制表示(b)2 = (00000011 11101000 )2 //b的二進(jìn)制表示a&b =(00000000 00001000 )2 =(8)10 //一一為一，其它為0a|b = (00000011 11101011 )2 =(1003)10 //有一為一，零零為0a^b = (00000011 11100011 )2 =(995)10 //相同為0，不相同為1~b = (11111100 00010111 )2 =(-31767)10 //按位取反b>>3 = (00000000 01111101 )2 =(125)10 // 去掉低3位，高位補(bǔ)0或 = (11100000 01111101 )2 =(-24701)10 //去掉低3位，高位補(bǔ)1 補(bǔ)0還是1具體情況視編譯環(huán)境決定a<<3 = (00000000 01011000 )2 =(88)10 //去掉高3位，低位補(bǔ)0 看了上面的例子，相信你已經(jīng)明白具體規(guī)則了，不明白自己去google。下面講具體作用。位運(yùn)算應(yīng)用口訣清零取數(shù)要用與，某位置一可用或若要取反和交換，輕輕松松用異或例1.子網(wǎng)掩碼子網(wǎng)掩碼是個(gè)啥東東我也就不講了，計(jì)算機(jī)科學(xué)技術(shù)本身就是個(gè)非常龐大系統(tǒng)，一個(gè)人不可能面面俱到，但是一些基本的嘗試還是要懂的，不懂的可以自己去google，也可以等我的相關(guān)網(wǎng)絡(luò)方面的文章。這里只講與本問(wèn)有關(guān)的應(yīng)用部分。假如我是一個(gè)網(wǎng)管，公司內(nèi)部使用C類地址，現(xiàn)在我要把公司網(wǎng)絡(luò)劃分成5個(gè)子網(wǎng)，網(wǎng)絡(luò)號(hào)為192.168.1.0的前三段，那么子掩碼怎么填呢？我現(xiàn)在先告訴你子網(wǎng)的子網(wǎng)掩碼分別怎么填：192.168.1.224。(當(dāng)然這里還有其他答案，我取的是在子網(wǎng)擴(kuò)充不超過(guò)8個(gè)的情況下的每個(gè)子網(wǎng)所容納主機(jī)最多的最佳方案)。這個(gè)怎么來(lái)的呢？ip本身是個(gè)二進(jìn)制的東東，為了方便人們?cè)O(shè)置，我們采用了點(diǎn)分十進(jìn)制的轉(zhuǎn)換，把32位的ip地址轉(zhuǎn)換成了4個(gè)字節(jié)的十進(jìn)制萊表示。比如 192.168.1.213 這個(gè)ip地址的二進(jìn)制表示為：11000000 10101000 00000001 11010101 。對(duì)于C類地址默認(rèn)的前三個(gè)字節(jié)表示網(wǎng)絡(luò)號(hào)，那么這個(gè)網(wǎng)絡(luò)號(hào)就是：11000000 10101000 00000001 ，最后一個(gè)字節(jié)11010101表示主機(jī)號(hào)，可以知道這個(gè)網(wǎng)絡(luò)可以容納的最多主機(jī)數(shù)為2^8-2，為什么減2自己去查。現(xiàn)在要?jiǎng)澐肿泳W(wǎng)，那么我們就要從表示主機(jī)的那個(gè)字節(jié)也就是8個(gè)位里面拿出幾個(gè)位來(lái)表示子網(wǎng)號(hào)，幾位比較合適呢？這就要看你需要?jiǎng)澐侄嗌賯€(gè)子網(wǎng)咯。比如我們現(xiàn)在要?jiǎng)澐?個(gè)子網(wǎng)，(5)10 = (101)2 ，那么至少就需要3位了，而且最多可以劃分2^3 = 8個(gè)子網(wǎng)。現(xiàn)在你把224換成二進(jìn)制看看吧(224)10 = (11100000)2 ,明白了吧，我們可以推斷出子網(wǎng)掩碼干了什么勾當(dāng)？不錯(cuò)子網(wǎng)掩碼與ip地址做了按位與運(yùn)算，他的作用就是屏蔽了主機(jī)號(hào)獲取網(wǎng)絡(luò)號(hào)與子網(wǎng)號(hào)。如果你明白了這點(diǎn)，你就知道自己在192.168.1.64子網(wǎng)的ip該怎么填了，不會(huì)錯(cuò)誤滴填成192.168.1.10了。竟然扯到一邊去了，講了半天才講了一個(gè)與運(yùn)算的應(yīng)用。例2. 防止int型變量溢出 int x = 32760;int y = 32762; 要求求x、y的平均值，要求空間復(fù)雜度位O(0)。你能用常規(guī)方法去解決嗎？可以。我不會(huì)講，這里只講位運(yùn)算的方法。int ave(int x, int y) //返回X、Y的平均值{ return (x & y) + ( (x^y)>>1 );}知識(shí)點(diǎn)：>>n 相當(dāng)于除于2^n ，<<n 相當(dāng)于乘于2^n . x,y對(duì)應(yīng)位均為1，相加后再除以2還是原來(lái)的數(shù)，如兩個(gè)00001000相加后除以2仍得00001000,那么我們把x與y分別分成兩個(gè)部分來(lái)看,兩者相同的位分別拿出來(lái) 則 :x = (111111111111000)2 = (111111111111000)2 + (000000000000000)2y = (111111111111010)2 = (111111111111000)2 + (000000000000010)2相同部分我們叫做x1,y1,不同部分我們叫做x2,y2.那么現(xiàn)在(x+y)/2 =(x1+y1)/2 +(x2 + y2)/2 ,因?yàn)閤1 == y1 ,所以(x1+y1)/2 ==x1 ==y1,相同部分我們用與運(yùn)算求出來(lái) x1 = x&y ,不同部分的和我們用^求出來(lái),然后除于2是不是我們想要的結(jié)果了呢？言至于此，無(wú)需再言！這個(gè)例子有點(diǎn)難于理解.但是經(jīng)過(guò)我的分解應(yīng)該還算好理解了，弄懂這個(gè)例子相信你的位運(yùn)算已經(jīng)登入大門了。例3(《有關(guān)集合算法的實(shí)現(xiàn)一些學(xué)習(xí)筆記》中的"算法2") 將整數(shù)index的元素插入集合int insert(BitSet* s,int index){ if(index >=0 && index>>3 < s->size) {s->array[index>>3] |= (1<< (index & 7) );return 1} return 0;}代碼詳解：index>=0不解釋，(index>>3 )< s->size 這個(gè)是保證 index < n 的。因?yàn)閕ndex<=n-1，所以 index/8 <=(n-1)/8，又因?yàn)?nbsp;index < n+7 ==(n-1) +8，所以index/8 < (n-1)/8 +8/8 == s->size。因?yàn)閍rray的下標(biāo)是0到size-1，index>>3也就是index/8取整也就是index下標(biāo)所在的字節(jié)，index&7 等價(jià)于 index & 0000000 00000111 ，就是取index二進(jìn)制編碼的低三位也就是相當(dāng)于index>>3所剩下的余數(shù)，余數(shù)對(duì)應(yīng)的十進(jìn)制就是index所在字節(jié)的序號(hào)( 這個(gè)序號(hào)也是從0開始，并且從右至左)，所以把1左移相應(yīng)的位數(shù)就是index在n中對(duì)應(yīng)bit了，再把s->array[index>>3]也就是index所在的字節(jié)與(1<<(index&7))也就是除了index所在的位以外均為0或運(yùn)算，這樣無(wú)論index所對(duì)應(yīng)位原先是什么狀態(tài)，之后都被置1。這個(gè)可能比上一個(gè)例子難度大多了，這個(gè)需要掌握位向量的相關(guān)知識(shí)，如果你不能看懂就跳過(guò)吧。以上是我自己的一些學(xué)習(xí)心得。下面將貼上一些網(wǎng)絡(luò)上的例子。應(yīng)用舉例(1) 判斷int型變量a是奇數(shù)還是偶數(shù) a&1 = 0 偶數(shù) a&1 = 1 奇數(shù)(2) 取int型變量a的第k位 (k=0,1,2……sizeof(int))，即a>>k&1 (先右移再與1)

(3) 將int型變量a的第k位清0，即a=a&~(1<<k) (10000 取反后為00001 )

(4) 將int型變量a的第k位置1，即a=a|(1<<k)

(5) int型變量循環(huán)左移k次，即a=a<<k|a>>16-k (設(shè)sizeof(int)=16)(6) int型變量a循環(huán)右移k次，即a=a>>k|a<<16-k (設(shè)sizeof(int)=16)

(7)對(duì)于一個(gè)數(shù) x >= 0，判斷是不是2的冪。

boolean power2(int x){ return ( (x&(x-1))==0) && (x!=0);}

(8)不用temp交換兩個(gè)整數(shù)void swap(int x , int y){ x ^= y; y ^= x; x ^= y;}

(9)計(jì)算絕對(duì)值

int abs( int x ){ int y ; y = x >> 31 ; return (x^y)-y ; //or: (x+y)^y}

(10)取模運(yùn)算轉(zhuǎn)化成位運(yùn)算 (在不產(chǎn)生溢出的情況下) a % (2^n) 等價(jià)于 a & (2^n - 1)(11)乘法運(yùn)算轉(zhuǎn)化成位運(yùn)算 (在不產(chǎn)生溢出的情況下) a * (2^n) 等價(jià)于 a<< n(12)除法運(yùn)算轉(zhuǎn)化成位運(yùn)算 (在不產(chǎn)生溢出的情況下) a / (2^n) 等價(jià)于 a>> n 例: 12/8 == 12>>3(13) a % 2 等價(jià)于 a & 1 (14) if (x == a)

x= b;　　 else x= a;　　等價(jià)于 x= a ^ b ^ x;(15) x 的相反數(shù) 表示為 (~x+1)(16)輸入2的n次方：1 << 19(17)乘除2的倍數(shù)：千萬(wàn)不要用乘除法，非常拖效率。只要知道左移1位就是乘以2，右移1位就是除以2就行了。比如要算25 * 4，用25 << 2就好啦

實(shí)例功能 | 示例 | 位運(yùn)算 ----------------------+---------------------------+-------------------- 去掉最后一位 | (101101->10110) | x >> 1 在最后加一個(gè)0 | (101101->1011010) | x < < 1 在最后加一個(gè)1 | (101101->1011011) | x < < 1+1 把最后一位變成1 | (101100->101101) | x | 1 把最后一位變成0 | (101101->101100) | x | 1-1 最后一位取反 | (101101->101100) | x ^ 1 把右數(shù)第k位變成1 | (101001->101101,k=3) | x | (1 < < (k-1)) 把右數(shù)第k位變成0 | (101101->101001,k=3) | x & ~ (1 < < (k-1)) 右數(shù)第k位取反 | (101001->101101,k=3) | x ^ (1 < < (k-1)) 取末三位 | (1101101->101) | x & 7 取末k位 | (1101101->1101,k=5) | x & ((1 < < k)-1) 取右數(shù)第k位 | (1101101->1,k=4) | x >> (k-1) & 1 把末k位變成1 | (101001->101111,k=4) | x | (1 < < k-1) 末k位取反 | (101001->100110,k=4) | x ^ (1 < < k-1) 把右邊連續(xù)的1變成0 | (100101111->100100000) | x & (x+1) 把右起第一個(gè)0變成1 | (100101111->100111111) | x | (x+1) 把右邊連續(xù)的0變成1 | (11011000->11011111) | x | (x-1) 取右邊連續(xù)的1 | (100101111->1111) | (x ^ (x+1)) >> 1 去掉右起第一個(gè)1的左邊 | (100101000->1000) | x & (x ^ (x-1)) 判斷奇數(shù) (x&1)==1 判斷偶數(shù) (x&1)==0

上一篇：PAT 1035

下一篇：關(guān)于DirectShow SDK版本變遷說(shuō)明及解決找不到streams.h文件