位运算简单介绍
C/C++ 位操作 位操作技巧 判斷奇偶 交換兩數(shù) 變換符號(hào) 求絕對(duì)值 位操作壓縮空間 篩素?cái)?shù) 位操作趣味應(yīng)用 位操作筆試面試
位操作篇共分為基礎(chǔ)篇和提高篇，基礎(chǔ)篇主要對(duì)位操作進(jìn)行全面總結(jié)，幫助大家梳理知識(shí)。提高篇?jiǎng)t針對(duì)各大IT公司如微軟、騰訊、百度、360等公司的筆試面試題作詳細(xì)的解答，使大家能熟練應(yīng)對(duì)在筆試面試中位操作題目。
??????下面就先來對(duì)位操作作個(gè)全面總結(jié)，歡迎大家補(bǔ)充。
在計(jì)算機(jī)中所有數(shù)據(jù)都是以二進(jìn)制的形式儲(chǔ)存的。位運(yùn)算其實(shí)就是直接對(duì)在內(nèi)存中的二進(jìn)制數(shù)據(jù)進(jìn)行操作，因此處理數(shù)據(jù)的速度非常快。
在實(shí)際編程中，如果能巧妙運(yùn)用位操作，完全可以達(dá)到四兩撥千斤的效果，正因?yàn)槲徊僮鞯倪@些優(yōu)點(diǎn)，所以位操作在各大IT公司的筆試面試中一直是個(gè)熱點(diǎn)問題。因此本文將對(duì)位操作進(jìn)行如下方面總結(jié)：
??????一．?位操作基礎(chǔ)，用一張表描述位操作符的應(yīng)用規(guī)則并詳細(xì)解釋。
??????二．?常用位操作小技巧，有判斷奇偶、交換兩數(shù)、變換符號(hào)、求絕對(duì)值。
??????三．?位操作與空間壓縮，針對(duì)篩素?cái)?shù)進(jìn)行空間壓縮。
??????四．?位操作的趣味應(yīng)用，列舉了位操作在高低位交換、二進(jìn)制逆序、二進(jìn)制中1的個(gè)數(shù)以及缺失的數(shù)字這4種趣味應(yīng)用。
希望讀者能認(rèn)真學(xué)習(xí)和親自上機(jī)輸入代碼進(jìn)行實(shí)驗(yàn)，相信通過本文及適當(dāng)?shù)木毩?xí)可以使你對(duì)位操作有更加深入的了解，在筆試面試中遇到位操作相關(guān)試題能更加從容。
一． 位操作基礎(chǔ)
基本的位操作符有與、或、異或、取反、左移、右移這6種，它們的運(yùn)算規(guī)則如下所示：
| 符號(hào) | ?描述 | ?運(yùn)算規(guī)則??????????????????????? by MoreWindows |
| &?????? | ?與 | 兩個(gè)位都為1時(shí)，結(jié)果才為1 |
| |?? | ?或???? | 兩個(gè)位都為0時(shí)，結(jié)果才為0 |
| ^???? | 異或 | 兩個(gè)位相同為0，相異為1 |
| ~??? | 取反 | 0變1，1變0 |
| <<? | 左移 | 各二進(jìn)位全部左移若干位，高位丟棄，低位補(bǔ)0 |
| >>? | 右移 | 各二進(jìn)位全部右移若干位，對(duì)無符號(hào)數(shù)，高位補(bǔ)0，有符號(hào)數(shù)，各編譯器處理方法不一樣，有的補(bǔ)符號(hào)位（算術(shù)右移），有的補(bǔ)0（邏輯右移） |
注意以下幾點(diǎn)：
1．? 在這6種操作符，只有~取反是單目操作符，其它5種都是雙目操作符。
2．??位操作只能用于整形數(shù)據(jù)，對(duì)float和double類型進(jìn)行位操作會(huì)被編譯器報(bào)錯(cuò)。
3．? 對(duì)于移位操作，在微軟的VC6.0和VS2008編譯器都是采取算術(shù)稱位即算術(shù)移位操作，算術(shù)移位是相對(duì)于邏輯移位，它們?cè)谧笠撇僮髦卸家粯?#xff0c;低位補(bǔ)0即可，但在右移中邏輯移位的高位補(bǔ)0而算術(shù)移位的高位是補(bǔ)符號(hào)位。如下面代碼會(huì)輸出-4和3。
[cpp]?view plaincopy因?yàn)?5=0000 1111(二進(jìn)制)，右移二位，最高位由符號(hào)位填充將得到0000 0011即3。-15 = 1111 0001(二進(jìn)制)，右移二位，最高位由符號(hào)位填充將得到1111 1100即-4（見注1）。
4．? 位操作符的運(yùn)算優(yōu)先級(jí)比較低，因?yàn)楸M量使用括號(hào)來確保運(yùn)算順序，否則很可能會(huì)得到莫明其妙的結(jié)果。比如要得到像1，3，5，9這些2^i+1的數(shù)字。寫成int a = 1 << i + 1;是不對(duì)的，程序會(huì)先執(zhí)行i + 1，再執(zhí)行左移操作。應(yīng)該寫成int a = (1 << i) + 1;
5．? 另外位操作還有一些復(fù)合操作符，如&=、|=、 ^=、<<=、>>=。
?
二． 常用位操作小技巧
下面對(duì)位操作的一些常見應(yīng)用作個(gè)總結(jié)，有判斷奇偶、交換兩數(shù)、變換符號(hào)及求絕對(duì)值。這些小技巧應(yīng)用易記，應(yīng)當(dāng)熟練掌握。
1．判斷奇偶
只要根據(jù)最未位是0還是1來決定，為0就是偶數(shù)，為1就是奇數(shù)。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)來判斷a是不是偶數(shù)。
下面程序?qū)⑤敵?到100之間的所有奇數(shù)。
[cpp]?view plaincopy2．交換兩數(shù)
一般的寫法是：
[cpp]?view plaincopy可以用位操作來實(shí)現(xiàn)交換兩數(shù)而不用第三方變量：
[cpp]?view plaincopy可以這樣理解：
第一步? a^=b 即a=(a^b);
第二步? b^=a 即b=b^(a^b)，由于^運(yùn)算滿足交換律，b^(a^b)=b^b^a。由于一個(gè)數(shù)和自己異或的結(jié)果為0并且任何數(shù)與0異或都會(huì)不變的，所以此時(shí)b被賦上了a的值。
第三步 a^=b 就是a=a^b，由于前面二步可知a=(a^b)，b=a，所以a=a^b即a=(a^b)^a。故a會(huì)被賦上b的值。
再來個(gè)實(shí)例說明下以加深印象。int a = 13, b = 6;
a的二進(jìn)制為 13=8+4+1=1101(二進(jìn)制)
b的二進(jìn)制為 6=4+2=110(二進(jìn)制)
第一步 a^=b? a = 1101 ^ 110 = 1011;
第二步 b^=a? b = 110 ^ 1011 = 1101;即b=13
第三步 a^=b? a = 1011 ^ 1101 = 110;即a=6
3．變換符號(hào)
變換符號(hào)就是正數(shù)變成負(fù)數(shù)，負(fù)數(shù)變成正數(shù)。
如對(duì)于-11和11，可以通過下面的變換方法將-11變成11
??????1111 0101(二進(jìn)制) –取反-> 0000 1010(二進(jìn)制) –加1-> 0000 1011(二進(jìn)制)
同樣可以這樣的將11變成-11
??????0000 1011(二進(jìn)制) –取反-> 0000 0100(二進(jìn)制) –加1-> 1111 0101(二進(jìn)制)
因此變換符號(hào)只需要取反后加1即可。完整代碼如下：
[cpp]?view plaincopy4．求絕對(duì)值
位操作也可以用來求絕對(duì)值，對(duì)于負(fù)數(shù)可以通過對(duì)其取反后加1來得到正數(shù)。對(duì)-6可以這樣：
??????1111 1010(二進(jìn)制) –取反->0000 0101(二進(jìn)制) -加1-> 0000 0110(二進(jìn)制)
來得到6。
因此先移位來取符號(hào)位，int i = a >> 31;要注意如果a為正數(shù)，i等于0，為負(fù)數(shù)，i等于-1。然后對(duì)i進(jìn)行判斷——如果i等于0，直接返回。否之，返回~a+1。完整代碼如下：
[cpp]?view plaincopy現(xiàn)在再分析下。對(duì)于任何數(shù)，與0異或都會(huì)保持不變，與-1即0xFFFFFFFF異或就相當(dāng)于取反。因此，a與i異或后再減i（因?yàn)閕為0或-1，所以減i即是要么加0要么加1）也可以得到絕對(duì)值。所以可以對(duì)上面代碼優(yōu)化下：
[cpp]?view plaincopy注意這種方法沒用任何判斷表達(dá)式，而且有些筆面試題就要求這樣做，因此建議讀者記住該方法（^_^講解過后應(yīng)該是比較好記了）。
?
三． 位操作與空間壓縮
篩素?cái)?shù)法在這里不就詳細(xì)介紹了，本文著重對(duì)篩素?cái)?shù)法所使用的素?cái)?shù)表進(jìn)行優(yōu)化來減小其空間占用。要壓縮素?cái)?shù)表的空間占用，可以使用位操作。下面是用篩素?cái)?shù)法計(jì)算100以內(nèi)的素?cái)?shù)示例代碼（注2）：
[cpp]?view plaincopy運(yùn)行結(jié)果如下：
在上面程序是用bool數(shù)組來作標(biāo)記的，bool型數(shù)據(jù)占1個(gè)字節(jié)（8位），因此用位操作來壓縮下空間占用將會(huì)使空間的占用減少八分之七。
下面考慮下如何在數(shù)組中對(duì)指定位置置1，先考慮如何對(duì)一個(gè)整數(shù)在指定位置上置1。對(duì)于一個(gè)整數(shù)可以通過將1向左移位后與其相或來達(dá)到在指定位上置1的效果，代碼如下所示：
[cpp]?view plaincopy同樣，可以1向左移位后與原數(shù)相與來判斷指定位上是0還是1（也可以將原數(shù)右移若干位再與1相與）。
[cpp]?view plaincopy擴(kuò)展到數(shù)組上，我們可以采用這種方法，因?yàn)閿?shù)組在內(nèi)存上也是連續(xù)分配的一段空間，完全可以“認(rèn)為”是一個(gè)很長(zhǎng)的整數(shù)。先寫一份測(cè)試代碼，看看如何在數(shù)組中使用位操作：
[cpp]?view plaincopy運(yùn)行結(jié)果如下：
可以看出該數(shù)組每3個(gè)就置成了1，證明我們上面對(duì)數(shù)組進(jìn)行位操作的方法是正確的。因此可以將上面篩素?cái)?shù)方法改成使用位操作壓縮后的篩素?cái)?shù)方法：
[cpp]?view plaincopy同樣運(yùn)行結(jié)果為：
另外，還可以使用C++ STL中的bitset類來作素?cái)?shù)表。篩素?cái)?shù)方法在筆試面試出現(xiàn)的幾率還是比較大的，能寫出用位操作壓縮后的篩素?cái)?shù)方法無疑將會(huì)使你的代碼脫穎而出，因此強(qiáng)烈建議讀者自己親自動(dòng)手實(shí)現(xiàn)一遍，平時(shí)多努力，考試才不慌。
位操作的壓縮空間技巧也被用于strtok函數(shù)的實(shí)現(xiàn)，請(qǐng)參考《strtok源碼剖析 位操作與空間壓縮》（http://blog.csdn.net/morewindows/article/details/8740315）
?
四． 位操作的趣味應(yīng)用
位操作有很有趣的應(yīng)用，下面列舉出一些，歡迎讀者補(bǔ)充。
1．? 高低位交換
給出一個(gè)16位的無符號(hào)整數(shù)。稱這個(gè)二進(jìn)制數(shù)的前8位為“高位”，后8位為“低位”。現(xiàn)在寫一程序?qū)⑺母叩臀唤粨Q。例如，數(shù)34520用二進(jìn)制表示為：
??????10000110?11011000
將它的高低位進(jìn)行交換，我們得到了一個(gè)新的二進(jìn)制數(shù)：
??????11011000?10000110
它即是十進(jìn)制的55430。
這個(gè)問題用位操作解決起來非常方便，設(shè)x=34520=10000110?11011000(二進(jìn)制) 由于x為無符號(hào)數(shù)，右移時(shí)會(huì)執(zhí)行邏輯右移即高位補(bǔ)0，因此x右移8位將得到0000000010000110。而x左移8位將得到11011000?00000000。可以發(fā)現(xiàn)只要將x>>8與x<<8這兩個(gè)數(shù)相或就可以得到11011000?10000110。用代碼實(shí)現(xiàn)非常簡(jiǎn)潔：
[cpp]?view plaincopy運(yùn)行結(jié)果如下：
2．? 二進(jìn)制逆序
我們知道如何對(duì)字符串求逆序，現(xiàn)在要求計(jì)算二進(jìn)制的逆序，如數(shù)34520用二進(jìn)制表示為：
??????10000110 11011000
將它逆序，我們得到了一個(gè)新的二進(jìn)制數(shù)：
??????00011011 01100001
它即是十進(jìn)制的7009。
??? 回顧下字符串的逆序，可以從字符串的首尾開始，依次交換兩端的數(shù)據(jù)。在二進(jìn)制逆序我們也可以用這種方法，但運(yùn)用位操作的高低位交換來處理二進(jìn)制逆序?qū)?huì)得到更簡(jiǎn)潔的方法。類似于歸并排序的分組處理，可以通過下面4步得到16位數(shù)據(jù)的二進(jìn)制逆序：
第一步：每2位為一組，組內(nèi)高低位交換
??????10 00 01 10 ?11 01 10 00
? -->01 00 10 01 11 10 01 00
第二步：每4位為一組，組內(nèi)高低位交換
??????0100 1001 1110 0100
? -->0001 0110 1011 0001
第三步：每8位為一組，組內(nèi)高低位交換
??????00010110 10110001
? -->01100001 00011011
第四步：每16位為一組，組內(nèi)高低位交換
??????01100001 00011011
? -->00011011 01100001
對(duì)第一步，可以依次取出每2位作一組，再組內(nèi)高低位交換，這樣有點(diǎn)麻煩，下面介紹一種非常有技巧的方法。先分別取10000110 11011000的奇數(shù)位和偶數(shù)位，空位以下劃線表示。
??????原 數(shù)????10000110?11011000
??????奇數(shù)位 1_0_0_1_ 1_0_1_0_
??????偶數(shù)位??_0_0_1_0 _1_1_0_0
將下劃線用0填充，可得
??????原 數(shù)????10000110?11011000
??????奇數(shù)位?10000010?10001000
??????偶數(shù)位 00000100?01010000
再將奇數(shù)位右移一位，偶數(shù)位左移一位，此時(shí)將這兩個(gè)數(shù)據(jù)相或即可以達(dá)到奇偶位上數(shù)據(jù)交換的效果了。
??????原 數(shù)???????????10000110?11011000
??????奇數(shù)位右移?01000001?01000100??
? ????偶數(shù)位左移?00001000?10100000
????? 相或得到???? ?01001001 11100100
可以看出，結(jié)果完全達(dá)到了奇偶位的數(shù)據(jù)交換，再來考慮代碼的實(shí)現(xiàn)——
??????取x的奇數(shù)位并將偶數(shù)位用0填充用代碼實(shí)現(xiàn)就是x & 0xAAAA
??????取x的偶數(shù)位并將奇數(shù)位用0填充用代碼實(shí)現(xiàn)就是x & 0x5555
因此，第一步就用代碼實(shí)現(xiàn)就是：
?????? x = ((x & 0xAAAA) >> 1) | ((x & 0x5555) << 1);
類似可以得到后三步的代碼。完整程序如下：
[cpp]?view plaincopy運(yùn)行結(jié)果如下：
3．? 二進(jìn)制中1的個(gè)數(shù)
統(tǒng)計(jì)二進(jìn)制中1的個(gè)數(shù)可以直接移位再判斷，當(dāng)然像《編程之美》書中用循環(huán)移位計(jì)數(shù)或先打一個(gè)表再計(jì)算都可以。本文詳細(xì)講解一種高效的方法。以34520為例，可以通過下面四步來計(jì)算其二進(jìn)制中1的個(gè)數(shù)二進(jìn)制中1的個(gè)數(shù)。
第一步：每2位為一組，組內(nèi)高低位相加
????? 10 00 01 10 ?11 01 10 00
? -->01 00 01 01? 10 01 01 00
第二步：每4位為一組，組內(nèi)高低位相加
????? 0100 0101 1001 0100
? -->0001 0010 0011 0001
第三步：每8位為一組，組內(nèi)高低位相加
??????00010010 00110001
? -->00000011 00000100
第四步：每16位為一組，組內(nèi)高低位相加
??????00000011 00000100
? -->00000000 00000111
這樣最后得到的00000000 00000111即7即34520二進(jìn)制中1的個(gè)數(shù)。類似上文中對(duì)二進(jìn)制逆序的做法不難實(shí)現(xiàn)第一步的代碼：
?????? x = ((x & 0xAAAA) >> 1) + (x & 0x5555);
好的，有了第一步，后面幾步就請(qǐng)讀者完成下吧，先動(dòng)動(dòng)筆再看下面的完整代碼：
[cpp]?view plaincopy運(yùn)行結(jié)果如下：
可以發(fā)現(xiàn)巧妙運(yùn)用分組處理確實(shí)是解決很多二進(jìn)制問題的靈丹妙藥。
4．? 缺失的數(shù)字
很多成對(duì)出現(xiàn)數(shù)字保存在磁盤文件中，注意成對(duì)的數(shù)字不一定是相鄰的，如2, 3, 4, 3, 4, 2……，由于意外有一個(gè)數(shù)字消失了，如何盡快的找到是哪個(gè)數(shù)字消失了？
由于有一個(gè)數(shù)字消失了，那必定有一個(gè)數(shù)只出現(xiàn)一次而且其它數(shù)字都出現(xiàn)了偶數(shù)次。用搜索來做就沒必要了，利用異或運(yùn)算的兩個(gè)特性——1.自己與自己異或結(jié)果為0，2.異或滿足交換律。因此我們將這些數(shù)字全異或一遍，結(jié)果就一定是那個(gè)僅出現(xiàn)一個(gè)的那個(gè)數(shù)。 示例代碼如下：
[cpp]?view plaincopy在這個(gè)題目中有一個(gè)數(shù)字丟失了，如果有兩個(gè)數(shù)字丟失了應(yīng)該怎么做了，請(qǐng)看《【白話經(jīng)典算法系列之十二】數(shù)組中只出現(xiàn)1次的兩個(gè)數(shù)字(百度面試題)》?
地址：http://blog.csdn.net/morewindows/article/details/8214003
?
位操作是一種高效優(yōu)美的方法，同時(shí)由于其高效的運(yùn)算性能和掌握難度較大，位操作運(yùn)算一直是筆試面試時(shí)的熱門話題之一。本文詳細(xì)總結(jié)了位操作的方法與技巧并列出4種位操作趣味應(yīng)用，如果讀者能親自上機(jī)實(shí)現(xiàn)代碼，相信必能更好應(yīng)對(duì)筆試和面試時(shí)可能遇到的位操作問題。
另外，歡迎各位能提供筆試面試中的位操作相關(guān)的題目給我，我將會(huì)在提高篇中加入這些。謝謝大家。
?
?
注1．int類型一般占4字節(jié)，32位。因此15準(zhǔn)確表達(dá)為
15=00000000 00000000 00000000 00001111(二進(jìn)制)
-15準(zhǔn)確表達(dá)為
-15=11111111 11111111 11111111 11110001(二進(jìn)制)
為了簡(jiǎn)便起見，文章中使用15=00001111(二進(jìn)制)，-15=11110001(二進(jìn)制)。
?
注2．這種篩素?cái)?shù)的方法很樸素，會(huì)多次重復(fù)訪問數(shù)據(jù)，有什么辦法能改進(jìn)一下嗎？請(qǐng)看《改進(jìn)的篩素?cái)?shù)方法》一文。
?
轉(zhuǎn)載請(qǐng)標(biāo)明出處，原文地址：http://blog.csdn.net/morewindows/article/details/7354571
如果覺得本文對(duì)您有幫助，請(qǐng)點(diǎn)擊‘頂’支持一下，您的支持是我寫作最大的動(dòng)力，謝謝。
總結(jié)
- 上一篇： string类的用法详解
- 下一篇： linux如查看是否安装了mysql_l