python中的位运算

Question

class Solution:
  def isUnique(self, astr: str) -> bool:
    mark = 0
    for char in astr:
      move_bit = ord(char) - ord('a')
      if (mark & (1 << move_bit)) != 0:
        return False
      else:
        mark |= (1 << move_bit)
    return True

s = Solution()
s.isUnique("abcd")

可以解释下这个位运算解题思路中，红色划线部分，是什么意思吗？谢谢

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

这段 Python 代码是一个用于检测给定字符串 astr 中的字符是否都是唯一的算法。它使用了位运算来高效地完成这个任务。红色划线部分的代码涉及到两个位运算符：&（按位与）和 |=（按位或赋值）。

1. mark & (1 << move_bit)：这行代码是用来检查 mark 变量中是否已经设置了与当前字符对应的位。1 << move_bit 这部分是将数字 1 向左移动 move_bit 位，这样就会在 move_bit 位上设置一个 1，其他位都是 0。例如，如果 move_bit 是 1，那么 1 << 1 的结果就是 2（二进制 10），其中只有第 1 位是 1。然后，使用 & 运算符与 mark 进行按位与操作，如果 mark 中的相应位已经被设置（即之前出现过该字符），那么结果不为 0，表示字符不是唯一的。

2. mark |= (1 << move_bit)：这行代码是在 mark 变量中设置对应当前字符的位。|= 是按位或赋值运算符，它将 mark 与 1 << move_bit 进行按位或操作，并将结果赋值回 mark。如果 mark 中的相应位之前没有被设置，那么这个位现在会被设置为 1，表示这个字符已经出现过。

简单来说，这段代码通过一个整数 mark 来跟踪字符串中已经出现过的字符。每个字符对应一个唯一的位，如果一个字符的位在 mark 中已经被设置，那么字符串中的字符不是唯一的；如果没有被设置，就将其设置为 1，表示这个字符是第一次出现。

这个算法之所以高效，是因为它只需要一个整数来存储所有字符的状态，而不是使用额外的数据结构（如集合或列表）来存储已经出现过的字符。

参考链接：

• Python 官方文档关于位运算符的说明：Python Bitwise Operators
• 位运算在算法中的应用：Bit Manipulation in Algorithms