珠海工程建設(shè)信息網(wǎng)站快速網(wǎng)站輕松排名
目錄
文章目錄:本章講解的主要是刷題系列
? ? ? ? 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è)贊哦!!
????????