第87课 - 位运算技巧

学习目标

• 掌握使用 lowbit 技巧快速提取二进制数中最低位的 1。
• 学会高效统计一个整数的二进制表示中 1 的个数 (popcount)。
• 理解并应用位运算来判断一个数是否为 2 的幂。
• 熟练使用位掩码 (mask) 来进行集合或权限的操作。

核心概念

在上一课的位运算基础之上，本课将介绍一些在算法竞赛和工程开发中非常实用的位运算技巧。这些技巧能让你用更少的代码、更高的效率解决特定问题。

1. lowbit 操作： lowbit(x) 的作用是取出 x 在二进制表示下，最低位的 1 以及它后面的 0 所构成的数值。它有一个非常优雅的数学表示：lowbit(x) = x & (-x)。 原理：在补码表示中，-x 等于 ~x + 1。x & (-x) 的效果是，-x 在 x 的最低位 1 处（以及该位右侧）与 x 完全相同，而在该位左侧，-x 与 x 的每一位都相反。按位与 (&) 操作后，只有最低位的 1 被保留。

   # 例如：x = 12 (二进制：1100)
   # -x = -12 (补码，在64位系统中表示为...11110100，这里简化考虑)
   # x & (-x) = 1100 & ...0100 = 0100 (即 4)
   

   复制+ 追加到编辑器

2. popcount 操作： popcount(x) 用于统计一个整数 x 的二进制表示中 1 的个数。许多现代 CPU 提供了直接的硬件指令来执行此操作（在Python中，可以使用 bin(x).count("1")，但了解位运算实现更有意义）。 Brian Kernighan 算法：每次执行 x = x & (x - 1) 都会将 x 的二进制表示中最右边的一个 1 变为 0。因此，循环执行该操作直到 x 为 0，执行的次数就是 1 的个数。

3. 判断 2 的幂： 一个数 n 是 2 的幂，当且仅当 n > 0 且其二进制表示中只有一个 1。根据这个性质，n & (n - 1) 的作用是消除 n 最右边的 1。如果 n 是 2 的幂，那么 n & (n - 1) 的结果必然为 0。

   # 例如：n = 8 (1000), n-1=7 (0111), 8 & 7 = 0
   # n = 12 (1100), n-1=11 (1011), 12 & 11 = 1000 (8) != 0
   

   复制+ 追加到编辑器

4. 位掩码 (mask)： 掩码是一串二进制数字，用于通过位运算（主要是 &、|、^、~）来提取、设置或清除其他二进制数中的特定位。

   • 设置位：flags = flags | MASK (使用 | 或运算将指定位设为 1)
   • 清除位：flags = flags & ~MASK (使用 & 和 ~ 将指定位设为 0)
   • 翻转位：flags = flags ^ MASK (使用 ^ 异或将指定位取反)
   • 检查位：if (flags & MASK) != 0 (检查指定位是否为 1)

代码示例

def lowbit(x):
    """返回x二进制表示中最低位的1所代表的值"""
    return x & (-x)

def popcount_kernighan(x):
    """使用Brian Kernighan算法统计二进制中1的个数"""
    count = 0
    while x:
        x &= (x - 1)  # 消除最右边的一个1
        count += 1
    return count

def is_power_of_two(n):
    """判断一个数是否是2的幂 (n>0)"""
    return n > 0 and (n & (n - 1)) == 0

# 位掩码示例：模拟文件权限系统 (读, 写, 执行)
PERM_READ = 1 << 0   # 001
PERM_WRITE = 1 << 1  # 010
PERM_EXEC = 1 << 2   # 100

def set_permission(permissions, perm_to_set):
    """设置权限"""
    return permissions | perm_to_set

def clear_permission(permissions, perm_to_clear):
    """清除权限"""
    return permissions & (~perm_to_clear)

def check_permission(permissions, perm_to_check):
    """检查权限"""
    return (permissions & perm_to_check) == perm_to_check

# 测试代码
if __name__ == "__main__":
    # 测试 lowbit
    num = 0b101100  # 44
    print(f"Number: {num}, Binary: {bin(num)}")
    print(f"Lowest Set Bit (lowbit): {lowbit(num)}, Binary: {bin(lowbit(num))}\n")

    # 测试 popcount
    num = 0b10110111  # 183
    print(f"Number: {num}, Binary: {bin(num)}")
    print(f"Number of 1s (popcount): {popcount_kernighan(num)}\n")

    # 测试 is_power_of_two
    test_nums = [0, 1, 2, 3, 4, 16, 18]
    for n in test_nums:
        print(f"{n} is power of two? {is_power_of_two(n)}")
    print()

    # 测试位掩码
    my_perms = 0  # 初始无权限
    print(f"Initial permissions: {my_perms:03b}")
    my_perms = set_permission(my_perms, PERM_READ)
    print(f"After adding READ: {my_perms:03b}")
    my_perms = set_permission(my_perms, PERM_WRITE)
    print(f"After adding WRITE: {my_perms:03b}")
    my_perms = set_permission(my_perms, PERM_EXEC)
    print(f"After adding EXEC: {my_perms:03b}")
    print(f"Has EXEC permission? {check_permission(my_perms, PERM_EXEC)}")
    my_perms = clear_permission(my_perms, PERM_WRITE)
    print(f"After clearing WRITE: {my_perms:03b}")
    print(f"Has WRITE permission? {check_permission(my_perms, PERM_WRITE)}")

实践练习

1. （易）使用 lowbit 统计正数 x 的二进制中 1 的个数。

   • 要求：不使用 popcount 函数或 bin().count()，仅利用 lowbit 的思想循环实现。
   • 提示：每次用 lowbit 得到当前最低位的 1，然后从 x 中减去这个值（或使用异或清除该位），计数加一，直到 x 变为 0。
   • 预期输出：输入 13 (二进制 1101)，输出 3。

2. （中）给定一个非空整数数组，其中某个元素只出现一次，其余每个元素均出现两次。找出那个只出现了一次的元素。

   • 要求：使用位运算实现，时间复杂度 O(n)，空间复杂度 O(1)。
   • 提示：考虑异或 (^) 的性质：a ^ a = 0, a ^ 0 = a。将所有数字进行异或，最终结果即为只出现一次的数字。
   • 示例：输入 [2, 2, 1]，输出 1；输入 [4, 1, 2, 1, 2]，输出 4。

3. （难）给定一个整数 n，计算从 0 到 n 之间每个数的二进制中 1 的个数（包含 0 和 n）。

   • 要求：尝试使用动态规划或利用 n & (n-1) 的性质，找到比循环调用 popcount 更优的解法。
   • 提示：count[i] = count[i & (i - 1)] + 1。即 i 中 1 的个数等于将它最低位 1 变为 0 后那个数的 1 的个数加 1。
   • 示例：输入 2，输出 [0, 1, 1]；输入 5，输出 [0, 1, 1, 2, 1, 2]。

常见错误

1. & 的优先级：在表达式如 x & MASK == 0 中，== 的优先级高于 &。这会被解释为 x & (MASK == 0)，导致逻辑错误。务必使用括号：(x & MASK) == 0。
2. 处理负数时的陷阱：在 Python 中，整数是任意精度的，位运算对负数的处理（尤其是移位）与某些语言不同。上述 lowbit 和 is_power_of_two 的经典公式主要针对补码表示的无符号或正数。对于负数，需要特别注意其补码表示。
3. 误解 popcount：popcount 统计的是二进制中 1 的个数，而不是十进制中数字的个数。例如 popcount(10) 统计的是二进制 1010 中 1 的个数 2，而不是数字 1 和 0。
4. is_power_of_two 对 0 的处理：(n & (n-1)) == 0 对于 0 也成立（0 & (-1) 在 Python 中为 0），但 0 通常不被认为是 2 的幂次方。因此，条件必须加上 n > 0。

小结

本课学习了四个关键的位运算技巧：

• lowbit：通过 x & (-x) 快速定位最低位的 1，是树状数组等数据结构的基石。
• popcount：统计 1 的个数，Brian Kernighan 算法 (x &= x-1) 是其核心思想。
• 判断 2 的幂：利用 n > 0 && (n & (n-1)) == 0，简洁高效。
• 位掩码：通过预先定义的常量（1 << k）与位运算（|, &, ^, ~），实现对特定位的灵活操作，是处理集合、权限和标志位的经典方法。

掌握这些技巧，能显著提升你编写位运算相关代码的能力和效率。下一课，我们将学习如何使用位运算来高效地枚举一个集合的所有子集。