初识算法 · 位运算常见总结(1)

位运算是计算机科学中一项非常基础且重要的技术，它通过对二进制位（即 0 和 1）的操作，能够高效地完成一些常见的任务，如数据的压缩、加密解密、图像处理等。虽然位运算相较于常见的算术运算和逻辑运算看起来有些抽象，但它却在许多高效算法中起着不可或缺的作用，尤其是在性能要求较高的应用中，往往能起到事半功倍的效果。

在这篇文章中，我们将深入探讨位运算的基本概念，常见的位运算操作，并通过具体的应用案例帮助大家更好地理解位运算的实用性。

1. 位运算基础

位运算是对整数在二进制位层面进行操作的计算方法。计算机内部的一切数据都是由二进制组成的，因此，位运算能够直接操作数据的最基本单位——二进制位。

1.1 位运算符

在常见的编程语言中（如 C、C++、Java、Python 等），位运算符主要有以下几种：

与运算（&）：按位与运算，即两个二进制数的每一位都进行与操作，只有当两位都是1时，结果才为1，否则为0。
```
pythonCopy Code
5 & 3  # 5: 0101, 3: 0011, 结果是 0001，输出 1
```
或运算（|）：按位或运算，即两个二进制数的每一位都进行或操作，只有当两位都为0时，结果才为0，其他情况结果为1。
```
pythonCopy Code
5 | 3  # 5: 0101, 3: 0011, 结果是 0111，输出 7
```
异或运算（^）：按位异或运算，即两个二进制数的每一位都进行异或操作，只有当两个二进制位不同（一个为1，另一个为0）时，结果才为1。
```
pythonCopy Code
5 ^ 3  # 5: 0101, 3: 0011, 结果是 0110，输出 6
```
非运算（~）：按位非运算，对一个数的每一位取反，即 0 变成 1，1 变成 0。
```
pythonCopy Code
~5  # 5: 0101, 结果是 1010，输出 -6
```
左移运算（<<）：将一个二进制数的各个二进制位向左移动指定的位数，左移的同时，低位补 0。
```
pythonCopy Code
5 << 1  # 5: 0101, 结果是 1010，输出 10
```
右移运算（>>）：将一个二进制数的各个二进制位向右移动指定的位数，右移时高位根据符号位（符号扩展或零扩展）补充。
```
pythonCopy Code
5 >> 1  # 5: 0101, 结果是 0010，输出 2
```

1.2 位运算的特性

位运算是非常高效的，通常是常数时间 O(1) 操作，在一些性能要求高的应用场景下，能够极大地提升程序的效率。
位运算可以用于直接操作数字的二进制表示，帮助我们节省空间和时间。
位运算能够直接控制数据的具体位，这对于一些要求高效、底层操作的场景非常重要。

2. 常见位运算应用场景

虽然位运算的理论看起来较为简单，但其应用却非常广泛，尤其是在涉及到大数据量、频繁操作的场景中，能够大大提高算法的效率。

2.1 快速判断一个数是否是 2 的幂

判断一个整数是否是 2 的幂是一个经典的位运算问题。如果一个数是 2 的幂，它的二进制表示中只有一个 1，其他都是 0。例如，8 的二进制表示是 1000，16 的二进制表示是 10000。

一个常见的技巧是：如果 n 是 2 的幂，则 n & (n - 1) == 0。这是因为 n - 1 会将 n 的二进制表示中的最低的 1 变为 0，并将其后面的位变为 1。

pythonCopy Code
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(10)) # False

2.2 交换两个变量的值

我们可以通过位运算快速交换两个数的值，且不需要借助第三个变量。这个方法利用了异或运算的性质：a ^ b 可以将 a 和 b 的不同部分提取出来。

交换的步骤如下：

a = a ^ b
b = a ^ b（此时 b 恢复成原来的 a）
a = a ^ b（此时 a 恢复成原来的 b）

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

# 示例
a, b = 5, 10
a, b = swap(a, b)
print(a, b)  # 输出 10 5

2.3 统计一个数的二进制表示中 1 的个数

我们可以使用位运算高效地统计一个整数二进制表示中有多少个 1。一个经典的算法是：将 n 和 n - 1 做与运算，这样可以消除 n 二进制表示中最右边的 1。然后重复这一操作，直到 n 变为 0。

pythonCopy Code
def count_ones(n):
    count = 0
    while n:
        count += 1
        n &= (n - 1)
    return count

# 示例
print(count_ones(5))  # 输出 2，5 的二进制表示是 101

2.4 判断两个整数是否有相同的位

如果两个整数的二进制表示有相同的位，我们可以通过与运算判断。可以通过将两个数进行与运算，然后检查结果是否等于原始数之一。

pythonCopy Code
def have_same_bit(a, b):
    return (a & b) > 0

# 示例
print(have_same_bit(5, 3))  # True，5: 0101, 3: 0011 有相同的位
print(have_same_bit(5, 8))  # False，5: 0101, 8: 1000 没有相同的位

2.5 利用位运算加速大数运算

位运算常常用于大数运算，例如计算模运算（取余）。在某些场合下，尤其是处理二进制数据时，直接使用位运算可以大大提升效率。比如，如果要求一个数模 2 的结果（即判断该数是奇数还是偶数），可以使用与运算 n & 1，这比用除法运算更高效。

pythonCopy Code
def is_odd(n):
    return (n & 1) != 0

# 示例
print(is_odd(5))  # True，5 是奇数
print(is_odd(8))  # False，8 是偶数

2.6 使用位运算实现乘法和除法

在计算机中，乘法和除法运算常常可以通过位运算来优化，尤其是对于 2 的幂次方数的乘法和除法。

乘以 2 的幂：通过左移运算实现 n * (2^k)。
除以 2 的幂：通过右移运算实现 n / (2^k)。

pythonCopy Code
def multiply_by_power_of_two(n, k):
    return n << k

def divide_by_power_of_two(n, k):
    return n >> k

# 示例
print(multiply_by_power_of_two(5, 2))  # 20，5 * 4
print(divide_by_power_of_two(20, 2))   # 5，20 / 4
``