任何信息在計算機中都是采用二進(jìn)制表示的，數(shù)據(jù)在計算機中是以補碼形式存儲的，位運算就是直接對整數(shù)在內(nèi)存中的二進(jìn)制位進(jìn)行運算。由于位運算直接對內(nèi)存數(shù)據(jù)進(jìn)行操作，不需要轉(zhuǎn)換成十進(jìn)制，因此處理速度非常快，在信息學(xué)競賽中往往可以優(yōu)化理論時間復(fù)雜度的系數(shù)。同時，一個整數(shù)的各個二進(jìn)制位互不影響，利用位運算的一些技巧可以幫助我們簡化程序代碼。

C++提供了按位與（&）、按位或（I）、按位異或（^）、取反（~）、左移（<<）、右移（>>）這6種位運算符。這些運算符只能用于整型操作數(shù)，即只能用于帶符號或無符號的char、short、int與long類型。

“a&b”是指將參加運算的兩個整數(shù)a和b，按二進(jìn)制位進(jìn)行“與”運算。如果兩個相應(yīng)的二進(jìn)制位數(shù)字都為1，則該位的結(jié)果為1；否則為0。這里的1可以理解為邏輯中的true，0可以理解為邏輯中的false。“按位與”其實與邏輯上“與”的運算規(guī)則一致。

//3-00000011//5-00000101int a = 3;int b = 5;int c = a & b;cout << c<< endl; // 00000001

“a|b”是指將參加運算的兩個整數(shù)a和b，按二進(jìn)制位進(jìn)行“或”運算。如果兩個相應(yīng)的二進(jìn)制位數(shù)字有一個為1，則該位的結(jié)果為1否則為0。“按位或”其實與邏輯上“或”的運算規(guī)則一致。

// 48 - 00110000 //15 - 0000111int a = 48; int b = 15; int c = a | b; cout<< c<< endl; // 63 - 00111111

“a^b”是指將參加運算的兩個整數(shù)a和b，按二進(jìn)制位進(jìn)行“異或”運算。如果兩個相應(yīng)的二進(jìn)制位數(shù)字不相同，則該位的結(jié)果為1；否則為0。

a^0 = a? ? ? ? ?a^a = 0

// 52 - 00110100 //15-00001111 int a = 52; int b = 15; int c = a ^ b;cout << c<< endl; // 59 - 00111011

“~a”是指將整數(shù)a的各個二進(jìn)制位都取反，即1變?yōu)?，0變?yōu)?。“～”是一元運算符。

cout << ~9 << endl; /*9 - 00001001 取反 - 11110110 補碼11110101 反碼10001010 原碼最高位 1 表示負(fù)數(shù) -10*/

“a<<b”是指將整數(shù)a的各個二進(jìn)制位左移b位，高位丟棄，低位用0補齊。需要注意的是b必須是非負(fù)整數(shù)。在高位沒有1丟棄的情況下，a<<1相當(dāng)于a*2。

char a = (143<<2);printf("%d", a);/*143 - 10001111左移2 - 1000111100 60*/

“a>>b”是指將整數(shù)a的各個二進(jìn)制位右移b位，低位丟棄。對于無符號數(shù)，高位補0。對于有符號數(shù)，某些機器將對左邊空出的部分用符號位填補（即“算術(shù)移位”），而另一些機器則對左邊空出的部分用0填補（即“邏輯移位”）。同樣，b必須是非負(fù)整數(shù)。a>>1相當(dāng)于a/2。

char a = (15 >> 2 ); printf( "%d",a); /*15 - 00001111右移位2 - 00000011 3 */char a = (-15 >> 2 ); printf( "%d",a ); /*15 - 10001111反碼 - 11110000 補碼 - 11110001 右移2 - 1111110001 反碼 - 11111011 原碼 - 10000100 -4 */

位運算符也可以與賦值運算符組成復(fù)合運算符。

例如a &=b相當(dāng)于a=a&b，a<<=2相當(dāng)于a=a<<2。

位運算符也是有優(yōu)先級的，例如

• “加減”高于“>>”和“<<”
• “~”與“!”、“++”、“-”一致 ，高于“乘除”
• “關(guān)系運算” 高于?“&” 高于 “^” 高于 “|”高于“&&”和“||”

為了避免出錯，增強程序的可讀性，利于調(diào)試，建議在需要的地方添加括號來保證優(yōu)先運算。比如1<<5-1，建議寫成1<<（5-1），等價于1<<4。

例1：交換和取平均值

#include<iostream> using namespace std; int main() { //交換int x = 3,y = 9,z;x^= y; //x = x^y;y^= x; // y = y^x = (y ^ (x^y) ) =x;x^= y; //x = x^y = (x^y)^x = y;cout << x << " " << y << endl;//取平均值z = (x&y) + ((x^y)>>1 );cout << z << endl;return 0;}

?例2：整數(shù)冪

判斷一個數(shù)n是不是2的整數(shù)冪，比如64=2^6，所以輸出“yes”，而65 無法表示成2的整數(shù)冪形式，所以輸出"no"。n在int 范圍以內(nèi)。

• 【問題分析】
• 我們考慮一個數(shù)如果是2的整數(shù)冪會有什么特殊性。觀察發(fā)現(xiàn)64轉(zhuǎn)換成二進(jìn)制為0100000，只有一個位是1。將這個數(shù)減去1，就變成00111111的形式，我們將這2個數(shù)做按位與運算，發(fā)現(xiàn)結(jié)果為0。分析發(fā)現(xiàn)，如果一個數(shù)不能表示成2的整數(shù)冪形式，則以上過程的運算結(jié)果一定不為0。所以，可以利用位運算將算法的時間復(fù)雜度優(yōu)化成O（1）。

#include<iostream> using namespace std; int main() {int n;cin >> n;if (n&(n-1))cout << "no";elsecout << "yes";return 0;}

總結(jié)

以上是生活随笔為你收集整理的【算法学习】位运算的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。