Python 刷题笔记：位运算专题二

昨天笔记里对原码、反码、补码的描述有误，这里更正下：

正数三码相同，负数的反码才会除了首位符号位不变、其余位取反。位运算都是基于数字的补码来进行运算的。

昨天题目中代码结尾处有个特殊处理没来得及验证，今天细说下：

由于 Python 3 中整数是动态长度，并不是像其它语言中一般被限制到 32 位，所以通常如果涉及到复杂些的位运算，会通过整除一个 33 位的首位为 1、其余位全部为 0 的数来限制到 32 位——而这个除数在十进制中也就是 2 的 32 次方、用 16 进制则表示为 0x100000000，比如：

temp = 2**40+2
MASK = 0x100000000
result = temp%MASK

同时，32 位最小的负数为 32 位全部为 1，即十进制中的负（2 的 31 次方-1），十六进制中的负 0x7FFFFFFF，对于比其更小的数字 a, 我们昨天代码中的处理方式是 MIN_INT = 0x7FFFFFFF + 1, a%MIN_INT 即只保留 31 位，然后将结果与 0x7FFFFFFF 进行异或运算，即除了符号位全部取反，最后再按位取反，即符号位也取反，就能拿到负数结果。

比如我们对 -20 经过一番处理，仍旧可以取回 -20，但 -2「35 超出下限，就只返回 -2」31（这里貌似应该 - 1 的，之前代码中对数字是先整除 MASK 保证 32 位的，所以和这里会略有差异）

可以看到，上面这种处理方式比较绕，为了避开这操作，我们再看一份代码：

class Solution:
    def getSum(self, a: int, b: int) -> int:
    	# 将两数转化为 32 位内二进制可以表示的整数
        a &= 0xFFFFFFFF
        b &= 0xFFFFFFFF
        # 只要 b 进位不为 0 
        while b:
        	# 对两数按位与获取进位
            carry = a & b
            # 对两数按位异或获取不进位相加
            a ^= b
            # 进位左移
            b = ((carry) << 1) & 0xFFFFFFFF
		# 正数正常返回，负数单独处理
        return a if a < 0x80000000 else ~(a^0xFFFFFFFF)

#作者：lih
#链接：https://leetcode-cn.com/problems/sum-of-two-integers/solution/python-wei-yun-suan-yi-xie-keng-by-lih/

保留 32 位内有效值，直接通过 a & 0xFFFFFFFF, 也就是和 32 位的 1 来进行按位与运算，这就清晰明了太多，最后超出范围后，先进行异或运算再取反，也是相似的思路但更直接些。

我们接着看下其它题目：

题目一

「第 136 题：只出现一次的数字」

难度：简单

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

「说明：」

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:
输入: [2,2,1]
输出: 1

示例 2:
输入: [4,1,2,1,2]
输出: 4

题目分析

常规操作可以建个字典统计每个元素出现次数，最后再遍历下字典中次数为 1 的值返回；

或者建个列表，当元素第一次出现时，加入到列表中，当再次遇到该元素时，从列表中删除，那么最终列表中剩下的就是结果。

再或者，我们对此列表求和，然后将其转化为集合，对集合求和再乘二，这两个数的差值即结果。

但这些思路都不满足题目中提到的「不使用额外空间」，我们来看看位运算的骚操作吧！

「位运算技巧：数字 a 与它本身按位异或结果为 0，与 0 按位异或结果为它本身，即 a ^ a = 0, a ^ 0 = a」

放到这题目里，出现两次的数字按位异或运算后为 0，那么只要把所有数接连按位异或运算一遍，结果就是只出现一次的元素了！

代码实现

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        # 遍历列表
        for i in nums:
        	# 这里是 result = result ^ i 的简写
            result ^= i
        return result

提交测试表现：

执行用时 : 40 ms, 在所有 Python3 提交中击败了 92.68% 的用户
内存消耗 : 15.3 MB, 在所有 Python3 提交中击败了 5.26% 的用户

就是这么骚气！

题目二

「第 137 题：只出现一次的数字 II」

难度：中等

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

「说明：」

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:
输入: [2,2,3,2]
输出: 3

示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99

题目分析

这是专门针对位运算么？三次，刚我们设计的按位异或又变回该数本身了，无法甄别第一次还是第三次。

但是，我们结合着其它位运算来实现：当出现第一次时，记录结果，但出现第二次之后就不再记录该结果。

假设 seen_once = 0、seen_twice = 0，结合按位异或、按位取反和按位与，可以设计如下：

位运算图解

图片及算法来源：
https://leetcode-cn.com/problems/single-number-ii/solution/zhi-chu-xian-yi-ci-de-shu-zi-ii-by-leetcode/

我们先看第一步，seen_twice 为 0，～seen_twice 即一串 1，再进行 & 的话其实相当于不改变右半部分，即 seen_once = seen_once ^ x

seen_twice = ~seen_once & (seen_twice ^ x), 这里 & 左右两边是反的，所以仍然为 0

到了第二步，seen_once 因为第二次出现变为 0，但 seen_twice 因为 seen_once 的变 0 就可以记录该值了

再到第三步，seen_twice 此时不为 0，会导致 seen_once 仍旧结果为 0；同时 seen_twice 也因为该值的再次出现被按位异或出结果 0

所以如果对所有数全部执行一遍上述操作，那么结果就是只出现一次的数字。

代码实现

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        seen_once = 0
        seen_twice = 0
		# 遍历列表，执行上述操作
        for i in nums:
            seen_once = ~ seen_twice & (seen_once ^ i)
            seen_twice = ~ seen_once & (seen_twice ^ i)
        # 最终结果存在 seen_once 中
        return seen_once

提交测试表现：

执行用时 : 48 ms, 在所有 Python3 提交中击败了 63.90% 的用户
内存消耗 : 14.6 MB, 在所有 Python3 提交中击败了 25.00% 的用户

这种骚操作，除非遇到原题，不然挺难考虑的。

题目三

「第 231 题：2 的幂」

难度：简单

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

示例 1:

输入: 1
输出: true
解释: 20 = 1

示例 2:
输入: 16
输出: true
解释: 24 = 16

示例 3:
输入: 218
输出: false

#来源：力扣（LeetCode）
#链接：https://leetcode-cn.com/problems/power-of-two

题目分析

常规思路可以建立个 while 循环一直除以 2 取余数，若直到最后一直为 0 则返回 True。涉及到位运算的话，2 的幂次方，即 2 进制位中只会出现 1 个 1，那么可以通过位运算将这个 1 变成 0 从而检测剩余的数值是否为 0。

「位运算技巧：数字 a & (a-1) 可以去除 a 二进制位中最右侧的 1」

去除最右侧1图解

图片和算法来源：
https://leetcode-cn.com/problems/power-of-two/solution/2de-mi-by-leetcode/

当然还有其它位运算可以提取这个最右侧的 1，比如 a & (-a) ，这个上面链接里也都有提到。

回归到题目，只要判断 a & (a-1) 结果为 0，则该数是 2 的幂次方、返回 True

代码实现

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n<=0:
            return False
        return n&(n-1)==0

提交测试表现：

执行用时 : 44 ms, 在所有 Python3 提交中击败了 56.49% 的用户
内存消耗 : 13.7 MB, 在所有 Python3 提交中击败了 6.25% 的用户

结论

对于位运算的练习，这两天接触了四道题目，基本都是参考着题解算法来做的。这类题目，属于知道了可能会用，不知道完全没这概念的类型，所以，我们主要通过练习加深对位运算的理解，有这么个位运算概念，能记住最好，记不住也不用强求。

整理一下遇到的位运算技巧：

1. 加法通过 a ^ b 进行不进位加法、 a & b << 1 获取进位结果来实现
2. 按位异或运算特点：a ^ a = 0, a ^ 0 = a
3. 去除最右侧的 1: a ^ (a-1) ; 应用是通过判断该结果是否为 0 检测是否为 2 的幂次方

此外，还有些常用技巧：

1. 判断奇偶性：a & 1, 若结果为 1 则 a 为奇数；若为 0 则 a 为偶数
2. 这个比较奇怪，但记着吧：a + (~ a) = -1
3. 判断两数是否同号：a ^ b >= 0，若 a、b 同号，则其首位符号位相同，a ^ b 结果首位为 0、整体 >= 0; 若异号，则首位为 1，则结果是小于 0 的

今早有周赛的，睡过了没能参加，趁机休整下，明天准备看一下二叉树的题目，明儿见！