苏州网站建设托管,如何在网上推广信用卡,苏州论坛,榆林市中小企业融资服务平台目录
文章目录#xff1a;本章讲解的主要是刷题系列 1#xff1a;首先会介绍 I ^这三个操作符的作用#xff0c;性质 2#xff1a;三道使用位运算操作符的经典 笔试题(来自剑指offer) 题目链接如下#xff1a; 1:136. 只出现一次的数字 - 力扣#xff08;LeetCode…目录
文章目录本章讲解的主要是刷题系列 1首先会介绍 I ^这三个操作符的作用性质 2三道使用位运算操作符的经典 笔试题(来自剑指offer) 题目链接如下 1:136. 只出现一次的数字 - 力扣LeetCode 2:剑指 Offer 15. 二进制中1的个数 - 力扣LeetCode 3:剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣LeetCode 文章正式开始~~~ 1:位运算符 ^(按位异或) (按位与) |(按位或) 首先我们得理解位运算符中这个位的含意:这个位其实就是我们平常所说的二进制位所以位运算符是用来针对二进制位(只含有0和1)进行的运算操作符。 :这个操作符的名字叫做按位与不要将他与(逻辑或)这个操作符弄混淆了的作用是将两个操作数二进制位全为1的才是1其他的位如果有0或1就会将他变成0.(简单的理解就是全1才为1否则这一位的值为0). 比如说35
35假设在32位平台下
3的二进制位00000000 00000000 00000000 000000115的二进制位00000000 00000000 00000000 0000010135 00000000 00000000 00000000 00000001全1才为1其它都为0 |(按位或):这个操作符与上面的操作符有异曲同工之妙只是它的作用与相反二进制位上全0才为0有1就为1. 3|5的结果如下 3|5
假设在32位平台下
3的二进制位00000000 00000000 00000000 000000115的二进制位 00000000 00000000 00000000 00000101
3|5的结果 00000000 00000000 00000000 00000111 ^按位异或二进制位相同的为0相异的为1 与此同时^操作符具有交换律与结合律的特点比如说a^a0 因为二进制位全部相同 a^0a; 0不会改变它原有的位 a^ b^ab,这里就体现了它的性质相当于a^a^ b . 知识点已经铺垫完毕让我们进入习题的讲解吧。 2经典笔试题(位运算) 题目的难度是由简单到难的哦 1 136. 只出现一次的数字 - 力扣LeetCode 这道题也可以称作单身狗问题(dog) 首先这个题目的意思就是给我们一个数组然后数组中有一个数只出现了1次其它的数均出现了2次。 这里我们就可以联想到我们上面所讲的^操作符的性质a^a0; 0^aa; 因为数组中有数字出现了2次,那么我们使用^之后就可以消除这两个相同的数了到最后数组中留下的数字就是那个唯一出现1次的数字 代码
int singleNumber(int* nums, int numsSize){int ret 0;int i 0;for(i0;inumsSize;i){ret^nums[i];}return ret;
} 这道题就很巧妙的使用了^操作符当然这个题可能还有其它的算法比如说排序加计数哈希表...都可以用来实现这个算法。但是我们因为讲的是位操作符所以就使用了位运算操作符。 2剑指 Offer 15. 二进制中1的个数 这道题我会用两种解法来讲解这道题: 方法一移位操作符 加上 运算符 计数 思路假设我们知道一个数因为1的二进制位只有最右边的1位为1其它的位都为0所以我们将所需要计算数的二进制位的每1位都与1进行运算 代码
int hammingWeight(uint32_t n) {int count0;int i 0;for(i0;i32;i){if(((ni)1)1)count;}return count;
} 方法2将我们所需要求的数的最后一位的1消除循环进行下去。 思路nn(n-1); 我们举个列子来讲解 代码实现 int hammingWeight(uint32_t n) {int count0;while(n){count;nn(n-1);}return count;
} 3:剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣LeetCode 这道题相对于前面两道题就有一定的难度了并没有上面两道题那么直接 我们通过实际的列子来进行讲解 我们在这里采用的思想就是分组异或 那么什么又叫分组异或呢 比如说我们可以把 1 1 3 3 5放在一个数组 把2 2 4 4 6放在另外一个数组这样我们对每一个数组进行异或就可以得到 5 和6 了。 那么我们如何进行分组呢 首先我们将数组中的所有数字进行异或得到 5^6,又因为两个数字不可能相等所以异或起来肯定不为1那么结果中的数二进制位中肯定有一位为1那么我们就可以利用这个1来进行分组了。 比如5^6 因为5与6在这一位的不同所以我们将在这一位与5相同的数放进一个组与5不相同的数我们放到另外的一个数组中然后分别异或就可以得到答案了。
那么如何找到5与6哪一位不同呢 首先我们异或整个数组得到5与6的^值然后将这个值的每一位与1进行运算如果找到1位的结果为1那么我们就可以将这个位置给标记出来然后再让我们原数组中的每个值移动pos位如果与它等于1我们用dog1将它^起来不等于1那么我们用dog2将它^起来 所以最终我们的dog1为其中的一个值dog2为其中的第二个值。 代码
int* singleNumbers(int* nums, int numsSize, int* returnSize){int*ret(int*)malloc(sizeof(int)*2);int i 0;int pos0;int a0;for(i0;inumsSize;i){a^nums[i];}//a现在为两个数字的异或值 a^b0//标记那个位置为1for(i0;i32;i){if(ai11){posi;break;}}int dog10;int dog20;//根据pos位置分为两个数组直接异或就是我们所需要的答案了for(i0;inumsSize;i){if((nums[i]pos)11){dog1^nums[i];}else{dog2^nums[i];}}ret[0]dog1,ret[1]dog2;* returnSize2;return ret;
}本章的经典例题讲解完毕感谢大家的观看~~ 如果觉得对你有用的话可以点个赞哦
