目錄

文章目錄：本章講解的主要是刷題系列

? ? ? ? 1：首先會(huì)介紹 I & ^這三個(gè)操作符的作用，性質(zhì)

? ? ? ? 2：三道使用位運(yùn)算操作符的經(jīng)典?筆試題(來(lái)自劍指offer)

????????????????????????題目鏈接如下：

? ? ? ? ? ? ? ?1:136. 只出現(xiàn)一次的數(shù)字 - 力扣（LeetCode）

??? ? ? ? ? ? ?2:劍指 Offer 15. 二進(jìn)制中1的個(gè)數(shù) - 力扣（LeetCode）

? ? ? ? ? ? ? ?3:劍指 Offer 56 - I. 數(shù)組中數(shù)字出現(xiàn)的次數(shù) - 力扣（LeetCode）

---

文章正式開(kāi)始~~~

? ? ? ? ? 1:位運(yùn)算符? ^(按位異或) &(按位與)? |(按位或)

? ? ? ? 首先我們得理解位運(yùn)算符中這個(gè)位的含意:這個(gè)位其實(shí)就是我們平常所說(shuō)的二進(jìn)制位，所以位運(yùn)算符是用來(lái)針對(duì)二進(jìn)制位(只含有0和1)進(jìn)行的運(yùn)算操作符。

? ? ? ? &:這個(gè)操作符的名字叫做按位與，不要將他與&&(邏輯或)這個(gè)操作符弄混淆了，&的作用是將兩個(gè)操作數(shù)二進(jìn)制位全為1的才是1，其他的位如果有0或1就會(huì)將他變成0.(簡(jiǎn)單的理解就是：全1才為1，否則這一位的值為0).

? ? ? ? 比如說(shuō)：3&5

3&5假設(shè)在32位平臺(tái)下
3的二進(jìn)制位：00000000 00000000 00000000 000000115的二進(jìn)制位：00000000 00000000 00000000 000001013&5         00000000 00000000 00000000 00000001全1才為1，其它都為0     

? ? ? ?

? ? ? ? |(按位或):這個(gè)操作符與上面的操作符有異曲同工之妙，只是它的作用與&相反，二進(jìn)制位上全0才為0，有1就為1.

? ? ? ? 3|5的結(jié)果如下：

????????

3|5
假設(shè)在32位平臺(tái)下
3的二進(jìn)制位：00000000 00000000 00000000 000000115的二進(jìn)制位： 00000000 00000000 00000000 00000101
3|5的結(jié)果    00000000  00000000 00000000 00000111

? ? ^按位異或：二進(jìn)制位相同的為0，相異的為1 ，與此同時(shí)^操作符具有交換律與結(jié)合律的特點(diǎn)，比如說(shuō)：a^a=0 因?yàn)槎M(jìn)制位全部相同? ?a^0=a;? 0不會(huì)改變它原有的位? ? a^ b^a=b,這里就體現(xiàn)了它的性質(zhì)，相當(dāng)于a^a^ b?.

? ? ? ?知識(shí)點(diǎn)已經(jīng)鋪墊完畢，讓我們進(jìn)入習(xí)題的講解吧。

? ?2：經(jīng)典筆試題(位運(yùn)算)

? ? ? ? 題目的難度是由簡(jiǎn)單到難的哦！

? ? ? ? 1：??136. 只出現(xiàn)一次的數(shù)字 - 力扣（LeetCode）

????????

? ? ? ? 這道題也可以稱(chēng)作單身狗問(wèn)題(dog)

? ? ? ? 首先這個(gè)題目的意思就是：給我們一個(gè)數(shù)組，然后數(shù)組中有一個(gè)數(shù)只出現(xiàn)了1次，其它的數(shù)均出現(xiàn)了2次。

? ? ? ? 這里我們就可以聯(lián)想到我們上面所講的^操作符的性質(zhì)：a^a=0; 0^a=a;

? ? ? ? 因?yàn)閿?shù)組中有數(shù)字出現(xiàn)了2次,那么我們使用^之后就可以消除這兩個(gè)相同的數(shù)了，到最后數(shù)組中留下的數(shù)字就是那個(gè)唯一出現(xiàn)1次的數(shù)字

? ? ? ? 代碼：

int singleNumber(int* nums, int numsSize){int ret =0;int i =0;for(i=0;i<numsSize;i++){ret^=nums[i];}return ret;
}

? ? ? ? 這道題就很巧妙的使用了^操作符，當(dāng)然這個(gè)題可能還有其它的算法，比如說(shuō)排序加計(jì)數(shù)，哈希表...都可以用來(lái)實(shí)現(xiàn)這個(gè)算法。但是我們因?yàn)橹v的是位操作符，所以就使用了位運(yùn)算操作符。

2：劍指 Offer 15.?二進(jìn)制中1的個(gè)數(shù)

? ? ? ? 這道題我會(huì)用兩種解法來(lái)講解這道題:

? ? ? ? 方法一：移位操作符? ? 加上? ? ? ?&運(yùn)算符 +計(jì)數(shù)

? ? ? ? 思路：假設(shè)我們知道一個(gè)數(shù)因?yàn)?的二進(jìn)制位只有最右邊的1位為1其它的位都為0，所以我們將所需要計(jì)算數(shù)的二進(jìn)制位的每1位都與1進(jìn)行&運(yùn)算

? ? ? ? 代碼：

int hammingWeight(uint32_t n) {int count=0;int i =0;for(i=0;i<32;i++){if(((n>>i)&1)==1)count++;}return count;
}

? ? ? ? 方法2：將我們所需要求的數(shù)的最后一位的1消除，循環(huán)進(jìn)行下去。

? ? ? ? 思路：n=n&(n-1);

? ? ? ? 我們舉個(gè)列子來(lái)講解：

????????? ? ? ? 代碼實(shí)現(xiàn)：

????????

int hammingWeight(uint32_t n) {int count=0;while(n){count++;n=n&(n-1);}return count;
}

?? ? ? 3:劍指 Offer 56 - I. 數(shù)組中數(shù)字出現(xiàn)的次數(shù) - 力扣（LeetCode）

????????

? ? ? ? 這道題相對(duì)于前面兩道題就有一定的難度了，并沒(méi)有上面兩道題那么直接：

? ? ? ? 我們通過(guò)實(shí)際的列子來(lái)進(jìn)行講解

????????? ? ? ? 我們?cè)谶@里采用的思想就是分組異或

? ? ? ? 那么什么又叫分組異或呢？

? ? ? ? 比如說(shuō)我們可以把? 1? 1? 3 3 5放在一個(gè)數(shù)組? 把2? 2 4 4 6放在另外一個(gè)數(shù)組，這樣我們對(duì)每一個(gè)數(shù)組進(jìn)行異或就可以得到? 5 和6 了。

? ? ? ? 那么我們?nèi)绾芜M(jìn)行分組呢？

? ? ? ? 首先我們將數(shù)組中的所有數(shù)字進(jìn)行異或得到? 5^6,又因?yàn)閮蓚€(gè)數(shù)字不可能相等所以異或起來(lái)肯定不為1，那么結(jié)果中的數(shù)二進(jìn)制位中肯定有一位為1，那么我們就可以利用這個(gè)1來(lái)進(jìn)行分組了。

? ? ? ? 比如5^6

????????

????????因?yàn)?與6在這一位的不同，所以我們將在這一位與5相同的數(shù)放進(jìn)一個(gè)組，與5不相同的數(shù)我們放到另外的一個(gè)數(shù)組中，然后分別異或就可以得到答案了。

那么如何找到5與6哪一位不同呢？

????????首先我們異或整個(gè)數(shù)組得到5與6的^值，然后將這個(gè)值的每一位與1進(jìn)行&運(yùn)算，如果找到1位&的結(jié)果為1那么我們就可以將這個(gè)位置給標(biāo)記出來(lái)，然后再讓我們?cè)瓟?shù)組中的每個(gè)值移動(dòng)pos位如果與它&等于1，我們用dog1將它^起來(lái)，不等于1那么我們用dog2將它^起來(lái)

? ? ? ? 所以最終我們的dog1為其中的一個(gè)值，dog2為其中的第二個(gè)值。

? ? ? ? 代碼：

int* singleNumbers(int* nums, int numsSize, int* returnSize){int*ret=(int*)malloc(sizeof(int)*2);int i =0;int pos=0;int a=0;for(i=0;i<numsSize;i++){a^=nums[i];}//a現(xiàn)在為兩個(gè)數(shù)字的異或值 a^b！=0//標(biāo)記那個(gè)位置為1for(i=0;i<32;i++){if(a>>i&1==1){pos=i;break;}}int dog1=0;int dog2=0;//根據(jù)pos位置分為兩個(gè)數(shù)組，直接異或就是我們所需要的答案了for(i=0;i<numsSize;i++){if((nums[i]>>pos)&1==1){dog1^=nums[i];}else{dog2^=nums[i];}}ret[0]=dog1,ret[1]=dog2;* returnSize=2;return ret;
}

? ? ? ? 本章的經(jīng)典例題講解完畢，感謝大家的觀看~~

? ? ? ? ? ? ? ? 如果覺(jué)得對(duì)你有用的話，可以點(diǎn)個(gè)贊哦！！

????????