772
劍指Offer之麵試位運算總結
（1）基本知識
位運算的題目經常出現在麵試中。在此總結一下關於位運算的知識點。
位運算是把數字用於二進製表示之後，對每一位上的0,1的運算。
其實二進製的位運算並不是很難掌握，因為位運算總共隻有五種運算：與，或，異或，左移和右移。
左移：
左移運算符m <<n 表示把m左移n位。在左移n位的時候，最左邊的n位將被丟棄，同時在最右邊補上n個0。
比如：
00001010 << 2 = 00101000
10001010 << 3 = 01010000
右移：
右移運算符m >> n表示把m右移n位。右移n位的時候最右邊的n位將被丟棄。但注意的是右移時候的最左邊的n位的處理。
如果數字是一個為無符號數值，則用0填補最左邊的n位。如果數字是一個有符號數值，則用數字的符號位填補最左邊的n位。
也就是說如果原先數字是一個整數則右移之後最左邊補上n個0,；如果數字原始是負數，則右移之後在左邊補n個1。
比如：
00001010 >> 2 = 00000010
10001010 >> 3 = 11110001
注意以下幾點：
1.在這5種操作符，都是雙目操作符。隻有~取反是單目操作符，在這沒有提及。
2.位操作隻能用於整形數據，對float和double類型進行位操作會被編譯器報錯。
3.對於移位操作，在微軟的VC6.0和VS2008編譯器都是采取算術稱位即算術移位操作，算術移位是相對於邏輯移位，它們在左移操作中都一樣，低位補0即可，但在右移中邏輯
移位的高位補0而算術移位的高位是補符號位。
4.位操作符的運算優先級比較低，因為盡量使用括號來確保運算順序，否則很可能會得到莫明其妙的結果。比如要得到像1，3，5，9這些2^i+1的數字。寫成int a = 1 << i + 1;是
不對的，程序會先執行i + 1，再執行左移操作。應該寫成int a = (1 << i) + 1;
5.另外位操作還有一些複合操作符，如&=、|=、 ^=、<<=、>>=。
（2）位運算常用技巧
1.判斷奇偶
隻要根據最未位是0還是1來決定,為0就是偶數,為1就是奇數。因此可以用if((a & 1) == 0)代替if(a % 2 == 0)來判斷a是不是偶數。
int a = 4;
if(a & 1){
printf("%d是奇數!\n",a);
}
else{
printf("%d是偶數!\n",a);
}
2.交換數據
//臨時變量法交換數據
void swap(int &a, int &b){
int temp;
if (a != b){
temp = a;
a = b;
b = temp;
}
}
//位運算法交換數據
void swap2(int &a, int &b){
if (a != b){
a ^= b;
b ^= a;
a ^= b;
}
}
第一步 a^=b 即a=(a^b);
第二步 b^=a即b=b^(a^b)，由於^運算滿足交換律，b^(a^b)=b^b^a。
由於一個數和自己異或的結果為0並且任何數與0異或都會不變的，所以此時b被賦上了a的值。
第三步 a^=b 就是a=a^b，由於前麵二步可知a=(a^b)，b=a，所以a=a^b即a=(a^b)^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.變換符號
變換符號就是正數變成負數，負數變成正數。
如對於-11和11，可以通過下麵的變換方法將-11變成11
1111 0101(二進製) 取反-> 0000 1010(二進製) 加1-> 0000 1011(二進製)
同樣可以這樣的將11變成-11
0000 1011(二進製) 取反-> 0000 0100(二進製) 加1-> 1111 0101(二進製)
因此變換符號隻需要取反後加1即可。
int a = 4;
int b = ~a + 1;
printf("%d\n",b);
int c = -4;
int d = ~c + 1;
printf("%d\n",d);
4.求絕對值
位操作也可以用來求絕對值，對於負數可以通過對其取反後加1來得到正數。
對-6可以這樣：
1111 1010(二進製) –取反->0000 0101(二進製) -加1-> 0000 0110(二進製)
來得到6。
因此先移位來取符號位，int i = a >> 31;
要注意如果a為正數，i等於0，為負數，i等於-1。
然後對i進行判斷:如果i等於0，直接返回。否之，返回~a+1。
//取符號位
int a = -100;
int i = a >> 31;
//i = 0 正數
if(i == 0){
printf("%d\n",a);
}
//i = 1 負數
else{
printf("%d\n",~a + 1);
}
對於任何數，與0異或都會保持不變，與-1即0xFFFFFFFF異或就相當於取反。
因此，a與i異或後再減i（因為i為0或-1，所以減i即是要麼加0要麼加1）也可以得到絕對值。
int a = -100;
int i = a >> 31;
int b = ((a ^ i) - i);
printf("%d\n",b);
（3）位運算應用
它即是十進製的55430。
這個問題用位操作解決起來非常方便，設x=34520=10000110 11011000(二進製) 由於x為無符號數，右移時會執行邏輯右移即高位補0，因此x右移8位將得到00000000 10000110。而x左移8位將得到11011000 00000000。可以發現隻要將x>>8與x<<8這兩個數相或就可以得到1101100010000110。
2.判斷一個整數是不是2的整數次方
如果一個整數是2的整數次方，那麼他的二進製標識中一定有且隻有一位是1，而其他所有位均為0.
解決方案：
把這個整數減去1之後再和他自己做與運算，這個整數中唯一的一個1就會變成0.所以隻要判斷是不是等於0即可。
最後更新：2017-04-03 14:54:04