C语言中如何表示长比特序列？十六进制转Base64遇移位难题

嘿，我刚巧啃过Cryptopals的这个挑战，你的思路方向完全没问题！其实不用费劲去操作整个数组左移，换个用比特缓冲区+位运算的思路会轻松很多，我给你拆解下具体怎么搞：

核心思路：用缓冲区累积比特位，按需提取6位组 #

你已经知道两个十六进制字符对应一个8位字节，接下来不用纠结“左移整个数组”，而是用一个整数作为临时缓冲区，把字节的比特位存进去，攒够6位就提取转换，剩下的继续和下一个字节的比特位拼接：

1. 先把十六进制字符串转成字节数组
   这步你已经想到了，比如"49"会被转成十进制73（也就是二进制01001001），直接用语言自带的工具就能搞定，比如Python里的bytes.fromhex(hex_str)。

2. 初始化缓冲区和计数器
   用一个整数buffer来存累积的比特位，初始值为0；再用buffer_bits记录当前缓冲区里有多少位，初始值0。

3. 遍历每个字节，填充缓冲区并提取6位组

   • 把当前字节加到缓冲区：buffer = (buffer << 8) | byte_value，同时buffer_bits += 8（相当于把新字节的8位拼到缓冲区末尾）。
   • 循环检查缓冲区的位数是否≥6：
     • 取最左边的6位：six_bits = buffer >> (buffer_bits - 6)（比如缓冲区有10位，就右移4位，把最高6位移到最低位）。
     • 把这6位对应到Base64字符（Base64表是A-Z,a-z,0-9,+/"，索引就是6位的十进制值）。
     • 更新缓冲区：用掩码(1 << (buffer_bits - 6)) - 1把已经提取的6位去掉，同时buffer_bits -= 6。

4. 处理剩余的不足6位的比特
   遍历完所有字节后，如果缓冲区还有剩余的位（比如2位或4位），就补0凑够6位再转成Base64字符，然后根据剩余位数补=：剩2位补两个=，剩4位补一个=。

举个代码示例（Python） #

def hex_to_base64(hex_str):
    base64_chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
    buffer = 0
    buffer_bits = 0
    result = []
    
    # 十六进制转字节数组
    byte_array = bytes.fromhex(hex_str)
    
    for byte in byte_array:
        buffer = (buffer << 8) | byte
        buffer_bits += 8
        
        # 提取所有可处理的6位组
        while buffer_bits >= 6:
            six_bits = buffer >> (buffer_bits - 6)
            result.append(base64_chars[six_bits])
            # 移除已处理的6位，保留剩余比特
            buffer = buffer & ((1 << (buffer_bits - 6)) - 1)
            buffer_bits -= 6
    
    # 处理剩余的比特位
    if buffer_bits > 0:
        # 补0到6位
        six_bits = buffer << (6 - buffer_bits)
        result.append(base64_chars[six_bits])
        # 补=完成Base64格式
        padding = (6 - buffer_bits) // 2
        result.append('=' * padding)
    
    return ''.join(result)

这个方法本质上是用整数的位运算模拟了比特流的处理，比操作数组左移要高效得多，也更容易理解～

内容的提问来源于stack exchange，提问作者Mithrandir