Python 刷题笔记：位运算专题一
Python 刷题笔记：位运算专题一
学 Python 初接触 &、| 等运算符时，只大概了解它们被称为位运算符，并不同于逻辑运算符 and、or，今天就通过基础知识点和几道题目来熟悉下。
知识点
我们都知道所有数值在计算机底层是以二进制形式存在的，首先要明确几个概念：
- 原码：直接将一个数值转化为二进制，其首位代表符号，0 为正 1 为负
- 反码：最高位符号位不变，其余为取反，即 1 变 0、0 变 1
- 补码：正数的补码与原码相同；负数的补码为其反码 +1
以正数 4 和负数 -5 为例，其 32 位二进制形式如下：
关键点来了，我们接下来要接触的「位运算符，都是对数字的补码进行运算的」！这就是我们自己测试时，正数间的位运算看着都挺正常，但一涉及到负数就老不按预想走。
接下来我们看常用的运算符：
我们运行下示例：
示例位运算结果
结合着之前 4 和 -5 的补码，就很容易理解 ～ 4 值为何是 -5 了。
当然，这只是最基础的位运算，当具体到特定情景时，位运算有很多妙用，我们就在题目中去体会学习吧！
题目
第 371 题：两整数之和
难度：简单
不使用运算符 + 和 - ，计算两整数 a 、b 之和。
示例 1：
输入: a = 1, b = 2
输出: 3
示例 2:
输入: a = -2, b = 3
输出: 1位运算技巧
这里的解释说明我直接选用精选题解，还是容易理解的：
题解来源：https://leetcode-cn.com/problems/sum-of-two-integers/solution/wei-yun-suan-xiang-jie-yi-ji-zai-python-zhong-xu-y/位运算中两数加法情况如下：
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0（进位 1）恰好与「按位异或」基本一致，但却缺少进位，例如 5 + 4:
a = 5 = 0101
b = 4 = 0100
a ^ b 如下：
0 1 0 1
0 1 0 0
-------
0 0 0 1a ^ b 得到了一个无进位加法结果，如果要得到 a + b 的最终值，我们还要找到进位的数，把这二者相加。在位运算中，我们可以使用与操作获得进位：
a = 5 = 0101
b = 4 = 0100
a & b 如下：
0 1 0 1
0 1 0 0
-------
0 1 0 0由计算结果可见，0100 并不是我们想要的进位，1 + 1 所获得的进位应该要放置在它的更高位，即左侧位上，因此我们还要把 0100 左移一位，才是我们所要的进位结果：a & b << 1
此时，将上述两结果“相加”即可得到最终结果，但是，我们没有加号，所以要对上述两结果重复类似运算，直到最后无需进位：
- a + b 的问题拆分为 (a 和 b 的无进位结果) + (a 和 b 的进位结果)
- 无进位加法使用异或运算计算得出
- 进位结果使用与运算和移位运算计算得出
- 循环此过程，直到进位为 0
此外要注意的是，Python 中整数并不是 32 位的，即 << 左移并不会导致溢出，所以需要我们要对 Python 中的整数处理来达到 32 位整型效果，具体做法是将整数对 0x100000000 (0x 代表此数是 16 进制) 取模，即超出 32 位的部分不要、设为 0。
所以上述位运算模拟的加法在 Python 中除了上述循环位运算，还要通过整数取模保证结果一直在 32 位内。
代码实现
class Solution(object):
def getSum(self, a, b):
"""
:type a: int
:type b: int
:rtype: int
"""
# 2^32
MASK = 0x100000000
# 整型最大值
MAX_INT = 0x7FFFFFFF
MIN_INT = MAX_INT + 1
# 进位结果若不为 0 ，一直循环执行位运算
while b != 0:
# 计算进位
carry = (a & b) << 1
# 取余范围限制在 [0, 2^32-1] 范围内
a = (a ^ b) % MASK
b = carry % MASK
return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT)
#作者：jalan
#链接：https://leetcode-cn.com/problems/sum-of-two-integers/solution/wei-yun-suan-xiang-jie-yi-ji-zai-python-zhong-xu-y/结尾处的 return 语句也对其超出范围时做了特殊处理，我也找来了评论区相关的注解：
❝~((a % MIN_INT) ^ MAX_INT) 这里为什么要对负数做这样的处理呢？ 因为在 Python 中 int 不是 32 位的，所以一个负数比如 -2, 其 64 位表示就是 0x00000000FFFFFFFE, 用 Python 求取这个 16 进制的值 int('0x00000000FFFFFFFE', 16), 得到的数字是 4294967294 不是我们想要的 -2，所以：(a % MIN_INT) ^ MAX_INT 是先对 a 的 32 位以外部分取反，对应 -2，就得到0x0000000000000002 再用 ～ 操作符对所以位置取反，对应 -2，得到 0xFFFFFFFFFFFFFFFE。 ❞
这里总感觉描述的不准确，后续我还要再验证下，但大致就是如果不对负数特殊处理，那么负数前面还可能存在 0，最后输出的是大于32位的正数。
结论
其实挺简单的一个运算过程，但由于 Python 中 int 没有 32 位限制，导致对数字的处理显得挺麻烦了。原本想多记录几个用法的，没成想这个最简单的加法都整理这么一堆。不过也好，一次性理清其概念，明天直接题目走起～
今天心态又爆炸，各种不顺、不爽，被血虐。。