前言位运算隐藏在编程语言的角落。它神秘而强大,隐藏着内功。有的人光听位运算的名字就觉得不自在看到位运算的人就很远了,我以前也是这样。但是狡猾的面试官往往喜欢搞偷袭,抓住我们的弱点来攻击我们。为了防患于未然,特将本文记录下来!这篇文章的内容是位运算的介绍和一些经典位运算的介绍和分析。当然,位运算这么好,后面还要总结一下。认识位运算什么是位运算?程序中的所有数字都以二进制形式存储在计算机内存中。按位运算直接对内存中整数的二进制位进行操作。位运算是对二进制数的直接运算,那么位运算有哪几种呢?常用运算符有与(&)、或(|)、异或(^)、取反(~)、左移(<<)、右移(>>有符号右移>>>无符号右移)。让我们仔细看看每个位操作的规则。位运算&(与)规则:对二进制对应位进行逻辑与运算(只有当对应位的值为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<
