按位与(&)

按位与运算法则可以概括成“ 同真则真，反之则假 ”，在0和1之间的运算，有以下形式：

• 1&1 = 1

• 1&0 = 0

• 0&0 = 0

比如数字5和数字6之间采用按位与运算，将两个数组 8位二进制形式的每一位对应 ，运用上面的法则就可以得出一个新的数字4，即5 & 6 = 4。

按位或(|)

按位或运算法则可以概括成“ 同假才假，反之则真 ”，在0和1之间的运算，有以下形式：

• 1 | 1 = 1

• 1 | 0 = 1

• 0 | 0 = 0

同样还用数字5和数字6举例，利用上述相同方式在二者之间做按位或运算，可以得到一个新的数字7，即5 | 6 = 7。

按位异或(^)

按位异或运算法则可以概括成“ 相同则真，不同则假 ”，在0和1之间的运算，有以下形式：

• 1 | 1 = 0

• 1 | 0 = 1

• 0 | 0 = 0

仍然还是数字5与数字6为例利用上述相同方式在二者之间做按位异域运算，可以得到一个新的数字3，即5 ^ 6 = 3。

左移(<<)

左移操作就是将一个数字的二进制形式整体向左移动，然后右边的 虚位补0 ，具体移动看下图：

这个例子是2<<2 = 8的体现，可以看到1原本处于右边第2位，如果整体向左移动两位，那么1就移动到了右边第4位，空下的两位用0补上即可。

右移(>>)

右移操作与左移操作方式相同，方向相反，具体移动看下图：

这个例子是6>>2 = 1的体现，只需要整体向右移动两位，然后左边虚位补0，不需要顾虑会不会有1被覆盖。

这两个符号比较容易混乱，这里给一个自己的小Tips： 箭头朝哪向哪移，左移值增大，左移值减小。

取反(~)

取反操作就比较简单了，只需要记住这样一个小式子: ~x = -(x+1) ，比如数字5取反操作就等于-6，即~5 = -(5+1) = -6。

已经介绍完了这六个位运算符是如何对二进制进行操作的，可是简单的介绍并不能体现出位运算的高大上，下面利用位运算的技巧解决一些问题，这些问题并不是很难，但是我们从中可以认识到位运算的便捷，以及加深对位运算操作的印象。

交换两个数字

对于这个问题可能我们想到的第一个方法就是利用 第三个变量 来帮助交换，比如若要交换a、b两个变量的值，就需要定义一个临时变量temp辅助。

a =  1 ;b =  2

temp =  0

temp = a; a = b; b = temp

这样做是需要额外存储空间的，那有没有一种方法仅在原地就可以交换a、b两个变量的值呢？位运算就可以，而且十分简单。

a = a^b  #(1)

b = a^b  #(2)

a = a^b 

#(3)

如果你没接触过位运算，对于这三行代码肯定很懵，读懂这三行代码你还需要知道按位异或的几个性质：

• 1.按位异或满足交换律，即a ^ b = b ^ a

• 2.按位异或满足结合律，即(a^b)^c=a^(b^c)

• 3.任何数与0异或都等于它自己，比如a ^ 0 = a。

若将式子(1)代入式子(2)，利用上述性质并结合按位异或“ 相同则假 ”的法则，可以将式子(2)变成以下形式：

b = a^b^b = a^ 0 = a

这样a的值就赋给b了，如果再将求出的式子(2)代入式子(3)，式子(3)则变成：

a = a^a^b =  0 ^b = b

这样就完成了变量a、b之间的调换，是不是已经有NiuBi的感觉了，继续看下一道。

2的幂

假设给定一个数字，你需要判断它是否为2的幂，如果是，需要返回true，反之就返回false。

这个问题利用循环方法也比较不错，设定一个循环条件，然后让输入整数n一直除以2，最后只需要判断n是否等于1即可，因为n==1只有当n为2的幂时才满足。

这种方法应该算是一种很普通的方法了，体现不出自己的逼格怎么办？看看利用位运算是怎么解决的吧。

return n >  0 and n & (n -  1 ) ==  0

如果n是2的幂的话，则其二进制最高位上应该为1，其余位置都应该为0 ，比如8的二进制为1000； 对于n-1的话，则应该是除了最高位为0，其余都为1 ，比如7的二进制为0111，所以此时n&(n-1)=0。

找不同

假如给定一个只包含小写字母的字符串s1,然后字符串s2是将s1打乱并且向其中插入了一个新的小写字母，想让你挑出这个新插入的字母。比如s1 = 'abc',s2 = 'badc'，输出d。

第一种想法就是利用哈希表来统计并存储每个元素出现的次数，出现一次的就是新加入的元素，而利用哈希表就意味着 需要空间新建字典 。而利用按位异或运算只需 引入一个第三变量 就可以解决这个问题，利用上文提及的异或性质1和3、以及“相同则假”的法则即可。

m = s1+s2

first =  0

for i  in range( 0 ,len(m)):

first ^= ord(m[i])

return

chr(first)

这里ord是将字母转为对应的Ascii码，chr则是将Ascii码数字转回为对应的字母形式。

翻转二进制

先以8位的二进制举例，比如输入的二进制为000100111，要求输出为11001000。

整数翻转利用字符串就可以很好的解决，但是二进制不同于整数，因为二进制中有很多0，可能在翻转并转化之后有些0会被抹去。这里就可以利用位运算实现二进制的翻转，具体代码如下：

res =  0

for i  in range( 8 ):

res <<=  1

res += n &  1

n >>=  1

return

bin(res)

这里利用 按位与“同真则真，反之则假” 的法则，每次将输入的二进制最后一位与1比较，得出的结果加至res上，然后将n右移一位，因为此时最后一位已经比较过了。

在每次遍历开始时要注意将res左移一位，因为 不论n&1得到的结果是0还是1，它在二进制中都是有意义的，需要为这个即将得出的数提供一个空地，不可以省略 。这里推荐自己手推一下，很容易就理解了。

1个数的奇偶

还是给定一个8位的二进制，统计这8个数字中1个数的奇偶性，若1个数为奇数，则返回1；若1个数为偶数，则返回0。比如00110111，里面一共有5个1，所以应该返回1。

这道题利用位运算的思路和上一道有些相似，也是利用 按位与“同真则真，反之则假” 的法则，循环遍历这8个数字，用计数器count统计1的个数，最后用count&1判断count的奇偶性即可，奇数返回1，偶数则返回0。

但是这并不是位运算最NiuBi之处，下面这种方法才是真的强，但是可读性可能不如上面的方法。

仍用00110111举例，将n与n>>1做异或操作，得到一个新的二进制，具体如下：

新二进制中0的意义表示该位置与前一个位置共有偶数个1,1则表示该位置与前一个位置共有奇数个1 。比如New中第6位的1表示Num1中第5位和第6位共有奇数个1，可以看到Num1中对应位置为01是符合的，同理可以对比一下其他位置也是具有这个性质。

同理移动2位(上图) 表示该位置与前三个位置(上次已知1个，这次移动两个)1个数的奇偶性 、 移动 4位 表示该位置与前七个位置1个数的奇偶性 ， 所以当移动4位后末位的数字就表示整个8位二进制中1的奇偶性 ，如果末位为1，则代表有奇数个1；如果末位为0，则代表有偶数个1。

上文例题部分来源于力扣(LeetCode)

总结

位运算可能很多人都知道，但是在解题的时候却很少用到，因为有很多通俗易懂的方法可以代替位运算，但是位运算的功能是非常很强大的，值得学习一下。通过上面例子也可以发现位运算解决某些问题真的是很便捷，但对不理解的人可读性会比较差，同时这也是位运算可以ZhuangBi之处。

相关文章