基础算法 - 位运算

交换两个数

• 技巧: 使用异或运算 ^ 交换两个数。
• 解释: 无需临时变量即可交换。
• 代码:

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

取反加一求负数

• 技巧: 使用 ~n + 1 求负数。
• 解释: 等价于 -n。
• 代码:

  neg_n = ~n + 1

判断是否为 2 的幂

• 技巧: 使用 n & (n - 1) 判断。
• 解释: 如果结果为 0，n 是 2 的幂。
• 代码:

  if n & (n - 1) == 0:
      print("是2的幂")

计算二进制中 1 的个数

• 技巧: 使用 n &= (n - 1) 循环计算。
• 解释: 每次操作消除一个1，直到 n 为 0。
• 代码:

  count = 0
  while n:
      n &= (n - 1)
      count += 1
  print(count)

获取最低位的 1

• 技巧: 使用 n & -n 获取最低位的 1。
• 解释: 结果为最低位 1 所在的值。
• 代码:

  lowest_one = n & -n

将最低位的 1 置 0

• 技巧: 使用 n & (n - 1) 将最低位的 1 置 0。
• 解释: 常用于计算 1 的个数或判断 2 的幂。
• 代码:

  n = n & (n - 1)

位移运算

• 技巧: 使用 << 和 >> 进行位移。
• 解释: n << k 等价于 n * 2^k，n >> k 等价于 n // 2^k。
• 代码:

  n = n << 1  # 乘以2
  n = n >> 1  # 除以2

掩码操作

• 技巧: 使用掩码提取或设置特定位。
• 解释: 常用于位掩码操作。
• 代码:

  mask = 1 << k  # 第k位
  bit = (n & mask) >> k  # 提取第k位
  n |= mask  # 设置第k位为1
  n &= ~mask  # 设置第k位为0

快速幂运算

• 技巧: 使用位移和与运算加速幂运算。
• 解释: 常用于大数幂运算。
• 代码:

  def fast_pow(base, exponent):
      result = 1
      while exponent > 0:
          if exponent & 1:
              result *= base
          base *= base
          exponent >>= 1
      return result

判断某一位是否为 1

• 技巧: 使用 n & (1 << k) 判断第 k 位是否为 1。
• 解释: 结果为 0 则第 k 位为 0，否则为 1。
• 代码:

  if n & (1 << k):
      print("第k位是1")

将某一位设置为 1

• 技巧: 使用 n |= (1 << k) 将第 k 位设置为 1。
• 解释: 无论原值如何，第 k 位都会被置 1。
• 代码:

  n |= (1 << k)

将某一位设置为 0

• 技巧: 使用 n &= ~(1 << k) 将第 k 位设置为 0。
• 解释: 无论原值如何，第 k 位都会被置 0。
• 代码:

  n &= ~(1 << k)

异或运算的性质

• 技巧: 异或运算满足交换律和结合律，且 a ^ a = 0，a ^ 0 = a。
• 解释: 常用于找唯一出现一次的数字。
• 代码:

  result = 0
  for num in nums:
      result ^= num
  print(result)