力扣君表示位運算也是各大互聯網公司面試經常會問的一類問題。
電腦中的數在記憶體中都是以二進制形式進行儲存的,用位運算就是直接對整數在記憶體中的二進制位進行操作,因此其執行效率非常高,在程式中盡量使用位運算進行操作,這會大大提高程式的效能。
位操作符
1 0 0 1 1
& 1 1 0 0 1
------------------------------
1 0 0 0 1
1 0 0 1 1
| 1 1 0 0 1
------------------------------
1 1 0 1 1
1 0 0 1 1
^ 1 1 0 0 1
-----------------------------
0 1 0 1 0
~ 1 0 0 1 1
-----------------------------
0 1 1 0 0
int a = 8;
a << 3;
移位前:0000 0000 0000 0000 0000 0000 0000 1000
移位後:0000 0000 0000 0000 0000 0000 0100 0000
>> 右移運算,向右進行移位操作,對無符號數,高位補 0,對於有符號數,高位補符號位,如
unsigned int a = 8;
a >> 3;
移位前:0000 0000 0000 0000 0000 0000 0000 1000
移位後:0000 0000 0000 0000 0000 0000 0000 0001
int a = -8;
a >> 3;
移位前:1111 1111 1111 1111 1111 1111 1111 1000
移位前:1111 1111 1111 1111 1111 1111 1111 1111
常見位運算問題
1. 位操作實作乘除法
int a = 2;
a >> 1; ---> 1
a << 1; ---> 4
2. 位操作交貨兩數
//普通操作
void swap(int &a, int &b) {
a = a + b;
b = a - b;
a = a - b;
}
//位與操作
void swap(int &a, int &b) {
a ^= b;
b ^= a;
a ^= b;
}
位與操作解釋:第一步:a ^= b ---> a = (a^b);
第二步:b ^= a ---> b = b^(a^b) ---> b = (b^b)^a = a
第三步:a ^= b ---> a = (a^b)^a = (a^a)^b = b
3. 位操作判斷奇偶數
if(0 == (a & 1)) {
//偶數
}
4. 位操作交換符號
int reversal(int a) {
return ~a + 1;
}
整數取反加1,正好變成其對應的負數(補碼表示);負數取反加一,則變為其原碼,即正數
5. 位操作求絕對值
int abs(int a) {
int i = a >> 31;
return i == 0 ? a : (~a + 1);
}
上面的操作可以進行最佳化,可以將 i == 0 的條件判斷語句去掉。我們都知道符號位 i 只有兩種情況,即 i = 0 為正,i = -1 為負。對於任何數與 0 異或都會保持不變,與 -1 即 0xffffffff 進行異或就相當於對此數進行取反,因此可以將上面三目元算符轉換為((a^i)-i),即整數時 a 與 0 異或得到本身,再減去 0,負數時與 0xffffffff 異或將 a 進行取反,然後在加上 1,即減去 i(i =-1)
int abs2(int a) {
int i = a >> 31;
return ((a^i) - i);
}
6. 位操作進行高低位交換
34520的二進制表示:
10000110 11011000
將其高8位元與低8位元進行交換,得到一個新的二進制數:
11011000 10000110
其十進制為55430
從上面移位操作我們可以知道,只要將無符號數 a>>8 即可得到其高 8 位移到低 8 位,高位補 0;將 a<<8 即可將 低 8 位移到高 8 位,低 8 位補 0,然後將 a>>8 和 a<<8 進行或操作既可求得交換後的結果。
unsigned short a = 34520;
a = (a >> 8) | (a << 8);
7. 位操作進行二進制逆序
將無符號數的二進制表示進行逆序,求取逆序後的結果,如
數34520的二進制表示:
10000110 11011000
逆序後則為:
00011011 01100001
它的十進制為7009
在字串逆序過程中,可以從字串的首尾開始,依次交換兩端的數據。在二進制中使用位的高低位交換會更方便進行處理,這裏我們分組進行多步處理。
交換前: 10 00 01 10 11 01 10 00
交換後: 01 00 10 01 11 10 01 00
交換前: 0100 1001 1110 0100
交換後: 0001 0110 1011 0001
交換前: 00010110 10110001
交換後: 01100001 00011011
交換前: 0110000100011011
交換後: 0001101101100001
對於上面的第一步,依次以 2 位作為一組,再進行組內高低位交換,這樣處理起來比較繁瑣,下面介紹另外一種方法進行處理。先分別取原數 10000110 11011000 的奇數位和偶數位,將空余位用 0 填充:
原數: 10000110 11011000
奇數位: 10000010 10001000
偶數位: 00000100 01010000
再將奇數位右移一位,偶數位左移一位,此時將兩個數據相或即可以達到奇偶位上數據交換的效果:
原數: 10000110 11011000
奇數位右移一位: 0 10000010 1000100
偶數位左移一位:0000100 01010000 0
兩數相或得到: 01001001 11100100
上面的方法用位操作可以表示為:
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1)
同理,可以得到其第二、三和四步為:
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2)
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4)
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8)
因此整個操作為:
unsigned short a = 34520;
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1);
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2);
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4);
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8);
8. 位操作統計二進制中 1 的個數
統計二進制1的個數可以分別獲取每個二進制位數,然後再統計其1的個數,此方法效率比較低。這裏介紹另外一種高效的方法,同樣以 34520 為例,我們計算其 a &= (a-1)的結果:
count = 0
while(a){
a = a & (a - 1);
count++;
}
歡迎各位知友關註力扣官方微信公眾號:「 LeetCode力扣 」,更多關於程式設計師面試、技術幹貨的內容等你來啃!