1.位運(yùn)算解題技巧

1、使用 x & 1 == 1 判斷奇偶數(shù)。（注意，一些編輯器底層會(huì)把用%判斷奇偶數(shù)的代碼，自動(dòng)優(yōu)化成位運(yùn)算）
2、不使用第三個(gè)數(shù)，交換兩個(gè)數(shù)。x = x ^ y ， y = x ^ y ， x = x ^ y。（早些年喜歡問到，現(xiàn)在如果誰再問，大家會(huì)覺得很low）
3、兩個(gè)相同的數(shù)異或的結(jié)果是 0，一個(gè)數(shù)和 0 異或的結(jié)果是它本身。（對(duì)于找數(shù)這塊，異或往往有一些別樣的用處。）
4、x & (x - 1) ，可以將最右邊的 1 設(shè)置為 0。（這個(gè)技巧可以用來檢測(cè) 2的冪，或者檢測(cè)一個(gè)整數(shù)二進(jìn)制中 1 的個(gè)數(shù)，又或者別人問你一個(gè)數(shù)變成另一個(gè)數(shù)其中改變了多少個(gè)bit位，統(tǒng)統(tǒng)都是它）
5、異或可以被當(dāng)做無進(jìn)位加法使用，與操作可以用來獲取進(jìn)位。
6、i+(~i)=-1，i 取反再與 i 相加，相當(dāng)于把所有二進(jìn)制位設(shè)為1，其十進(jìn)制結(jié)果為-1。
7、對(duì)于int32而言，使用 n >> 31取得 n 的正負(fù)號(hào)。并且可以通過 (n ^ (n >> 31)) - (n >> 31) 來得到絕對(duì)值。（n為正，n >> 31 的所有位等于0。若n為負(fù)數(shù)，n >> 31 的所有位等于1，其值等于-1）
8、使用 (x ^ y) >= 0 來判斷符號(hào)是否相同。（如果兩個(gè)數(shù)都是正數(shù),則二進(jìn)制的第一位均為0,x ^ y=0；如果兩個(gè)數(shù)都是負(fù)數(shù),則二進(jìn)制的第一位均為1；x ^ y=0 如果兩個(gè)數(shù)符號(hào)相反,則二進(jìn)制的第一位相反,x ^ y=1。有0的情況例外，^相同得0，不同得1）
9.a-b結(jié)果的符號(hào)(int 類型)，可以用(a-b)>>31得出，-1則是為負(fù)，0為正數(shù)

2.異或(^)與與(&)左移(<<)做加法運(yùn)算

無進(jìn)位和 與 異或運(yùn)算 規(guī)律相同，進(jìn)位 和 與運(yùn)算 規(guī)律相同

那么每異或一次，相當(dāng)于求一次兩數(shù)無進(jìn)位和，每做一次與運(yùn)算加左移，相當(dāng)于求出所有進(jìn)位的和，再與第一次異或的結(jié)果再次異或，如此循環(huán)，當(dāng)沒有進(jìn)位時(shí)即進(jìn)位和為0時(shí)，代表求出最終結(jié)果

C++代碼

class Solution { public:int add(int a, int b) {while(b!=0){int c=(unsigned int)(a&b)<<1;a=a^b;b=c;}return a;} };

3.異或(^)的妙用

那么如果把一個(gè)數(shù)組的所有元素全部異或一遍，那么最終得到的結(jié)果是兩個(gè)不重復(fù)值的異或結(jié)果，又由于異或是相同得0不同得1，我們找到異或結(jié)果從低位到高位的第個(gè)位1(哪一位1都無所謂)，那么異或的兩個(gè)值，一個(gè)此位置為0，一個(gè)此位置為1，就可以把數(shù)組的元素分為兩組，這個(gè)時(shí)候，此位置為1的數(shù)據(jù)與a異或，為0的數(shù)據(jù)與b異或，最終a和b就是兩個(gè)我們需要的數(shù)據(jù)(其余數(shù)據(jù)的異或會(huì)得到0，因?yàn)槠溆鄶?shù)字都出現(xiàn)兩次)

class Solution { public:vector<int> singleNumbers(vector<int>& nums) {//用于將所有的數(shù)異或起來int k = 0;for (int num : nums) {k ^= num;}//獲得k中最低位的1,K里面兩數(shù)不同，故肯定有一位1是不同的，可以以此區(qū)分int mask = 1;while ((k & mask) == 0) {mask <<= 1;}int a = 0; int b = 0;for (int num : nums) {if ((num & mask) == 0) {a ^= num; // 找到那位不為1的元素， 其余數(shù)為偶數(shù)，會(huì)自動(dòng)消去} else {b ^= num; // 找到那位為1的元素}}return {a, b};} };

4.0x55555555與0xaaaaaaaa的妙用

0xaaaaaaaa = 10101010101010101010101010101010 (偶數(shù)位為1，奇數(shù)位為0）
0x55555555 = 1010101010101010101010101010101 (偶數(shù)位為0，奇數(shù)位為1）

class Solution { public:int exchangeBits(int num) {int odd = num & 0x55555555;//偶數(shù)int even = num & 0xaaaaaaaa;odd = odd << 1;even = even >> 1;return odd | even;} };

5.n&(n-1)的妙用

任何一個(gè)是2的冪次方的數(shù)，它都是最高位(代表數(shù)值的位)是1，后面的數(shù)字全0，那么這個(gè)數(shù)減1與這個(gè)數(shù)進(jìn)行位于運(yùn)算一定為0，即：

class Solution { public:bool isPowerOfTwo(int n) {return (n>0)&&(n&(n-1))==0;} };

n&(n-1)每進(jìn)行一輪都會(huì)把當(dāng)前數(shù)值部分(也就是n)最低位的1變成0。比如：數(shù)值11轉(zhuǎn)化成二進(jìn)制有三個(gè)1，那么每進(jìn)行一次n=n&(n-1)就會(huì)消去當(dāng)前n最低位的1

class Solution { public:int hammingWeight(uint32_t n) {int cnt=0;while(n){n&=(n-1);++cnt;}return cnt; } };

總結(jié)

以上是生活随笔為你收集整理的详解位运算解题套路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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