荐 七十八、Python | Leetcode位运算系列

@Author：Runsen
@Date：2020/7/5

人生最重要的不是所站的位置，而是内心所朝的方向。只要我在每篇博文中写得自己体会，修炼身心；在每天的不断重复学习中，耐住寂寞，练就真功，不畏艰难，奋勇前行，不忘初心，砥砺前行，人生定会有所收获，不留遗憾 （作者：Runsen ）

作者介绍：Runsen目前大三下学期，专业化学工程与工艺，大学沉迷日语，Python， Java和一系列数据分析软件。导致翘课严重，专业排名中下。.在大学60%的时间，都在CSDN。决定今天比昨天要更加努力。
前面文章，点击下面链接

我的Python教程，不断整理，反复学习

今日，我决定继续更新Python教程，今天就开始了七十八、Python | Leetcode位运算系列。

位运算

位运算，计算机内所有的数都以二进制存储，位运算是对二进制位的操作

按位“与”运算

按位“与”运算的运算符是：&。首先我声明一个变量i等于11，j等于2，然后我们计算i和j的按位“与”运算，也就是11&2，得到的结果是2.‘

个2是怎么来的，首先我们要把这个11和这个2全部转换成二进制，我们从上图看出11的二进制是0b1011，2的二进制是0b10。0b这个它就是一个二进制的标识位，就是告诉我们这个是二进制。

按照位“与”运算的原则，如果两个值相应的位置都为1也就是上下都为1的时候，那么该结果就是1，如果有一个不是1，那么就是0

1011
0010
----
0010

所以，1011和0010的按位“与”运算就是0010,然后将二进制的0010转化为十进制，就是我们的结果2。

按位“或”运算

下面，我们介绍按位“或”运算。按位“或”运算的运算符是：|。我们同样计算11和2的按位“或”运算，得到的结果是11。

这个结果2到底是怎么样来进行运算的？11的二进制是1011，而2的二进制是0010。

按照位“或”运算的原则，如果两个值相应的位置有一个是1,那么该结果就是1，也就是如果都是0，该结果就是0

1011
0010
----
1011

所以，1011和0010的按位“与”运算就是1011,然后将二进制的1011转化为十进制，就是我们的结果11。

按位“异或”运算

下面，我们介绍按位“异或”运算。按位“异或”运算的运算符是：^。我们同样计算11和2的 按位“异或”运算，得到的结果是9。

这个结果9到底是怎么样来进行运算的？11的二进制是1011，而2的二进制是0010。

按位“异或”运算的原则，如果两个值相应的位置相同1,那么该结果就是0，也就是如果都是0或者都是1，该结果就是0.同样只有是1和0，那些结果就是1

1011
0010
----
1001

所以，1011和0010的按位“异或”运算就是1001,然后将二进制的1001转化为十进制，就是我们的结果9。

按位取反运算

下面，我们介绍按位取反运算。按位“异或”运算的运算符是：~。我们计算11的按位取反运算，得到的结果是-12。

这个结果-12到底是怎么样来进行运算的？按位取反的计算结论是：~n = -(n+1)

因此，11的按位取反运算 ：~11=-(11+1)=-12

左移运算符

下面，我们介绍左移运算符。左移运算符是：<<。我们计算11的左移2位的运算，得到的结果是44。

这个结果44到底是怎么样来进行运算的？左移2位，就是1011往左移动2位，然后用0来补充，变成了101100。本来在这里向左边移动，其实是后边舍弃掉2位

1011
----
101

所以，1011的右移2位的”运算就是101100,然后将二进制的101100转化为十进制，就是我们的结果44。

右移运算符

下面，我们介绍右移运算符。右移运算符是：>>。我们计算11的右移2位的运算，得到的结果是2。

这个结果2到底是怎么样来进行运算的？右移2位，就是1011往右移动2位，然后右边的11直接去除，变成了10。本来在这里向右边移动，其实是后边删除位数。

1011
----
10

所以，1011和的左移2位的”运算就是10,然后将二进制的10转化为十进制，就是我们的结果2。下表就是总结。

符号	意义	示例
~	逻辑非运算	~a
&	逻辑与运算	a&b
|	逻辑或运算	a|b
<<	位左移运算	a<<2
>>	位右移运算	a>>2

判断奇数还是偶数

通常判断奇数还是偶数我们想到的办法就是除以2，看余数是否为0。
Python代码如下：

def isodd(x):
    return True if (x % 2 <> 0) else False

如何使用位运算呢？

我们只需要使用&运算，与1进行&，如果为1，那么该数为奇数；如果为0，那么该数是偶数，Python代码如下：

def isodd(x):
    return True if (x & 1) else False

左移一位相当于乘以2，右移一位相当于除以2

在面试的过程中，通常会遇到的一个问题是写二分查找代码。
二分查找的代码如下：

def binary_search(list, item):
    '''
    :param list: 有序列表
    :param item: 要查找的元素
    :return: item在list中的索引，若不在list中返回None
    '''
    low = 0
    high = len(list) - 1
    while low <= high:
        midpoint = (low + high) // 2
        if list[midpoint] == item:
            return midpoint
        elif list[midpoint] < item:
            low = midpoint + 1
        elif list[midpoint] > item:
            high = midpoint - 1
    return None

其中有一步是需要取最小小标和最大下标的中间值，若使用位运算符，midpoint = (low + high) >> 1，面试官肯定会对你刮目相看。

数值交换

数值交换的代码相信大家都非常熟悉了，因为似乎是从学编程语言的最开始就一直用：

temp = b
b = a
a = temp
# a,b =b,a

但是怎么使用位运算来完成此功能呢？

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

确实比较难理解，原理是什么呢？
第一行，a = a ^ b，很容易理解；
第二行， b = b ^ a = b ^ a ^ b，由于 b ^ b = 0，所以 b = a ^ 0，即 b = a;
第三行， a = a ^ b ,由于a在第一步重新赋值，所以，a = a ^ b ^ a = b，完成了数值交换。

下面就是位运算常见用法总结

判断x的奇偶数

x % 2 == 1 // 常规写法
x & 1 == 1 // 为真奇数，为假偶数

计算中位数

mid = (left + right) / 2  // 常规写法
mid  = (left + right) >> 1 // 位运算

交换两个数

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

LeetCode 第 78题：子集

#给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 
# 说明：解集不能包含重复的子集。 
# 示例: 
# 输入: nums = [1,2,3]
#输出:
#[
#  [3],
#  [1],
#  [2],
#  [1,2,3],
#  [1,3],
#  [2,3],
#  [1,2],
#  []
#] 
# Related Topics 位运算 数组 回溯算法

既然这道题让我们求的是所有的子集，那么我们可以从子集的特点入手。我们之前学过，一个含有n个元素的子集的数量是$2^n$。

使用位运算，对每一位为1的表示这一位的数字存在，例如对于输入[1,2,3] 编码i=001，表示只含有3，编码i=101.表示含有1,3

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ret = []
        n = len(nums)
        # 遍历所有的状态
        # 1左移n位相当于2的n次方
        for s in range(1 << n):
            cur = []
            # 通过位运算找到每一位是0还是1
            for i in range(n):
                # 判断s状态在2的i次方上，也就是第i位上是0还是1
                if s & (1 << i):
                    cur.append(nums[i])
            ret.append(cur[:])
        return ret

本文地址：https://blog.csdn.net/weixin_44510615/article/details/107134683