当前位置：首页 > article >正文

简单题:Base32 编码和解码问题| 豆包MarsCode AI刷题

article 2024/11/5 13:46:35

Base32 编码和解码问题解析

Base32 是一种将二进制数据编码为 ASCII 字符串的编码方式，它使用 32 个字符来表示 5 位的二进制数。与 Base64 相比，Base32 的编码效率稍低，但其在某些场景下具有特定的应用优势，比如对字符集的限制更为宽松。

编码流程解析

预处理二进制数据：
- 原始二进制数据可能不是 5 位的倍数，因此需要在末尾补 0，直到数据长度成为 5 的倍数。
分组：
- 将预处理后的二进制数据以 5 位为一组进行划分。
索引转换：
- 将每一组的 5 位二进制数转换为对应的十进制索引（0-31）。
字符映射：
- 使用 Base32 的索引-字符转换表，将索引映射为对应的字符。
补全字符：
- 根据原始二进制数据的总位数，计算需要补全的 ‘+’ 字符数量。这是因为在 Base32 编码中，每 5 位数据对应一个字符，但原始数据的长度可能不是 8（一个字符的位数/5）的整数倍，因此需要用 ‘+’ 字符来补齐。
- 补全规则：根据原始数据的位数除以 40（5 位/字符 * 8 字符/组）的余数来确定 ‘+’ 的数量。

解码流程解析

去除补全字符：
- 首先去除编码字符串末尾的 ‘+’ 字符。
字符到索引的映射：
- 使用 Base32 的字符-索引转换表，将每个字符映射回其对应的十进制索引。
分组并转换为二进制：
- 将索引转换回 5 位的二进制数，并重新组合成原始的二进制数据。
去除末尾的补 0：
- 由于编码时可能在末尾补 0，解码后需要去除这些额外的 0。

代码实现与分析

（由于篇幅限制，这里只给出伪代码和核心逻辑，实际实现需要编写完整的函数）

# Base32 字符集
BASE32_CHARS = "9876543210mnbvcxzasdfghjklpoiuyt"

# 索引到字符的映射表
INDEX_TO_CHAR = {i: BASE32_CHARS[i] for i in range(32)}

# 字符到索引的映射表
CHAR_TO_INDEX = {c: i for i, c in enumerate(BASE32_CHARS)}

def base32_encode(raw_bytes):
    # 预处理：补 0
    bits = ''.join(f'{byte:08b}' for byte in raw_bytes)  # 将每个字节转换为 8 位二进制字符串
    bits += '0' * (5 - len(bits) % 5)  # 补 0 至长度为 5 的倍数
    
    # 分组并转换为字符
    encoded_chars = []
    for i in range(0, len(bits), 5):
        index = int(bits[i:i+5], 2)  # 将 5 位二进制转换为十进制索引
        encoded_chars.append(INDEX_TO_CHAR[index])
    
    # 补全 '+' 字符
    remainder = len(bits) % 40
    padding = 8 - (remainder % 8) if remainder % 8 != 0 else 0
    encoded_str = ''.join(encoded_chars) + '+' * padding
    
    return encoded_str

def base32_decode(encoded_str):
    # 去除末尾的 '+' 字符
    encoded_str = encoded_str.rstrip('+')
    
    # 分组并转换为索引
    bits = []
    for char in encoded_str:
        index = CHAR_TO_INDEX[char]
        bits.extend(f'{index:05b}')  # 将索引转换为 5 位二进制字符串并展开
    
    # 转换为字节数组并去除末尾的补 0
    byte_array = bytearray()
    for i in range(0, len(bits), 8):
        byte = int(bits[i:i+8], 2)  # 将 8 位二进制转换为十进制字节
        if byte != 0 or i + 8 == len(bits):  # 去除末尾的补 0（但保留最后一个非零字节）
            byte_array.append(byte)
    
    return byte_array