发布于 由admin

Python Bit Manipulation：位运算在特定场景下的高效应用

Python Bit Manipulation：位运算在特定场景下的高效应用 (讲座模式)

各位观众老爷们，大家好！我是今天的主讲人，江湖人称“代码界的段子手”。今天咱们来聊聊一个听起来高大上，但其实非常实在的家伙：位运算。

啥是位运算？简单来说，就是直接在二进制位上进行操作。别害怕，听起来像黑客帝国，但其实它比你想的有用得多。而且，学会了位运算，你就能在某些特定场景下写出效率爆炸的代码，让你的程序跑得飞起！

一、 位运算：你真的了解它们吗？

我们先来认识一下位运算家族的成员，它们分别是：

运算符 名称 作用 示例
& 按位与 对应位都为 1 时，结果为 1，否则为 0 5 & 3
| 按位或 对应位只要有一个为 1，结果就为 1 5 | 3
^ 按位异或 对应位不同时，结果为 1，相同时为 0 5 ^ 3
~ 按位取反 将每一位取反，0 变为 1，1 变为 0 ~5
<< 左移 将二进制位向左移动指定的位数，右边用 0 填充 5 << 2
>> 右移 将二进制位向右移动指定的位数，左边用符号位填充（对于有符号整数）或 0 填充（对于无符号整数） 5 >> 1

别光看表格就觉得枯燥，咱们来点实际的。

  • 按位与 (&)

    想象一下，你手里有两把锁，只有两把锁都打开了，你才能进入宝藏库。& 运算就是这个意思。

    a = 5  # 二进制：0101
b = 3  # 二进制：0011
result = a & b  # 二进制：0001  十进制：1
print(result)  # 输出 1

    只有在 a 和 b 的对应位都为 1 的时候，结果的对应位才为 1。

  • 按位或 (|)

    这次，你手里还是两把锁，但是只要有一把锁打开了，你就能进入宝藏库。| 运算就是这样。

    a = 5  # 二进制：0101
b = 3  # 二进制：0011
result = a | b  # 二进制：0111  十进制：7
print(result)  # 输出 7

    只要 a 和 b 的对应位中有一个为 1，结果的对应位就为 1。

  • 按位异或 (^)

    现在，你手里还是两把锁，但是只有当两把锁的状态不同时（一把开，一把关），你才能进入宝藏库。^ 运算就是这个逻辑。

    a = 5  # 二进制：0101
b = 3  # 二进制：0011
result = a ^ b  # 二进制：0110  十进制：6
print(result)  # 输出 6

    当 a 和 b 的对应位不同时，结果的对应位才为 1。

  • 按位取反 (~)

    这个操作比较简单粗暴，直接把所有的 0 变成 1，1 变成 0。要注意的是，Python 中的 ~ 运算会考虑符号位，所以结果可能会让你有点困惑。

    a = 5  # 二进制：00000101 (假设是8位整数)
result = ~a  # 二进制：11111010  十进制：-6 (根据补码表示)
print(result)  # 输出 -6

    在 Python 中，整数通常使用补码表示。对一个数取反，实际上是对它的补码取反。

  • 左移 (<<)

    想象一下，你把一个队伍整体向左移动，空出来的位置用 0 填充。<< 运算就是这样，相当于乘以 2 的幂。

    a = 5  # 二进制：0101
result = a << 2  # 二进制：010100  十进制：20
print(result)  # 输出 20

    a << 2 相当于 a * (2 ** 2)，也就是 a * 4。

  • 右移 (>>)

    这次，你把队伍向右移动，空出来的位置用符号位或 0 填充（取决于具体的编程语言和数据类型）。>> 运算相当于除以 2 的幂。

    a = 5  # 二进制：0101
result = a >> 1  # 二进制：0010  十进制：2
print(result)  # 输出 2

b = -5 # 二进制 (补码): 11111011
result_b = b >> 1 #  二进制 (补码): 11111101 (算术右移，高位补1) 十进制：-3
print(result_b) #输出 -3

    a >> 1 相当于 a // (2 ** 1)，也就是 a // 2（整数除法）。注意，右移操作对于负数的处理方式可能因语言而异。Python 使用算术右移，即高位用符号位填充。

二、 位运算的骚操作：特定场景下的应用

好了，了解了位运算的基础知识，现在咱们来看看它们在实际应用中能发挥什么作用。

  1. 判断奇偶性

    判断一个数是奇数还是偶数，通常我们会用 % 2。但是，用位运算可以更快！

    def is_even(n):
    return (n & 1) == 0

print(is_even(4))  # 输出 True
print(is_even(5))  # 输出 False

    n & 1 相当于取 n 的二进制表示的最低位。如果最低位是 0，说明是偶数；如果最低位是 1，说明是奇数。位运算比取模运算快得多。

  2. 交换两个数

    交换两个数的值，通常我们需要一个临时变量。但是，用位运算可以不用临时变量！

    def swap(a, b):
    a = a ^ b
    b = a ^ b
    a = a ^ b
    return a, b

x = 5
y = 10
x, y = swap(x, y)
print(x, y)  # 输出 10 5

    这个方法利用了异或运算的性质：a ^ a = 0，a ^ 0 = a，a ^ b ^ b = a。

  3. 求绝对值

    求绝对值，通常我们会用 abs() 函数。但是，用位运算可以更高效！ (虽然通常不推荐，因为可读性较差)

    def absolute_value(n):
    mask = n >> (31)  # 对于32位整数
    return (n + mask) ^ mask
print(absolute_value(-5))
print(absolute_value(5))

    这个方法的原理是：如果 n 是正数，mask 为 0，结果不变；如果 n 是负数，mask 为 -1 (所有位都是1)，相当于求 n 的补码。

  4. 集合操作

    位运算在集合操作中非常有用。我们可以用一个整数的每一位来表示一个元素是否在集合中。

    # 假设我们有 5 个元素：A, B, C, D, E
# 用 00001 表示集合 {A}
# 用 00010 表示集合 {B}
# 用 00100 表示集合 {C}
# 用 01000 表示集合 {D}
# 用 10000 表示集合 {E}

# 集合 {A, C, E}
set1 = 0b10101  # 二进制 10101，十进制 21

# 集合 {B, D}
set2 = 0b01010  # 二进制 01010，十进制 10

# 求并集
union = set1 | set2  # 二进制 11111，十进制 31，集合 {A, B, C, D, E}

# 求交集
intersection = set1 & set2  # 二进制 00000，十进制 0，空集

# 求差集 (set1 - set2)
difference = set1 & (~set2)  # 二进制 10101，十进制 21，集合 {A, C, E}

print(f"Union: {bin(union)}, Decimal: {union}")
print(f"Intersection: {bin(intersection)}, Decimal: {intersection}")
print(f"Difference: {bin(difference)}, Decimal: {difference}")

    这种方法可以高效地表示和操作小规模的集合。

  5. 状态压缩

    在一些算法问题中，我们需要记录状态，如果状态很多，用普通的方法可能会占用大量的空间。这时，我们可以用位运算来进行状态压缩。

    例如，在旅行商问题 (TSP) 中，我们需要记录哪些城市已经被访问过。如果有 n 个城市，我们可以用一个 n 位的二进制数来表示访问状态。

    # 假设有 5 个城市
# 00000 表示没有访问任何城市
# 10000 表示只访问了第一个城市
# 11111 表示访问了所有城市

# 检查是否访问了第 i 个城市
def is_visited(state, i):
    return (state >> i) & 1

# 标记访问了第 i 个城市
def visit(state, i):
    return state | (1 << i)

state = 0b00000  # 初始状态：没有访问任何城市
print(f"Initial state: {bin(state)}")

state = visit(state, 2)  # 访问第 3 个城市
print(f"After visiting city 3: {bin(state)}")

if is_visited(state, 2):
    print("City 3 has been visited.")
else:
    print("City 3 has not been visited.")

    状态压缩可以有效地减少空间占用，提高程序的运行效率。

  6. 快速幂

    计算 a 的 n 次方，通常我们会用循环来实现。但是，用位运算可以更快！

    def fast_power(a, n):
    result = 1
    while n > 0:
        if n & 1:
            result = result * a
        a = a * a
        n >>= 1
    return result

print(fast_power(2, 10))  # 输出 1024

    这个方法的原理是：将 n 表示成二进制数，例如 n = 10 = 1010(binary)，那么 a^10 = a^(8 + 2) = a^8 * a^2。我们只需要计算 a^2, a^4, a^8, ...，然后根据 n 的二进制表示来选择是否将它们乘到结果中。

  7. 查找只出现一次的数字

    在一个数组中，只有一个数字出现一次，其他数字都出现两次，找出这个只出现一次的数字。

    def find_single_number(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

nums = [4, 1, 2, 1, 2]
print(find_single_number(nums))  # 输出 4

    这个方法的原理是：利用异或运算的性质 a ^ a = 0 和 a ^ 0 = a。将所有数字进行异或运算，出现两次的数字会被消掉，最后剩下的就是只出现一次的数字。

  8. 判断一个数是不是2的幂

      def is_power_of_two(n):
      return (n > 0) and (n & (n - 1) == 0)

  print(is_power_of_two(8)) #true
  print(is_power_of_two(6)) #false

    如果一个数是2的幂，那么它的二进制表示中只有一个1。 n & (n-1) 会把 n 的最低位的 1 变成 0。 所以如果 n 是 2 的幂，那么 n & (n – 1) 就会是 0。

三、 位运算的注意事项

  • 优先级：位运算的优先级比较低，所以在使用时要注意加括号。例如，a + b & c 可能会得到错误的结果，应该写成 a + (b & c)。
  • 符号位：对于有符号整数，右移操作可能会涉及到符号位的处理，不同的编程语言可能有不同的实现方式。
  • 溢出：在进行位运算时，要注意结果是否会溢出。

四、 总结

位运算是一种强大的工具，可以在特定场景下提高程序的效率。虽然它看起来有点晦涩难懂，但是只要掌握了基本原理，就能灵活运用。希望今天的讲座能让你对位运算有更深入的了解，并在实际编程中发挥它的威力。

记住，代码的世界里，没有最牛逼的技术，只有最适合的技术。选择合适的工具，才能写出高效、优雅的代码。

好了，今天的讲座就到这里，谢谢大家！ 散会，散会！

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注