Python超大整数左移位的文件外存实现方法咨询

你当前的代码存在两个核心逻辑错误：

• 你写的bin_[:N-d] + bin_[d:]不符合左移位运算规则，左移d位的本质是比特串整体向高位移动d位、低位补d个0，不是截断前后拼接
• 循环里n >> 20取到的是去掉最低20位的剩余高位，不是最高20位，且每次写bin(n)[2:]会把剩余所有比特重复写入文件，属于无效冗余操作

可行实现思路 #

全程不要用二进制字符串存储比特，按固定块大小拆分整数做外存读写，内存中最多同时存2个块的数据，完全不会触发内存溢出：

• 选2^20比特（即128KB）作为单块大小，存储时按低位块在前、高位块在后的顺序写入文件，避免每次运算重写全量数据
• 左移运算拆为两部分处理：跨块的整段偏移 + 块内移位+进位传递，全程顺序读写文件即可，不需要加载完整整数
• 你卡壳的「不加载全量内容删除前N个比特」不需要单独实现：处理完运算后从文件末尾（最高位块）往前扫描，全0的高位块直接截断丢弃即可，碰到第一个非0块时，再把块内前导0比特截掉就完成了前导位删除，全程内存只需要存单块数据。

注意：左移操作本身不需要删除前导比特，只有右移、高位截断场景才需要做前导位清理，不要做多余操作。

修正后的参考代码 #

import os
# 单块大小：2^20比特 = 128KB，和你设定的阈值一致
BLOCK_BITS = 1 << 20
BLOCK_BYTE = BLOCK_BITS // 8
BLOCK_MASK = (1 << BLOCK_BITS) - 1

def __lshift(n, d, tmp_file="bin.tmp"):
    total_bit_len = n.bit_length()
    # 小整数直接内存计算
    if total_bit_len + d <= BLOCK_BITS:
        return n << d

    # 大整数按块拆分写入临时文件，低位块在前
    with open(tmp_file, "wb") as f:
        remain = n
        while remain:
            cur_low_block = remain & BLOCK_MASK
            f.write(cur_low_block.to_bytes(BLOCK_BYTE, byteorder="little", signed=False))
            remain >>= BLOCK_BITS

    # 处理外存移位
    block_offset = d // BLOCK_BITS
    in_block_shift = d % BLOCK_BITS
    carry = 0

    with open(tmp_file, "rb+") as f:
        # 1. 处理跨块整段偏移：文件头补block_offset个全0块，原有块整体后移
        file_size = os.path.getsize(tmp_file)
        f.seek(0, 2)
        # 先给偏移和最后可能的进位块预留空间
        f.write(b"\x00" * (block_offset * BLOCK_BYTE + BLOCK_BYTE))
        # 从后往前搬移原有块，避免未读内容被覆盖
        for pos in range(file_size, 0, -BLOCK_BYTE):
            f.seek(pos - BLOCK_BYTE)
            cur_block = int.from_bytes(f.read(BLOCK_BYTE), byteorder="little", signed=False)
            f.seek(pos + block_offset * BLOCK_BYTE - BLOCK_BYTE)
            f.write(cur_block.to_bytes(BLOCK_BYTE, byteorder="little", signed=False))
        # 开头补全0偏移块
        f.seek(0)
        f.write(b"\x00" * (block_offset * BLOCK_BYTE))

        # 2. 逐块处理块内移位和进位
        f.seek(0)
        while True:
            block_data = f.read(BLOCK_BYTE)
            if not block_data:
                break
            cur_block = int.from_bytes(block_data, byteorder="little", signed=False)
            new_block_val = (cur_block << in_block_shift) + carry
            carry = new_block_val >> BLOCK_BITS
            new_block = new_block_val & BLOCK_MASK
            # 写回处理后的块
            f.seek(-BLOCK_BYTE, 1)
            f.write(new_block.to_bytes(BLOCK_BYTE, byteorder="little", signed=False))
        # 最后剩余进位追加为新的高位块
        if carry:
            f.write(carry.to_bytes(BLOCK_BYTE, byteorder="little", signed=False))

        # 3. 清理高位全0块（即你需要的删除前导多余比特逻辑）
        file_size = os.path.getsize(tmp_file)
        for pos in range(file_size - BLOCK_BYTE, -1, -BLOCK_BYTE):
            f.seek(pos)
            cur_block = int.from_bytes(f.read(BLOCK_BYTE), byteorder="little", signed=False)
            if cur_block != 0:
                f.truncate(pos + BLOCK_BYTE)
                break
        else:
            # 移位后结果为0直接返回
            return 0

    # 超大数结果保留在外存文件即可，后续运算直接按块读写，不需要加载全量到内存
    # 如果需要转回整数，可按块从高到低读取拼接
    return tmp_file

额外优化提示 #

• 不要用二进制字符串存储比特，直接存字节块的存储效率、运算速度比字符串高8倍以上，还省去了字符串和整数的转换开销
• 后续实现其他位运算、四则运算都可以复用这个固定块的外存存储结构，所有运算都可以做到单块内存占用完成，不需要加载全量大数

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