1. 什么是位运算
位运算，就是直接对数字的 二进制每一位 进行运算。
比如十进制的 13，写成二进制是：
1101
意思是：
- 第 1 位是 1
- 第 2 位是 0
- 第 3 位是 1
- 第 4 位是 1
位运算就是对这些 0 和 1 动手。
2. 为什么要先懂二进制
因为计算机底层存数字，本来就是用二进制。
十进制我们平时这样看：
347 = 3*100 + 4*10 + 7
二进制也一样，只不过基数变成 2：
1101 = 1*8 + 1*4 + 0*2 + 1*1 = 13
所以：
13 的二进制是 1101
再举几个：
1 -> 0001
2 -> 0010
3 -> 0011
4 -> 0100
5 -> 0101
6 -> 0110
7 -> 0111
8 -> 1000
3. 常见位运算符有哪些
最常见的就这几个：
&按位与|按位或^按位异或~按位取反<<左移>>右移
你现在最先要掌握的是前 5 个里的：
&|^<<>>
~ 稍微绕一点，最后再讲。
4. 按位与 &
规则：
1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0
你可以把它理解成：
只有两个位置都为 1，结果才是 1
例子：6 & 3
先写成二进制：
6 = 110
3 = 011
按位对应计算：
110
& 011
-----010
结果 010 就是十进制的 2。
所以：
6 & 3 = 2
& 常见用途
用途 1：判断奇偶
看最后一位是不是 1。
- 奇数最后一位一定是 1
- 偶数最后一位一定是 0
所以：
x & 1
如果结果是 1，说明是奇数。
如果结果是 0，说明是偶数。
例如：
7 = 111
7 & 1 = 1 # 奇数8 = 1000
8 & 1 = 0 # 偶数
用途 2：取模 2^k
这个就是你刚才那段代码里的用法。
x & ((1 << k) - 1)
等价于：
x % (2 ** k)
比如：
29 % 8 = 5
因为 8 = 2^3，所以也可以写成：
29 & (8 - 1)
29 & 7
验证一下：
29 = 111017 = 00111
-------------00101 = 5
所以：
29 & 7 = 5
5. 按位或 |
规则：
1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0
你可以理解成：
只要有一个是 1，结果就是 1
例子：6 | 3
6 = 110
3 = 011
按位或：
110
| 011
-----111
结果 111 是十进制 7。
所以：
6 | 3 = 7
| 常见用途
用途：把某一位强制设成 1
比如你想把一个数的第 2 位变成 1，就可以用 |。
例如：
x = 8 # 1000
x | 2 # 0010
计算：
1000
| 0010
------1010 = 10
所以结果是 10。
6. 按位异或 ^
规则：
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
你可以理解成：
两位不同，结果才是 1
例子：6 ^ 3
6 = 110
3 = 011
按位异或：
110
^ 011
-----101
结果 101 是十进制 5。
所以：
6 ^ 3 = 5
^ 最重要的性质
性质 1：同一个数和自己异或等于 0
a ^ a = 0
例如：
5 ^ 5 = 0
性质 2：一个数和 0 异或还是自己
a ^ 0 = a
性质 3：异或满足交换律、结合律
a ^ b ^ a = b
因为：
a ^ a = 0
0 ^ b = b
^ 常见用途
用途 1：找只出现一次的数
比如数组里其他数都出现两次，只有一个数出现一次：
[2, 3, 2, 4, 4]
全部异或起来：
2 ^ 3 ^ 2 ^ 4 ^ 4
= (2 ^ 2) ^ (4 ^ 4) ^ 3
= 0 ^ 0 ^ 3
= 3
最后答案就是 3。
这是面试和算法题里特别常见的用法。
用途 2：交换两个数
理论上可以这样写：
a = a ^ b
b = a ^ b
a = a ^ b
但实际开发里不推荐这样写，可读性差。
知道有这个技巧就行。
7. 左移 <<
规则：
x << 1
表示把二进制整体向左移 1 位，右边补 0。
例子
3 = 0011
3 << 1 = 0110 = 6
3 << 2 = 1100 = 12
所以：
x << 1 相当于 x * 2
x << 2 相当于 x * 4
x << k 相当于 x * (2^k)
为什么
因为二进制左移一位，相当于每一位的权重都乘 2。
就像十进制里：
23变成230，相当于乘 10
二进制里：
101变成1010，相当于乘 2
你代码里的 1 << 64
这就是：
2^64
因为：
1 << 1 = 2
1 << 2 = 4
1 << 3 = 8
...
1 << 64 = 2^64
所以：
(1 << 64) - 1
就是：
2^64 - 1
8. 右移 >>
规则：
x >> 1
表示把二进制整体向右移 1 位。
例子
12 = 1100
12 >> 1 = 0110 = 6
12 >> 2 = 0011 = 3
所以一般可以理解成：
x >> 1 相当于 x // 2
x >> 2 相当于 x // 4
x >> k 相当于 x // (2^k)
对于非负整数这个理解很好用。
9. 按位取反 ~
这个最容易绕，你先知道个大概就够。
它表示把每一位：
1变00变1
比如理论上：
~1010 = 0101
但 Python 里的负数表示会让结果看起来怪，所以会出现：
~5 = -6
这个你现在先不用深究。
刚入门时，先别主动用 ~，免得把自己绕晕。
10. 你最常见会见到的位运算写法
1）判断奇偶
if x & 1:print("奇数")
else:print("偶数")
2）计算 2^k
1 << k
例如：
1 << 3 = 8
1 << 5 = 32
3）乘以 2^k
x << k
4）除以 2^k
x >> k
5）对 2^k 取模
x & ((1 << k) - 1)
6）找只出现一次的数
ans = 0
for x in arr:ans ^= x
print(ans)
11. 回到你之前那句代码
你那句是：
print(total_sum & ((1 << 64) - 1))
我们拆开：
第一步
1 << 64
表示：
2^64
第二步
(1 << 64) - 1
表示：
2^64 - 1
第三步
total_sum & ((1 << 64) - 1)
表示：
只保留
total_sum的低 64 位
这和：
total_sum % (2 ** 64)
效果一样。
所以你完全可以先把它理解成：
print(total_sum % (2 ** 64))
12. 一个超实用的小表
你先把这个表记住最有用：
x & 1 判断奇偶
x << 1 乘 2
x << k 乘 2^k
x >> 1 除 2
x >> k 除 2^k
1 << k 表示 2^k
x ^ x 等于 0
x ^ 0 等于 x
x & ((1<<k)-1) 等于 x % (2^k)
13. 你现在最应该练的 5 个小例子
你可以自己先算一遍，再看结果。
例 1
5 & 1
5 = 101，最后一位是 1，所以结果是 1。
例 2
8 & 1
8 = 1000，最后一位是 0，所以结果是 0。
例 3
3 << 2
3 * 4 = 12，所以结果是 12。
例 4
12 >> 2
12 // 4 = 3，所以结果是 3。
例 5
6 ^ 6
同一个数异或自己等于 0，所以结果是 0。
14. 学位运算的建议
刚开始不要追求“完全懂底层”。
先按这个顺序学最稳：
- 先会二进制和十进制的简单转换
- 掌握
&、^、<<、>> - 记住几个高频结论
- 在题里慢慢见多了，就自然熟了
你现在完全不用一口气把所有位运算吃透。
先会最常用的几个，就已经够做很多题了。