算法技法：位运算

a & b   # 与：两位都为 1 才为 1
a | b   # 或：有一位为 1 就为 1
a ^ b   # 异或：两位不同为 1
~a      # 非：取反
a << n  # 左移：相当于 × 2^n
a >> n  # 右移：相当于 ÷ 2^n

# 判断奇偶
n & 1  # 1 是奇数，0 是偶数

# 交换两个数
a ^= b
b ^= a
a ^= b

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

# 获取最低位的 1
n & (-n)

# 判断是否是 2 的幂
n > 0 and (n & (n - 1)) == 0

# 取第 k 位
(n >> k) & 1

# 设置第 k 位为 1
n | (1 << k)

# 设置第 k 位为 0
n & ~(1 << k)

# 切换第 k 位
n ^ (1 << k)

def singleNumber(nums: list[int]) -> int:
    result = 0
    for num in nums:
        result ^= num
    return result

def hammingWeight(n: int) -> int:
    count = 0
    while n:
        n &= (n - 1)  # 消除最低位的 1
        count += 1
    return count

def hammingWeight(n: int) -> int:
    count = 0
    for _ in range(32):
        count += n & 1
        n >>= 1
    return count

def countBits(n: int) -> list[int]:
    dp = [0] * (n + 1)

    for i in range(1, n + 1):
        # i 比 i >> 1 多了最低位
        # 如果 i 是奇数，最低位是 1，否则是 0
        dp[i] = dp[i >> 1] + (i & 1)

    return dp

def countBits(n: int) -> list[int]:
    dp = [0] * (n + 1)

    for i in range(1, n + 1):
        # i 比 i & (i-1) 多一个 1
        dp[i] = dp[i & (i - 1)] + 1

    return dp

def hammingDistance(x: int, y: int) -> int:
    xor = x ^ y
    count = 0
    while xor:
        xor &= (xor - 1)
        count += 1
    return count

def missingNumber(nums: list[int]) -> int:
    result = 0
    n = len(nums)

    # 异或所有索引和数值
    for i, num in enumerate(nums):
        result ^= i ^ num

    # 最后异或 n
    return result ^ n

def isPowerOfTwo(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

def reverseBits(n: int) -> int:
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

def findMaximumXOR(nums: list[int]) -> int:
    result = 0
    mask = 0

    for i in range(30, -1, -1):
        mask |= (1 << i)

        # 当前所有数的前缀
        prefixes = set(num & mask for num in nums)

        # 尝试把结果的这一位置 1
        candidate = result | (1 << i)

        # 检查是否存在两个前缀异或等于 candidate
        for p in prefixes:
            if p ^ candidate in prefixes:
                result = candidate
                break

    return result

# 状态压缩 BFS
# state 的第 k 位表示是否有第 k 把钥匙

# Python 中负数右移是算术右移（符号位扩展）
-1 >> 1  # 还是 -1

# 解决：用位与限制位数
(-1 >> 1) & 0xFFFFFFFF

# 错误
if n & 1 == 1:  # == 优先级高于 &

# 正确
if (n & 1) == 1:

# 错误
n & n - 1  # 相当于 n & (n-1)，但容易误解

# 正确
n & (n - 1)

# Python 整数无溢出，但其他语言要注意
# 左移可能溢出