在 Python 中，位运算直接作用于整数的补码二进制表示

基础位运算符

运算符	名称	逻辑描述	示例 (a=5,b=3)	二进制计算过程
&	按位与 (AND)	两位全为 1，结果才为 1	5 & 3 → 1	101 & 011 = 001
|	按位或 (OR)	两位有一个为 1，结果就为 1	5 | 3 → 7	101 | 011 = 111
^	按位异或 (XOR)	两位不同为 1，相同为 0	5 ^ 3 → 6	101 ^ 011 = 110
~	按位取反 (NOT)	1 变 0，0 变 1 (含符号位)	~5 → -6	~x 等同于 -(x+1)
<<	左移 (L-Shift)	各位左移，高位丢弃，低位补 0	5 << 1 → 10	101 变 1010 (相当于 $\times 2$)
>>	右移 (R-Shift)	各位右移，低位丢弃，高位补符号	5 >> 1 → 2	101 变 010 (相当于 $\div 2$ 取整)

 常用位运算技巧 

掌握这些公式能极大地提高解题速度：

• 消除最低位的 1：n & (n - 1)

  • 用途：计算一个数二进制中有多少个 1（Hamming Weight）。

• 获取最低位的 1：n & -n

  • 用途：树状数组，或在“只出现一次的数字 III”中进行分组。

• 判断奇偶：n & 1

  • 结果为 1 是奇数，为 0 是偶数。

• 交换两数 (不使用临时变量)：

  Python

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

• 乘/除 2 的 k 次幂：

  • n << k 等价于

  • n >> k 等价于

注意点

Python的整数是无限精度的，这与 C++/Java 的固定 32 位有显著不同：

1. 取反 ~ 的结果：

   在 Python 中，~x 永远等于 -(x + 1)。例如 ~0 会得到 -1，而不是一个巨大的正整数。

2. 处理 32 位溢出：

   如果题目要求模拟 32 位环境（如计算补码下的负数），通常需要手动使用掩码：

   Python

   # 将结果限制在 32 位范围内
   res = res & 0xFFFFFFFF
   
   # 如果结果大于 0x7FFFFFFF，说明在 32 位下它是个负数
   if res > 0x7FFFFFFF:
       res = ~(res ^ 0xFFFFFFFF)
   

异或 (XOR) 的性质

在算法题中，异或出现的频率最高，因为它有以下特性：

• 归零律：a ^ a = 0

• 恒等律：a ^ 0 = a

• 交换律/结合律：a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

  • 这就是为什么“只出现一次的数字 I”（其余出现两次）可以用一行代码搞定的原因。

例题

只出现一次的数字I

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res^=num
        return res

只出现一次的数字II

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for i in range(32):
            total=0
            for num in nums:
                total+=(num>>i)&1

            if total%3:
                if i==31:
                    res-=(1<<i)
                else:
                    res|=(1<<i)
        return res

如果我们将数组中所有数字的二进制表示垂直排开，对于任何一位 i，所有出现 3 次的数字，它们在这一位上贡献的 1 的个数要么是 0 个，要么是 3 个，因此，这一位 1 的总数 total 如果除以 3 余 1，那多出来的这一个 1 必然来自于那个只出现一次的数字

i = 31 时为什么要减去 (1 << i)？

这是 Python 处理负数的一个特殊机制，涉及计算机底层的补码。在 32 位有符号整数中：

• 第 0 到 30 位表示数值。

• 第 31 位是符号位。

关键点： 在补码表示法中，最高位（符号位）的权重是负的。

对于一个 32 位整数，它的值等于：

• 在 C++ 或 Java 中：整数固定是 32 位，把第 31 位设为 1 时，系统会自动把它识别为负数。

• 在 Python 中：整数是无限精度的。如果单纯地把第 31 位设为 1（res |= (1 << 31)），Python 会认为这是一个巨大的正整数。

为了让 Python 模拟出 32 位有符号整数的效果，当发现第 31 位应该是 1 时，我们不能用或运算增加数值，而要用减法减去 ，从而把这个数强行拉进负数区间。

所以说，对于一个数，既能整体加减，又能拿出单个位进行处理

多多最长字串

（题目描述来源于 塔子哥学算法，侵删）

import sys

def solve():
    # 读取输入
    try:
        line1 = sys.stdin.readline().split()
        if not line1: return
        m, n = map(int, line1)
        a = sys.stdin.readline().strip()
        b = sys.stdin.readline().strip()
    except EOFError:
        return

    # 1. 计算 B 的总异或和
    target_xor = 0
    for char in b:
        target_xor ^= int(char)

    # 2. 预处理 A 的前缀异或和
    prefix_xor = [0] * (m + 1)
    for i in range(m):
        prefix_xor[i+1] = prefix_xor[i] ^ int(a[i])

    # 3. 统计满足条件的唯一子串
    valid_substrings = set()
    
    for i in range(m - n + 1):
        # 计算子串 A[i...i+n-1] 的异或和
        current_xor = prefix_xor[i+n] ^ prefix_xor[i]
        
        if current_xor == target_xor:
            # 只有满足条件才进行切片并加入 set，减少内存和计算开销
            valid_substrings.add(a[i : i+n])

    print(len(valid_substrings))

if __name__ == "__main__":
    solve()