在計算機中所有數(shù)據(jù)都是以二進制的形式儲存的。位運算其實就是直接對在內(nèi)存中的二進制數(shù)據(jù)進行操作，因此處理數(shù)據(jù)的速度非炒蚓颍快。
在實際編程中鹏秋，如果能巧妙運用位操作尊蚁，完全可以達到四兩撥千斤的效果，正因為位操作的這些優(yōu)點侣夷，所以位操作在各大IT公司的筆試面試中一直是個熱點問題横朋。因此本文將對位操作進行如下方面總結(jié)：
一． 位操作基礎(chǔ)，用一張表描述位操作符的應(yīng)用規(guī)則并詳細解釋百拓。
二． 常用位操作小技巧琴锭，有判斷奇偶、交換兩數(shù)耐版、變換符號祠够、求絕對值。
三． 位操作與空間壓縮粪牲，針對篩素數(shù)進行空間壓縮古瓤。
四． 位操作的趣味應(yīng)用，列舉了位操作在高低位交換、二進制逆序落君、二進制中1的個數(shù)以及缺失的數(shù)字這4種趣味應(yīng)用穿香。
一． 位操作基礎(chǔ)
基本的位操作符有與、或绎速、異或皮获、取反、左移纹冤、右移這6種洒宝，它們的運算規(guī)則如下所示：
| 符號 | 描述 | 運算規(guī)則 |
|---|---|---|
| & | 與 | 兩個位都為1時，結(jié)果才為1 |
| 豎線 | 或 | 兩個位都為0時萌京，結(jié)果才為0 |
| ^ | 異或 | 兩個位相同為0雁歌，相異為1 |
| ~ | 取反 | 0變1，1變0 |
| << | 左移 | 各二進位全部左移若干位知残，高位丟棄靠瞎，低位補0 |
| >> | 右移 | 各二進位全部右移若干位，對無符號數(shù)求妹，高位補0乏盐，有符號數(shù)，各編譯器處理方法不一樣制恍，有的補符號位（算術(shù)右移）父能，有的補0（邏輯右移） |
注意以下幾點：
1． 在這6種操作符，只有~取反是單目操作符吧趣，其它5種都是雙目操作符法竞。
2． 位操作只能用于整形數(shù)據(jù)，對float和double類型進行位操作會被編譯器報錯强挫。
3． 對于移位操作，在微軟的VC6.0和VS2008編譯器都是采取算術(shù)稱位即算術(shù)移位操作薛躬，算術(shù)移位是相對于邏輯移位俯渤，它們在左移操作中都一樣，低位補0即可型宝，但在右移中邏輯移位的高位補0而算術(shù)移位的高位是補符號位八匠。如下面代碼會輸出-4和3。
int a = -15, b = 15;
printf("%d %d\n", a >> 2, b >> 2);
因為15=0000 1111(二進制)趴酣，右移二位梨树，最高位由符號位填充將得到0000 0011即3。-15 = 1111 0001(二進制)岖寞，右移二位抡四，最高位由符號位填充將得到1111 1100即-4（見注1）。
4． 位操作符的運算優(yōu)先級比較低，因為盡量使用括號來確保運算順序指巡，否則很可能會得到莫明其妙的結(jié)果淑履。比如要得到像1，3藻雪，5秘噪，9這些2^i+1的數(shù)字。寫成int a = 1 << i + 1;是不對的勉耀，程序會先執(zhí)行i + 1指煎，再執(zhí)行左移操作。應(yīng)該寫成int a = (1 << i) + 1;
5． 另外位操作還有一些復合操作符便斥，如&=至壤、|=、 ^=椭住、<<=崇渗、>>=。
二． 常用位操作小技巧
下面對位操作的一些常見應(yīng)用作個總結(jié)京郑，有判斷奇偶宅广、交換兩數(shù)、變換符號及求絕對值些举。這些小技巧應(yīng)用易記跟狱，應(yīng)當熟練掌握。
1．判斷奇偶
只要根據(jù)最未位是0還是1來決定户魏，為0就是偶數(shù)驶臊，為1就是奇數(shù)。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)來判斷a是不是偶數(shù)叼丑。
下面程序?qū)⑤敵?到100之間的所有奇數(shù)关翎。
for (i = 0; i < 100; ++i)
if (i & 1)
printf("%d ", i);
putchar('\n');
2．交換兩數(shù)
一般的寫法是：
void Swap(int &a, int &b)
{
if (a != b)
{
int c = a;
a = b;
b = c;
}
}
可以用位操作來實現(xiàn)交換兩數(shù)而不用第三方變量：
void Swap(int &a, int &b)
{
if (a != b)
{
a ^= b;
b ^= a;
a ^= b;
}
}
可以這樣理解：
第一步 a^=b 即a=(a^b);
第二步 b^=a 即b=b(ab)，由于運算滿足交換律鸠信，b(ab)=bb^a纵寝。由于一個數(shù)和自己異或的結(jié)果為0并且任何數(shù)與0異或都會不變的，所以此時b被賦上了a的值星立。
第三步 a^=b 就是a=ab爽茴，由于前面二步可知a=(ab)，b=a绰垂，所以a=ab即a=(ab)^a室奏。故a會被賦上b的值。再來個實例說明下以加深印象劲装。int a = 13, b = 6;
a的二進制為 13=8+4+1=1101(二進制)
b的二進制為 6=4+2=110(二進制)
第一步 a^=b a = 1101 ^ 110 = 1011;
第二步 b^=a b = 110 ^ 1011 = 1101;即b=13
第三步 a^=b a = 1011 ^ 1101 = 110;即a=6
3．變換符號
變換符號就是正數(shù)變成負數(shù)胧沫，負數(shù)變成正數(shù)昌简。
如對于-11和11，可以通過下面的變換方法將-11變成11
1111 0101(二進制) –取反-> 0000 1010(二進制) –加1-> 0000 1011(二進制)
同樣可以這樣的將11變成-11
0000 1011(二進制) –取反-> 0000 0100(二進制) –加1-> 1111 0101(二進制)
因此變換符號只需要取反后加1即可琳袄。完整代碼如下：
#include <stdio.h>
int SignReversal(int a)
{
return ~a + 1;
}
int main()
{
int a = 7, b = -12345;
printf("%d %d\n", SignReversal(a), SignReversal(b));
return 0;
}
4．求絕對值
位操作也可以用來求絕對值江场，對于負數(shù)可以通過對其取反后加1來得到正數(shù)。對-6可以這樣：
1111 1010(二進制) –取反->0000 0101(二進制) -加1-> 0000 0110(二進制)
來得到6窖逗。
因此先移位來取符號位址否，int i = a >> 31;要注意如果a為正數(shù)，i等于0碎紊，為負數(shù)佑附，i等于-1。然后對i進行判斷——如果i等于0仗考，直接返回音同。否之，返回~a+1秃嗜。完整代碼如下：
int my_abs(int a)
{
int i = a >> 31;
return i == 0 ? a : (~a + 1);
}
現(xiàn)在再分析下权均。對于任何數(shù)，與0異或都會保持不變锅锨，與-1即0xFFFFFFFF異或就相當于取反叽赊。因此，a與i異或后再減i（因為i為0或-1必搞，所以減i即是要么加0要么加1）也可以得到絕對值必指。所以可以對上面代碼優(yōu)化下：
int my_abs(int a)
{
int i = a >> 31;
return ((a ^ i) - i);
}
注意這種方法沒用任何判斷表達式，而且有些筆面試題就要求這樣做恕洲，因此建議讀者記住該方法（_講解過后應(yīng)該是比較好記了）塔橡。
三． 位操作與空間壓縮
篩素數(shù)法在這里不就詳細介紹了，本文著重對篩素數(shù)法所使用的素數(shù)表進行優(yōu)化來減小其空間占用霜第。要壓縮素數(shù)表的空間占用葛家，可以使用位操作。下面是用篩素數(shù)法計算100以內(nèi)的素數(shù)示例代碼（注2）：
const int MAXN = 100;
bool flag[MAXN];
int primes[MAXN / 3 + 1], pi;
//對每個素數(shù)泌类，它的倍數(shù)必定不是素數(shù)惦银。
//有很多重復如flag[10]會在訪問flag[2]和flag[5]時各訪問一次
void GetPrime_1()
{
int i, j;
pi = 0;
memset(flag, false, sizeof(flag));
for (i = 2; i < MAXN; i++)
if (!flag[i])
{
primes[pi++] = i;
for (j = i; j < MAXN; j += i)
flag[j] = true;
}
}
void PrintfArray()
{
for (int i = 0; i < pi; i++)
printf("%d ", primes[i]);
putchar('\n');
}
int main()
{
printf("用篩素數(shù)法求100以內(nèi)的素數(shù)\n-- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");
GetPrime_1();
PrintfArray();
return 0;
}
運行結(jié)果如下：
在上面程序是用bool數(shù)組來作標記的，bool型數(shù)據(jù)占1個字節(jié)（8位）末誓，因此用位操作來壓縮下空間占用將會使空間的占用減少八分之七。
下面考慮下如何在數(shù)組中對指定位置置1书蚪，先考慮如何對一個整數(shù)在指定位置上置1喇澡。對于一個整數(shù)可以通過將1向左移位后與其相或來達到在指定位上置1的效果，代碼如下所示：
//在一個數(shù)指定位上置1
int j = 0;
j |= 1 << 10;
printf("%d\n", j);
同樣殊校，可以1向左移位后與原數(shù)相與來判斷指定位上是0還是1（也可
以將原數(shù)右移若干位再與1相與）晴玖。
//判斷指定位上是0還是1
int j = 1 << 10;
if ((j & (1 << 10)) != 0)
printf("指定位上為1");
else
printf("指定位上為0");
擴展到數(shù)組上，我們可以采用這種方法，因為數(shù)組在內(nèi)存上也是連續(xù)分配的一段空間呕屎，完全可以“認為”是一個很長的整數(shù)让簿。先寫一份測試代碼，看看如何在數(shù)組中使用位操作：
int main()
{
printf(" 對數(shù)組中指定位置上置位和判斷該位\n");
printf("--- by MoreWindows( http://blog.csdn.net/MoreWindows ) ---\n\n");
//在數(shù)組中在指定的位置上寫1
int b[5] = {0};
int i;
//在第i個位置上寫1
for (i = 0; i < 40; i += 3)
b[i / 32] |= (1 << (i % 32));
//輸出整個bitset
for (i = 0; i < 40; i++)
{
if ((b[i / 32] >> (i % 32)) & 1)
putchar('1');
else
putchar('0');
}
putchar('\n');
return 0;
}
運行結(jié)果如下：
可以看出該數(shù)組每3個就置成了1秀睛，證明我們上面對數(shù)組進行位操作的方法是正確的尔当。因此可以將上面篩素數(shù)方法改成使用位操作壓縮后的篩素數(shù)方法：
//使用位操作壓縮后的篩素數(shù)方法
const int MAXN = 100;
int flag[MAXN / 32 + 1];
int primes[MAXN / 3 + 1], pi;
void GetPrime_1()
{
int i, j;
pi = 0;
memset(flag, 0, sizeof(flag));
for (i = 2; i < MAXN; i++)
if (!((flag[i / 32] >> (i % 32)) & 1))
{
primes[pi++] = i;
for (j = i; j < MAXN; j += i)
flag[j / 32] |= (1 << (j % 32));
}
}
void PrintfArray()
{
for (int i = 0; i < pi; i++)
printf("%d ", primes[i]);
putchar('\n');
}
int main()
{
printf("用位操作壓縮后篩素數(shù)法求100以內(nèi)的素數(shù)\n-- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");
GetPrime_1();
PrintfArray();
return 0;
}
同樣運行結(jié)果為：
另外，還可以使用C++ STL中的bitset類來作素數(shù)表蹂安。篩素數(shù)方法在筆試面試出現(xiàn)的幾率還是比較大的椭迎，能寫出用位操作壓縮后的篩素數(shù)方法無疑將會使你的代碼脫穎而出，因此強烈建議讀者自己親自動手實現(xiàn)一遍田盈，平時多努力畜号，考試才不慌。
位操作的壓縮空間技巧也被用于strtok函數(shù)的實現(xiàn)允瞧，請參考《strtok源碼剖析 位操作與空間壓縮》（http://blog.csdn.net/morewindows/article/details/8740315）
推薦閱讀：
經(jīng)典算法應(yīng)用之一----歸并排序（微軟筆試題）
經(jīng)典算法應(yīng)用之二----基數(shù)排序（google筆試題）
經(jīng)典算法應(yīng)用之三----應(yīng)用二中題目的升華
經(jīng)典算法應(yīng)用之四（上）---基本位操作之算法篇
經(jīng)典算法應(yīng)用之四（中）---基本位操作之算法篇
經(jīng)典算法應(yīng)用之四（下）---百度面試題
經(jīng)典算法應(yīng)用之五---隨機生成和為S的N個正整數(shù)
經(jīng)典算法應(yīng)用之六---過橋問題和過河問題
經(jīng)典算法應(yīng)用之七----10億數(shù)據(jù)中取最大的100個數(shù)據(jù)
