当前位置: 首页 > 科技观察

【推荐收藏】面试官的位运算奇葩技巧

时间:2023-03-15 08:48:17 科技观察

前言位运算隐藏在编程语言的角落。它神秘而强大,隐藏着内功。有的人光听位运算的名字就觉得不自在看到位运算的人就很远了,我以前也是这样。但是狡猾的面试官往往喜欢搞偷袭,抓住我们的弱点来攻击我们。为了防患于未然,特将本文记录下来!这篇文章的内容是位运算的介绍和一些经典位运算的介绍和分析。当然,位运算这么好,后面还要总结一下。认识位运算什么是位运算?程序中的所有数字都以二进制形式存储在计算机内存中。按位运算直接对内存中整数的二进制位进行操作。位运算是对二进制数的直接运算,那么位运算有哪几种呢?常用运算符有与(&)、或(|)、异或(^)、取反(~)、左移(<<)、右移(>>有符号右移>>>无符号右移)。让我们仔细看看每个位操作的规则。位运算&(与)规则:对二进制对应位进行逻辑与运算(只有当对应位的值为1时,结果为1,否则为0)即0&0=0,0&1=0,1&1=1例如:2&-2位操作|(or)规则:二进制中两个对应位的逻辑或运算(如果其中一个对应位为1,则为1)即0|0=0,0|1=1,1|1=1例如:2|-2位运算^(异或)规则:对二进制对应位进行逻辑异或(异或)运算(对应位的值不同时为1,否则为0)即0^0=1,0^1=0,1^1=1例如:2^-2按位取反~规则:二进制0变为1,1变为0移位运算符左移操作<<:左移后,右位补0右移操作>>:右移后,左位补原最左位的值(可能为0,也可能为1)右移操作>>>:右移后,左位补0补0。对于左移运算符<<,没有悬念。右边填零相当于整数乘以2,不管是正数还是负数。右移运算符有区别,分别左边补0>>>左边补原位>>,如果是正数左边补0达到效果除以2;如果是负数左边填0>>>那么这个值的符号会发生变化,由一个负数变成一个比较大的正数。而如果在左边补原位(负数补1)>>那么整数还是负数,相当于除以2的效果。下图可以帮助大家理解移位运算符负数很好:至此,我想你应该对位运算有了初步的了解,让你看看上面提到的一些案例的实现。理解起来可能会更清楚:位操作技巧下面介绍一些常用的位操作技巧。判断奇偶数在正常判断奇偶数的时候,我们会这样写:if(n%2==1)//n是奇数}使用位运算可以这样写:if(n&1==1){//n是奇数。}它的核心是判断二进制的最后一位是否为1,如果为1,那么加上2^0=1的结果一定是奇数,否则就是偶数。交换两个号码对于传统的交换两个号码,我们需要用一个变量来辅助完成操作,可能是这样的:intteam=a;a=b;b=team;但是使用位运算可以在不增加额外空间的情况下进行值交换:a=a^b;//a=a^bb=a^b;//b=(a^b)^b=a^0=aa=a^b;//a=(a^b)^(a^b^b)=0^b=0的原理在评论里已经写了。是不是感觉很屌?当二进制枚举遇到子集问题时,我们有时会使用二进制枚举来遍历各种状态(效率比dfs回溯)。这类问题属于排列组合问题。对于每一个物品(位置),都是使用和不使用两种状态,可以用二进制的1和0来表示。在实现上,通过枚举数的范围来分析每个二进制数的每个符号位的特征来进行计算和求解操作就足够了。二进制枚举的代码实现是:for(inti=0;i<(1<>1);二进制中1的个数是一道经典题。剑指offer里面也有相应的问题。具体问题要求输入一个整数,输出该数二进制表示中1的个数(其中负数用补码表示)。对于这个问题,也可以直接枚举字符'1'的个数,而不用位运算转换成二进制字符串,但是这样没有灵魂,效率也很低。这里有两个解决方案。一:大家都知道,每一类数据背后其实都是二元运算。大家都知道int数据类型的取值范围是(-2^31,2^31-1)。而int有32位。但并非所有32位都用于表示数据。实际用来表示数据大小的也是31位。最高位用于指示正??或负。首先,你要知道:其次,你要知道位运算&与。两个十进制与操作。每一位都等于1。所以我们用2的正次方和已知的数分别进行AND运算。如果结果不为0,则表示该位为1。(前31位的后31位都大于0,结果为负数,但如果该位为1,则结果肯定不为0)具体代码实现为:publicintNumberOf1(intn){intva=0;for(inti=0;i<32;i++){if((n&(1<>i)&1)==1){sum++;}}if(sum%3==1)value+=(1<>index)&1)==0)//如果这个数的index为0和num1XORnum1^=nums[i];else//否则与num2num2^=nums[i];}value[0]=num1;value[1]=num2;returnvalue;}privateintgetFirst1(intval){intindex=0;while(((val&1)==0&&index<32)){val>>=1;//val=val/2index++;}returnindex;}结论当然上面的问题可能还有更好的解决方法,还有更多经典的位运算题会总结出来之后。希望这篇位运算入门的文章能让大家有所收获,让大家对位运算有更深入的了解。对于很多问题,比如游戏问题,二进制位运算可以很巧妙的解决问题,相关内容会在以后分享,敬请期待!