摘要
位運算是C/C++中的基本運算之一，即便是這樣，它對大多數程序員來說是一個比較陌生的運算——大多數程序員很少使用位運算。本篇先簡要介紹基本的位運算操作符及其用法(何時使用)，然後介紹位運算符的幾個典型應用：
（1） 三種不用臨時變量交換兩個整數的實例，並分析每個實例的優缺點
（2） 進制轉換，通過位運算實現將十進制數按二進制和十六進制輸出，並得出一個通用的，用於將十進制按照2的n次方進制輸出的程序。
（3） 給出利用位運算實現的計算整數的二進制表示中有多少個1的實例。
揭開位運算的面紗
所有數據在計算機底層都是按二進制存儲的，一個數據可以看做是一個有序的位集合。每一位只有兩種狀態：0或1。位運算允許程序員操作數據的某一特定位，比如將某位設置為1(或0)，查詢某位的狀態(1，或0)。位運算由位運算操作符和操作數組成，不同的位運算操作符定義了不同的位運算，下面的表格是對每種位運算操作符及其對應的位運算和功能進行描述：
位運算操作符
對應的位運算
用法
功能描述
~
按位非
~expr
翻轉expr的每一個位：1變0,0變1
<<
左移
expr<<n
將expr向左移動n位，移到外面的被丟棄，右邊的位補0，因此左移n位相當於乘以2n
>>
右移
expr>>n
將expr向右移n位，移到外面的被丟棄，如果expr是無符號類型，則左邊補0，否則，左邊插入符號位的拷貝或者0(視具體實現而定)。
&
按位與
expr1&expr2
在每個位所在處，如果expr1和expr2都含有1，那麼結果該位為1，否則為0。
|
按位或
Expr1 | expr2
在每個位所在處，如果expr1和expr2都含有0，那麼結果該位為0，否則為1。
^
按位異或
Expr1 ^ expr2
在每個位所在處，如果expr1和expr2不相同，那麼結果該位為1，否則為0.
除了上面的基本位運算操作符外，還有&=，^=，|=，<<=,>>=等組合符號，它們分別是：按位與賦值，按位異或賦值，按位或賦值，左移賦值，右移賦值。接下來介紹如何實現位操作：
1.將expr的第n（n從0開始）位設置為1: expr |= (1<<n);
2.將expr的第n（n從0開始）位設置為0: expr &= (~(1<<n));
3.判斷expr的第n（n從0開始）位是否為1：bool b =expr & (1<<n);
4.翻轉expr的第n（n從0開始）位：expr ^=(1<<n)；
注意
1. C標准提供了bitset來進行各種位操作，可以在MSDN中輸入bitset了解相關內容，使用時需要包含頭文件:#include”bitset”。
2. 位運算只能用於操作有整數類型的數，比如說char,short,int,long等(包含signed 和unsigned)，不能操作浮點數，比如float，double！std：：bitset的構造函數的參數是unsigned long int，盡量不要對負數進行為操作，因為可移植性差，不同的系統平台對負數的右移操作定義不一樣（大多數平台規定高位補符號位，有些平台規定高位補0）。
位運算應用實例1：不用任何中間變量，交換兩個整數
這個問題是比較經典的了，你可以很容易地在網上找到多種答案，我在這裡給出兩個方案：
方案1：用算術運算實現(一個不完美的方案)
該方案的思路簡單，實現代碼很短，如下：
Template<class T>
Void mySwap_1(T& a, T& b)
{
a = a+b;
b = a -b;
a = a-b;
}
簡單吧，但是我還要簡單說一下：第一句a=a+b;是用a保存原來的a跟原的b的和；第二句b = a-b;使得原來的a的值被保存到了b裡面；最後一句a=a-b;使得原來的b的值保存到了a裡面。
我們說這個方法是不那麼完美的，原因在於算術運算可能會出現結果溢出的問題，假如a，b都非常大，那麼第一句a=a+b就會導致結果溢出，比如說原來的a = 2147483647,b = 2,那麼a+b就為2147483649，這個數大於了最大的無符號整數2147483648，因此發生溢出，a中保存的結果實際上是：-2147483647，但是讓人驚訝的是：雖然第一句程序得到的結果為-2147483647，後面兩句得到的結果卻是正確的，即能實現交換原始a,b的值，也就是說：只有第一句的結果是錯誤的，但最後的結果卻是正確的，這一點讓我很迷惑，至今還沒弄清楚緣由，再次向各位求教！
最後，談談這種方法相對於後面的方案2的優點：該方法可以用於交換兩個非整數(浮點數)，而方案2基於位運算，而對浮點數不能直接使用位運算，因此方案2不能用於交換兩個浮點數！
方案2：用位運算實現(較好的方案)
該方案代碼與方案1及其相似，思路也不難，先看代碼，然後再看我啰嗦的剖析：
template<class T>
void mySwap_2(T& a,T& b)
{
a = a^b;
b = b^a;
a = a^b;
}
對於編程老手來說，這個交換函數並不陌生，但我相信這些編程老手之中有一部分人只記得這麼寫代碼，而不知道三句代碼為何這麼寫，事實上我最初也是這樣，因此一開始我就覺得短短3行代碼，讓我花費時間去理解分析，還不如直接記憶來得劃算。事實上，直到今天我寫這篇文章時，我捨得消耗一點腦細胞來理解它，下面我嘗試著對上述三句代碼進行闡述，為了方便，假設數據類型為char，並且a = 5,b=3;那麼在內存中a,b存儲如下：
a:
0
0
0
0
0
1
0
1
b:
0
0
0
0
0
0
1
1
接下來詳細分析每一句：
首先來看第一句：a=a^b;執行該語句後a中保存了a與b的差異位，也就是說如果原來的a和b的某一位不同，那麼就將a的該位置為1，因此a在內存中成了如下圖的樣子，它說明a與b的第2,3個bit有差異：
a:
0
0
0
0
0
1
1
0
接著我們來看第二句：b=b^a；其意思是，將b中有差異的位翻轉，如此一來b中保存的值其實就等於原來a中的值，記住當第二個語句執行完之後a仍然保存了原來的a,b的差異信息，而b則變成了原來的a！
最後我們來看第三句：a=a^b;由於異或運算滿足交換律，因此這一句等價於：a=b^a;記住這個語句賦值號右邊的b中已經保存了原始的a值，而a中保存了原始的a，b的差異，因此這一句的最終作用是將原始a中有差異的位翻轉(變成b)然後賦值給a，如此一來a中就保存了原始的b值。
總結：上述三句中：第一句是記錄差異，第2,3句是翻轉，最終實現了不用任何中間變量就交換兩個變量的值。
分析：位運算不考慮進位問題，因此不會有結果溢出的問題！但是由於不能對浮點數進行直接位運算，因此該方法不能實現交換兩個浮點數！當然原題題目是交換兩個整數。
備注：還有其他實現兩個數交換的方法，比如采用內存拷貝！由於不屬於位運算范疇，這裡就不贅述了。
位運算應用實例2：進制轉換
要求：分別實現十進制整數按二進制、十六進制輸出。
兩種方法實現按二進制輸出：
方法1：由於整數在計算機中是按二進制存儲的，我們只需要將其每個bit按順序打印出來即可，如果某位為1，則打印字符‘1’，否則打印字符‘0’。我給出的代碼如下：
voidprintBinary(int num)
{
for(int i=0;i<32;i++)
{
cout<<((num>>(31-i))&1);
//cout<<( (num &(1<<(31-i))) ==0? 0 : 1 );
}
}
其中被注釋掉的那個cout與沒注釋的cout有同樣的功能！這個函數的思路很簡單，就是從高到底逐位打印每個bit。我上面的代碼有一點不好的地方，那就是語句太復雜，一個cout語句干了太多的事情，如果影響您的理解，那麼你可以增加幾個臨時變量，然後把它拆分成多個簡單語句。我這麼寫主要是考慮到篇幅的原因，因此程序段太占篇幅了。隨便說一句，編程時，語句力求簡單明了：一行只寫一條語句，一條語句只干一件事情！
方法二：利用bitset來實現
bitset是標准庫提供的一個類(不是容器)，利用它就可以很方便地操作位，下面是用bitset來實現的程序：
voidprintBinary(int num)
{
bitset<32> bits =bitset<32>((unsigned long)(num));
for(int i=31;i>=0;i--)
{
cout<<(bits[i]==true? '1' : '0');
}
}
備注：關於bitset重載了多個運算符，其中包含下標運算符：[]，可以方便地取得某一個bit，看它是否為1。關於bitset的更多信息請查閱msdn或者其他資料，你只要記住bitset是標准庫提供的，你可以隨時使用，不要忘記添加相應的頭文件。
實現按16進制輸出：
同樣由於數據在內存中是按二進制存儲的，因此將整數按照16進制輸出我們可以如下做：從左向右，每4位bit一組，組合成一個十六進制數，一次輸出即可，其程序如下：
void printHex(int num)
{
for(inti=28;i>=0;i-=4)
{
int temp =num>>i;
temp =temp&15; //15是掩碼！
char ch;
temp>9?(ch ='A'+temp-10):(ch = '0'+temp);
cout<<ch;
}
}
該程序與上面的printBinary函數非常相似，要注意的是i每次變化4，最關鍵點在於語句temp= temp&15；由於是16進制，因此這裡用15做掩碼。我想有了printBinary做鋪墊，理解這個printHex並不難，這裡不贅述了。接下來我將對這兩個函數進行個小小的擴展：實現整數按2n (2的n次方)進制輸出！比如按8進制，32進制等。為了方便描述，我們限制1<=n<=6；並用字符’0’到’9’表示數字0到9，用字符A,B,……Z,a,b,……表示數字10到63。程序如下：
void print2powerN(int num,int N)
{
for(inti=32-N;i>=0;i-=N)
{
int temp =num>>i;
temp =temp&((1<<N)-1);
char ch;
if(temp<=9)
{
ch ='0'+temp;
}
elseif(temp<=35)
{
ch ='A'+temp-10;
}
else
{
ch = 'a'+temp - 36;
}
cout<<ch;
}
}
備注：用位運算也能實現十進制到任意進制的轉換，這個問題比較難，我暫時還沒弄透徹！
位運算案例3：求整數的二進制表示中1的個數
問題描述：輸入一個整數N要求輸出其二進制表示中1的個數M，比如N=13，則M=3；
分析：該問題的求解方法不止一種，可以對二進制表示的每一位逐位掃描來實現，這種方法的復雜度是o(n)其中n是N的二進制表示的總位數。這裡介紹如何用位操作來求解，並且保證其復雜度低於o(n)，事實上該方法的復雜度為o(m)，其中m是N的二進制標識中1的個數！
思路：在講述具體實現時，來看這樣一個事實：n&(n-1)能實現將最低位的1翻轉！比如說n=108，其二進制表示為01101100,則n&(n-1)的結果是01101000。因此只要不停地翻轉n的二進制的最低位的1，每翻轉一次讓計數器+1，直到n等於0時，計數器中就記錄了n的二進制中1的位數，程序如下：
int count1Bits(long n)
{
int count =0;
while(n)
{
count++;
n&=(n-1);
}
return count;
}
注：關於該問題的其他方法，請參考《編程之美》。n&(n-1)的另外一個用處是判斷n是否是2的整數次冪。
到此，本文該結束了，我發現最近我每次寫的東西可以用一句諺語來形容：懶婆娘的裹腳——又臭又長！沒辦法，每次一想寫東西，就思維很發散(或許用凌亂來形容更加貼切)，看來以後得把大的專題篇總結了。還有，由於最近天氣奇熱，心情浮躁，頭腦發昏，文中的代碼有考慮欠佳的地方，還請各位批評指正。
