Blog of AgioPan
0%

数据结构与算法自学笔记（11）- 位图&位运算实现加减乘除

Posted on In ,

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

本笔记包括了位图数据结构的原理、实现和应用，以及如何用位运算实现加减乘除（完全不依赖任何算术运算符）。涵盖了class032 and class033的内容

032【必备】位图

前置知识

在学习位图之前，需要掌握以下基础知识：

  • 二进制和位运算操作
  • 对数器的使用方法

Python特别提醒：在实现位运算题目时需要特别注意溢出和符号扩展问题，通常需要手动处理：

1
2
# Python中处理溢出的常见方法
result = (n << shift_amount) & 0xFFFFFFFF

位图的核心概念

什么是位图

位图（Bitset）是一种极其节省空间的数据结构，用于存储大量布尔值。相比传统哈希表，位图具有显著的空间优势：

  • 哈希表：每存储一个数字需要32个bit的空间
  • 位图：每存储一个数字只需要1个bit的空间

位图的基本原理

位图本质上是用bit组成的数组来存放值，使用bit的状态（1和0）来表示元素的存在性：

  • bit位为1：表示该数字存在于集合中
  • bit位为0：表示该数字不存在于集合中

基本思想：

1
2
用一个很长的二进制位数组，每一位（bit）对应一个整数的"有无"状态
第0位代表数字0，第1位代表数字1，第2位代表数字2，依此类推

位图的适用场景

优势：

  • 极大节省空间（1个数字仅占1个bit）
  • 查询和修改操作都是O(1)时间复杂度
  • 支持高效的批量操作

限制：

  • 必须是连续范围的整数
  • 范围不能过大（适合0到几百万，不适合到几十亿）
  • 只能表示元素的存在性，不能存储额外信息

适用场景：

  • 判断大量整数是否存在
  • 统计范围内数字的出现情况
  • 实现简单的集合操作

位图的实现

位图实现原理

类设计接口

1
2
3
4
5
6
class Bitset:
    def __init__(self, n):          # 初始化位图，支持0~n-1所有数字
    def add(self, num):             # 把num加入到位图
    def remove(self, num):          # 把num从位图中删除
    def reverse(self, num):         # 翻转num的状态（存在则删除，不存在则添加）
    def contains(self, num):        # 查询num是否在位图中

完整实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Bitset:
    def __init__(self, n):
        """
        初始化位图，支持0~n-1范围内的数字
        n个数字需要 (n + 31) // 32 个32位整数来存储
        """
        # 计算需要多少个32位整数
        # 使用 (n + 31) // 32 实现向上取整
        # 例如：32个数字需要1个整数，33个数字需要2个整数
        self.set = [0] * ((n + 31) // 32)
    
    def add(self, num):
        """
        将num添加到位图中（将对应位设置为1）
        """
        # num // 32：确定数字在第几个32位整数中
        # num % 32：确定在该32位整数中的第几位
        # 1 << (num % 32)：创建掩码，将1左移到对应位置
        # |=：按位或赋值，将对应位设置为1
        self.set[num // 32] |= 1 << (num % 32)
    
    def remove(self, num):
        """
        将num从位图中删除（将对应位设置为0）
        """
        # ~(1 << (num % 32))：创建掩码并取反，除了目标位其他位都是1
        # &=：按位与赋值，将对应位清除为0
        self.set[num // 32] &= ~(1 << (num % 32))
    
    def reverse(self, num):
        """
        翻转num在位图中的状态
        如果存在则删除，如果不存在则添加
        """
        # ^=：按位异或赋值
        # 如果位是0，异或1后变成1
        # 如果位是1，异或1后变成0
        self.set[num // 32] ^= 1 << (num % 32)
    
    def contains(self, num):
        """
        判断num是否存在于位图中
        """
        # >> (num % 32)：将目标位移动到最低位
        # & 1：提取最低位的值
        # == 1：判断是否为1
        return ((self.set[num // 32] >> (num % 32)) & 1) == 1

关键实现细节

1. 空间分配策略

1
2
3
4
5
6
7
# 向上取整的巧妙实现
# 对于n个数字，需要的32位整数个数
array_size = (n + 31) // 32

# 原理：
# - 如果n=32，则(32+31)//32 = 63//32 = 1（正好1个整数）
# - 如果n=33，则(33+31)//32 = 64//32 = 2（需要2个整数）

2. 位置计算

1
2
3
4
5
def get_position(num):
    """计算数字num在位图中的位置"""
    array_index = num // 32    # 在第几个32位整数中
    bit_index = num % 32       # 在该整数的第几位
    return array_index, bit_index

3. 位运算技巧总结

操作 位运算实现 说明
设置位为1 x |= (1 << i) 按位或运算
清除位为0 x &= ~(1 << i) 按位与运算（掩码取反）
翻转位 x ^= (1 << i) 按位异或运算
检查位 (x >> i) & 1 右移后提取最低位

对数器测试

测试设计思路

使用Python内置的set作为参照标准，对位图的所有操作进行验证：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def test_bitset():
    """使用对数器验证位图实现的正确性"""
    n = 1000          # 位图大小
    testTimes = 10000 # 测试次数
    
    print("测试开始")
    bitSet = Bitset(n)      # 被测试的位图结构
    hashSet = set()         # 参照标准（Python内置set）
    
    print("调用阶段开始")
    for _ in range(testTimes):
        decide = random.random()                    # 随机决定操作类型
        number = int(random.random() * n)          # 随机生成0~n-1的数字
        
        if decide < 0.333:                         # 33%概率执行add操作
            bitSet.add(number)
            hashSet.add(number)
        elif decide < 0.666:                       # 33%概率执行remove操作
            bitSet.remove(number)
            hashSet.discard(number)                # 使用discard避免KeyError
        else:                                      # 34%概率执行reverse操作
            bitSet.reverse(number)
            if number in hashSet:
                hashSet.remove(number)
            else:
                hashSet.add(number)
    
    print("调用阶段结束")
    print("验证阶段开始")
    
    # 验证所有数字的存在性是否一致
    for i in range(n):
        if bitSet.contains(i) != (i in hashSet):
            print("出错了!")
            return False
    
    print("验证阶段结束")
    print("测试结束")
    return True

测试覆盖的场景

  1. 随机操作序列：大量随机的增删改查操作
  2. 边界条件：0和n-1等边界值
  3. 重复操作：对同一个数字的重复操作
  4. 状态一致性：每次操作后验证状态的一致性

性能分析

时间复杂度

操作 时间复杂度 说明
初始化 O(n/32) 需要初始化数组
add O(1) 常数时间位运算
remove O(1) 常数时间位运算
reverse O(1) 常数时间位运算
contains O(1) 常数时间位运算

空间复杂度

  • 位图空间：O(n/32) = O(n)
  • 相比哈希表：空间节省约32倍

实际空间对比

1
2
3
4
5
6
7
8
9
10
11
# 存储1000万个数字的空间对比
numbers = 10_000_000

# 哈希表（假设每个数字32位）
hash_space = numbers * 32  # 320,000,000 bits

# 位图
bitset_space = numbers * 1  # 10,000,000 bits

# 空间节省比例
space_saving = hash_space / bitset_space  # 32倍

应用场景与扩展

典型应用场景

  1. 大数据去重：判断海量数据中的重复元素
  2. 布隆过滤器基础：位图是布隆过滤器的核心组件
  3. 状态压缩：在动态规划中压缩状态空间
  4. 集合运算：高效实现并集、交集、差集运算

位图的集合运算

1
2
3
4
5
6
7
8
9
10
11
12
13
def bitset_union(bitset1, bitset2):
    """位图并集运算"""
    result = Bitset(max(len(bitset1.set), len(bitset2.set)) * 32)
    for i in range(min(len(bitset1.set), len(bitset2.set))):
        result.set[i] = bitset1.set[i] | bitset2.set[i]
    return result

def bitset_intersection(bitset1, bitset2):
    """位图交集运算"""
    result = Bitset(max(len(bitset1.set), len(bitset2.set)) * 32)
    for i in range(min(len(bitset1.set), len(bitset2.set))):
        result.set[i] = bitset1.set[i] & bitset2.set[i]
    return result

实际应用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def find_missing_numbers(arr, n):
    """找出0到n-1范围内缺失的所有数字"""
    bitset = Bitset(n)
    
    # 标记存在的数字
    for num in arr:
        if 0 <= num < n:
            bitset.add(num)
    
    # 找出缺失的数字
    missing = []
    for i in range(n):
        if not bitset.contains(i):
            missing.append(i)
    
    return missing

# 示例使用
arr = [0, 1, 3, 6, 7, 9]
n = 10
missing = find_missing_numbers(arr, n)
print(f"缺失的数字: {missing}")  # 输出: [2, 4, 5, 8]

总结

位图是一种非常实用的数据结构，特别适合处理大量整数的存在性判断问题。它的核心优势在于：

  1. 极致的空间效率：相比传统数据结构节省32倍空间
  2. 优秀的时间性能：所有基本操作都是O(1)时间复杂度
  3. 简单的实现逻辑：基于基础位运算，易于理解和实现

在大数据处理、系统设计等场景中，位图都是一个非常有价值的工具。

033【必备】位运算实现加减乘除

核心思想

位运算实现四则运算的核心在于模拟计算机底层的运算逻辑：

  • 加法：基于异或（无进位相加）和与运算（进位处理）
  • 减法：通过加法和取反实现
  • 乘法：基于移位和加法的重复运算
  • 除法：基于减法和移位的优化算法

Python中的特殊处理

在实现过程中，需要特别注意Python与Java的差异：

1
2
3
4
5
6
7
8
# Java中的整数范围限制
MIN = -2**31      # -2147483648
MAX = 2**31 - 1   # 2147483647

# Python中需要手动处理32位整数溢出
result &= 0xFFFFFFFF  # 保持32位
if result > 0x7FFFFFFF:
    result = ~(result ^ 0xFFFFFFFF)  # 转换为有符号整数

1. 加法实现（核心基础）

算法原理

加法的位运算实现基于两个关键概念：

  1. 无进位相加：使用异或运算（XOR）
  2. 进位信息：使用与运算（AND）后左移
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
@staticmethod
def add(a, b):
    """位运算实现加法"""
    #单次相加的结果为：无进位相加的结果+进位信息
    ans = a
    while b != 0: # 当b为0时，说明没有进位了，加法结束
        # 单次进位只能把当前位的进位信息加到下一高位，但新一位的进位可能和更高位产生新的进位冲突，需要继续处理。
        # 只有所有进位都为0，结果才是完整无误的。
        # ans : a和b无进位相加的结果
        ans = a ^ b
        # b : a和b相加时的进位信息
        b = (a & b) << 1
        # Python中int无限大，为了模拟int32，需要对超出部分进行处理
        # 下面两行确保ans和b都保持32位
        ans &= 0xFFFFFFFF
        b &= 0xFFFFFFFF
        a = ans
    # 处理负数转为补码
    return ans if ans <= 0x7FFFFFFF else ~(ans ^ 0xFFFFFFFF)  #结果超过最大值时，需要将无符号32位结果转换为有符号，当加法结果超过0x7FFFFFFF时，实际上表示的是负数，需要转换为对应的有符号表示
    #将ans与全1进行异或，相当于按位取反，~(...)：再次取反，相当于恢复原值

执行过程示例

以 5 + 3 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
第1轮：a=5(101), b=3(011)
  无进位：5^3 = 101^011 = 110 = 6
  进位：(5&3)<<1 = (001)<<1 = 010 = 2
  
第2轮：a=6(110), b=2(010)  
  无进位：6^2 = 110^010 = 100 = 4
  进位：(6&2)<<1 = (010)<<1 = 100 = 4
  
第3轮：a=4(100), b=4(100)
  无进位：4^4 = 100^100 = 000 = 0
  进位：(4&4)<<1 = (100)<<1 = 1000 = 8
  
第4轮：a=0(000), b=8(1000)
  无进位：0^8 = 1000 = 8
  进位：(0&8)<<1 = 0
  
结果：8

2. 取反运算

1
2
3
4
@staticmethod
def neg(n):
    """取相反数：~n + 1"""
    return BitOperationAddMinusMultiplyDivide.add(~n, 1)

原理解释

基于补码的性质：一个数的相反数等于该数按位取反后加1。

  • 正数：直接按位取反加1
  • 负数：同样规则，利用补码特性

3. 减法实现

1
2
3
4
@staticmethod
def minus(a, b):
    """减法就是加上-b"""
    return BitOperationAddMinusMultiplyDivide.add(a, BitOperationAddMinusMultiplyDivide.neg(b))

减法的实现非常简洁：a - b = a + (-b)

4. 乘法实现（龟速乘）

算法原理

基于二进制乘法的原理，将乘法转换为多次加法和移位运算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
@staticmethod
def multiply(a, b):
    """位运算实现乘法"""
    # 把乘法拆成若干次加法，用位运算（移位）和加法实现，不直接用乘号，适合大数和防溢出场合。
    # 二进制的乘法也是像十进制一样，从右到左，一位一位的乘，然后错位相加
    ans = 0
    # 为了模拟int32，确保a, b, ans都在32位内
    a &= 0xFFFFFFFF
    b &= 0xFFFFFFFF
    while b != 0: #说明乘数没有耗尽，继续乘
        if (b & 1) != 0: #说明当前位是1，需要加到结果上
            # 考察b当前最右的状态！
            ans = BitOperationAddMinusMultiplyDivide.add(ans, a)
            ans &= 0xFFFFFFFF  # 保持32位
        a = (a << 1) & 0xFFFFFFFF  # 左移并保持32位
        # Java中的 >>> 表示无符号右移，Python没有，需特殊处理
        if b >= 0:
            b >>= 1
        else:
            #在Java中，>>> 是无符号右移操作，无论原数是正数还是负数，右移时都在高位补0。但在Python中，>> 是有符号右移，对于负数会补1
            #内存中：b + 0x100000000和b的位模式完全相同，这时候又该告诉python该改变语义理解了
            b = (b + 0x100000000) >> 1 #0x100000000等于2^32
        b &= 0xFFFFFFFF  # 保持32位
    # 处理负数转为补码
    return ans if ans <= 0x7FFFFFFF else ~(ans ^ 0xFFFFFFFF) # 0xFFFFFFFF是全1，保证结果是32位，
    # 如果结果超过0x7FFFFFFF，说明发生了溢出
    # 使用~(ans ^ 0xFFFFFFFF)将结果"包装"到32位范围内
    # 这样就能得到正确的有符号32位整数结果

执行过程示例

以 5 × 3 为例：

1
2
3
4
5
3的二进制：011
第1轮：b=011, b&1=1, ans += 5×2^0 = 5
第2轮：b=001, b&1=1, ans += 5×2^1 = 5+10 = 15
第3轮：b=000, 结束
结果：15

应用场景

这种”龟速乘”在以下场景特别有用：

  • 大数乘法防溢出
  • 模运算：(a × b) % m
  • 快速幂运算的基础

5. 除法实现（最复杂）

核心挑战

除法是四则运算中最复杂的，需要处理多种边界情况：

  1. 除数为0的情况
  2. 整数最小值的特殊处理
  3. 溢出预防
  4. 符号处理

主要函数结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
@staticmethod
def divide(a, b):
    """主除法函数，处理各种边界情况"""
    # 处理 a 和 b 都为最小值的情况
    if a == BitOperationAddMinusMultiplyDivide.MIN and b == BitOperationAddMinusMultiplyDivide.MIN:
        # a和b都是整数最小
        return 1
    # 处理 a 和 b 都不是最小值的情况
    if a != BitOperationAddMinusMultiplyDivide.MIN and b != BitOperationAddMinusMultiplyDivide.MIN:
        # a和b都不是整数最小，那么正常去除
        return BitOperationAddMinusMultiplyDivide.div(a, b)
    # 处理 b 为最小值的情况
    if b == BitOperationAddMinusMultiplyDivide.MIN: 
        # a不是整数最小，b是整数最小，整数最小值是负数，而且整数最小值无法转成相反数
        return 0
    # 处理 a 为最小值，b 为 -1 的情况（防止溢出）
    # 第1个if不成立：a 和 b 不都是最小值；第2个if不成立：a 和 b 不都不是最小值；第3个if不成立：b 不是最小值，则排除完b，a就是最小值
    if b == BitOperationAddMinusMultiplyDivide.neg(1):
        # a是整数最小，b是-1，返回整数最大，因为题目里明确这么说了
        return BitOperationAddMinusMultiplyDivide.MAX
    # a是整数最小，b不是整数最小，b也不是-1
    a = BitOperationAddMinusMultiplyDivide.add(a, b if b > 0 else BitOperationAddMinusMultiplyDivide.neg(b)) #让 a 不再是最小值，这样就可以安全地调用 div 函数了，如果 b > 0：a = a + b；如果 b < 0：a = a + (-b)
    ans = BitOperationAddMinusMultiplyDivide.div(a, b) # 现在 a 不再是最小值，可以安全地调用 div 函数
    offset = BitOperationAddMinusMultiplyDivide.neg(1) if b > 0 else 1 # 如果 b > 0，则 offset = -1；如果 b < 0，则 offset = 1
    return BitOperationAddMinusMultiplyDivide.add(ans, offset) # 最后把 offset 加回去

核心除法算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@staticmethod
def div(a, b): #向下取整，但是不返回余数
    """核心除法实现，要求a和b都不是整数最小值"""
    x = BitOperationAddMinusMultiplyDivide.neg(a) if a < 0 else a  # 取绝对值
    y = BitOperationAddMinusMultiplyDivide.neg(b) if b < 0 else b  # 取绝对值
    ans = 0
    i = 30
    while i >= 0:
        # (x >> i) >= y 时，说明y << i 还能减掉
        if (x >> i) >= y: #判断x右移i位后是否大于等于y，若大于则记录1
            ans |= (1 << i)  # 记录这个位
            x = BitOperationAddMinusMultiplyDivide.minus(x, y << i)  # x 减去 y << i，即y*2^i
        i = BitOperationAddMinusMultiplyDivide.minus(i, 1)  # 相当于 i--
    # 最后根据正负判断符号
    return BitOperationAddMinusMultiplyDivide.neg(ans) if (a < 0) ^ (b < 0) else ans #当两个数的符号不同时，结果取负；当符号相同时，结果保持正。

算法原理解析

除法算法本质上是二分查找的变种：

  1. 从高位到低位：尝试每一位是否能为1
  2. 位移优化：y << i 相当于 y × 2^i
  3. 贪心策略：能减就减，记录对应的位

执行过程示例

以 10 ÷ 3 为例：

1
2
3
4
5
6
7
x=10, y=3
i=30: (10>>30)=0 < 3, 跳过
...
i=2: (10>>2)=2 < 3, 跳过  
i=1: (10>>1)=5 >= 3, ans|=(1<<1), x=10-6=4
i=0: (4>>0)=4 >= 3, ans|=(1<<0), x=4-3=1
结果：ans = 11(二进制) = 3(十进制)

边界情况处理

整数最小值的特殊性

1
2
MIN = -2**31  # -2147483648
MAX = 2**31 - 1  # 2147483647

整数最小值的特殊性在于它没有对应的正数，因为：

  • 最小值的绝对值是 2^31
  • 最大正整数只有 2^31 - 1

处理策略

  1. 预处理：将最小值调整为非最小值
  2. 后处理：补偿调整造成的误差
  3. 特殊返回：MIN ÷ (-1) 返回 MAX

完整实现的使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
# 创建类实例
calc = BitOperationAddMinusMultiplyDivide()

# 测试各种运算
print(calc.add(15, 27))        # 42
print(calc.minus(50, 18))      # 32  
print(calc.multiply(6, 7))     # 42
print(calc.divide(84, 2))      # 42

# 测试边界情况
print(calc.divide(-2**31, -1)) # 2**31-1 (MAX)
print(calc.divide(10, 3))      # 3
print(calc.divide(-10, 3))     # -3

时间复杂度分析

运算 时间复杂度 空间复杂度 说明
加法 O(1) O(1) 最多32次循环
减法 O(1) O(1) 调用加法和取反
乘法 O(1) O(1) 最多32次循环
除法 O(1) O(1) 固定31次循环

虽然有循环，但循环次数是固定的（最多32次），所以时间复杂度为常数。

实际应用场景

    1. 底层系统编程
      在某些嵌入式系统或底层驱动中，可能需要在没有算术运算单元的情况下实现运算。
    1. 大数运算
      在实现大整数库时，这些技巧是基础构建块。
    1. 密码学应用
      在某些密码学算法中，需要避免使用标准库的运算函数。
    1. 算法竞赛
      某些特殊题目可能限制算术运算的使用。
    1. 教学演示
      帮助理解计算机底层运算原理。

总结与思考

位运算实现四则运算展示了计算机底层运算的本质。虽然在实际开发中很少直接使用，但理解这些原理对于：

  1. 加深对计算机原理的理解
  2. 提升位运算技巧
  3. 应对特殊场景需求
  4. 算法思维的训练

都具有重要意义。特别是除法的实现，体现了二分思想和贪心策略的完美结合，是位运算技巧的集大成者。