LeetCode 位运算详解：原理、技巧与实战应用

引言

位运算是计算机科学中的基础操作，它直接对整数的二进制表示进行操作。在 LeetCode 中，位运算题目虽然不是最常见的，但却是很多高效算法的关键。掌握位运算不仅能帮助我们解决特定类型的问题，还能在某些情况下大大提高算法的效率。本文将深入探讨位运算的基本原理、常用技巧以及在 LeetCode 上的实际应用。

1. 位运算基础

在开始之前，我们先回顾一下基本的位运算操作：

  • &（与）：两个位都为 1 时，结果才为 1
  • |（或）：两个位都为 0 时，结果才为 0
  • ^（异或）：两个位相同为 0，不同为 1
  • ~（取反）：0 变 1，1 变 0
  • <<（左移）：各二进位全部左移若干位，高位丢弃，低位补 0
  • >>（右移）：各二进位全部右移若干位，对无符号数，高位补 0

2. 常用位运算技巧

2.1 判断奇偶

1
2
def is_odd(n):
    return n & 1 == 1

2.2 交换两数

1
2
3
4
5
def swap(a, b):
    a = a ^ b
    b = a ^ b
    a = a ^ b
    return a, b

2.3 获取最低位的 1

1
2
def lowest_bit(n):
    return n & (-n)

2.4 清除最低位的 1

1
2
def clear_lowest_bit(n):
    return n & (n - 1)

2.5 统计二进制中 1 的个数

1
2
3
4
5
6
def count_one(n):
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count

3. LeetCode 实战应用

3.1 LeetCode 136. Single Number

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

1
2
3
4
5
6
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

3.2 LeetCode 191. Number of 1 Bits

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数。

1
2
3
4
5
6
7
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= (n - 1)
            count += 1
        return count

3.3 LeetCode 190. Reverse Bits

颠倒给定的 32 位无符号整数的二进制位。

1
2
3
4
5
6
7
class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for i in range(32):
            result = (result << 1) | (n & 1)
            n >>= 1
        return result

3.4 LeetCode 371. Sum of Two Integers

不使用运算符 + 和 - ，计算两整数 a 、b 之和。

1
2
3
4
5
6
class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF
        while b != 0:
            a, b = (a ^ b) & mask, ((a & b) << 1) & mask
        return a if a <= 0x7FFFFFFF else ~(a ^ mask)

4. 高级位运算技巧

4.1 快速幂

计算 x 的 n 次方，可以用位运算优化。

1
2
3
4
5
6
7
8
def pow(x, n):
    result = 1
    while n:
        if n & 1:
            result *= x
        x *= x
        n >>= 1
    return result

4.2 格雷码生成

格雷码是一个二进制数字系统，其中两个连续的数值仅有一个位数的差异。

1
2
def grayCode(n):
    return [i ^ (i >> 1) for i in range(1 << n)]

4.3 找出不大于 N 的最大的 2 的幂

1
2
3
4
5
6
7
def largestPowerOf2(N):
    N = N | (N >> 1)
    N = N | (N >> 2)
    N = N | (N >> 4)
    N = N | (N >> 8)
    N = N | (N >> 16)
    return (N + 1) >> 1

5. 位运算的应用场景

  1. 优化空间复杂度：用一个整数的不同位表示不同的布尔值
  2. 加速运算：某些数学运算可以通过位运算加速
  3. 状态压缩：在动态规划中使用位来表示状态
  4. 编码与解码：某些编码算法中会用到位运算
  5. 加密算法：许多加密算法中都有位运算的身影
  6. 校验和计算：计算校验和时常用位运算
  7. 图形处理：位运算在图形处理中也有广泛应用

6. 位运算的优化技巧

  1. 使用位掩码：预先计算好的位掩码可以加速位操作
  2. 并行位计数：使用特定的位模式可以并行计算多个位
  3. 查表法：对于一些复杂的位操作，可以使用预计算的查找表
  4. 位域：在 C/C++ 中，可以使用位域来紧凑地存储数据
  5. 利用特定指令集：现代 CPU 往往有专门的位操作指令，可以使用内联汇编或编译器内建函数来利用这些指令

7. 位运算中的常见陷阱

  1. 符号位处理：在处理有符号整数时，要特别注意符号位的处理
  2. 溢出问题：位运算可能导致溢出，特别是在左移操作时
  3. 优先级问题：位运算的优先级较低，经常需要使用括号
  4. 跨平台问题：不同平台的整数位数可能不同，需要注意可移植性
  5. 误用无符号数：在一些语言中，无符号数的行为可能出人意料
  6. 忽视编译器优化：有时编译器的优化可能改变位运算的行为
  7. 过度使用位运算：虽然位运算效率高，但过度使用可能导致代码难以理解和维护

结语

位运算是一种强大而有趣的技术，它不仅能够帮助我们解决特定类型的问题，还能在某些情况下大大提高算法的效率。通过本文的学习，我们深入了解了位运算的基本原理、LeetCode 实战应用以及各种高级技巧。在实际应用中，我们需要根据具体问题选择合适的位运算技巧。记住，高效的位运算不仅需要了解各种技巧，还需要对问题有深入的理解和分析。通过不断练习和总结，我们可以在算法解题中越来越熟练地运用位运算技巧，解决各种复杂问题。同时，这些技能在底层系统开发、优化和调试中也会非常有用，能够帮助我们编写更高效、更精巧的代码。然而，我们也要注意到位运算的局限性和潜在陷阱，在使用时要权衡代码的可读性和性能，选择最合适的解决方案。