Эффективная целочисленная упаковка произвольного размера в Python

Question

Функция struct.pack () позволяет преобразовывать целые числа длиной до 64 бит в байтовые строки. Какой самый эффективный способ сложить еще большее целое число? Я бы предпочел не добавлять зависимость от нестандартных модулей, таких как PyCrypto (который предоставляет num_to_bytes ()).

Answer 1

Вы имеете в виду что-то как это:

def num_to_bytes(num):
    bytes = []
    num = abs(num) # Because I am unsure about negatives...
    while num > 0:
        bytes.append(chr(num % 256))
        num >>= 8
    return ''.join(reversed(bytes))

def bytes_to_num(bytes):
    num = 0
    for byte in bytes:
        num <<= 8
        num += ord(byte)
    return num

for n in (1, 16, 256, 257, 1234567890987654321):
    print n,
    print num_to_bytes(n).encode('hex'),
    print bytes_to_num(num_to_bytes(n))

Что возвращает:

1 01 1
16 10 16
256 0100 256
257 0101 257
1234567890987654321 112210f4b16c1cb1 1234567890987654321

Я просто не уверен, что делать с негативами ... Я не очень хорошо разбираюсь в этом.

РЕДАКТИРОВАТЬ: Другое решение (по моим тестам работает примерно на 30% быстрее):

def num_to_bytes(num):
    num = hex(num)[2:].rstrip('L')
    if len(num) % 2:
        return ('0%s' % num).decode('hex')
    return num.decode('hex')

def bytes_to_num(bytes):
    return int(bytes.encode('hex'), 16)

Answer 2

Наткнулся на ту же проблему. Начиная с Python 3.2, вы можете использовать int.to_bytes:

>>> (2**100).to_bytes(16, byteorder='big')
b'\x00\x00\x00\x10\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'

Answer 3

Предполагая, что автор хочет упаковать большое целое число в виде двоичной строки, то есть не использовать один байт памяти на цифру в числе. Один из способов сделать это выглядит так:

import marshal

a = 47L
print marshal.dumps(a)

Это печатает:

'l\x01\x00\x00\x00/\x00'

Я не могу сказать, что я понимаю, как интерпретировать эти биты, прямо сейчас ...

Answer 4

Это немного странно, но вы можете перейти к представлению шестнадцатеричной строки и там к двоичному с шестнадцатеричным кодеком:

>>> a = 2**60
>>> a
1152921504606846976L
>>> hex(a)
'0x1000000000000000L'
>>> hex(a).rstrip("L")[2:].decode('hex')
'\x10\x00\x00\x00\x00\x00\x00\x00'       # 8bytes, as expected.

>>> int(_.encode('hex'), 16)
1152921504606846976L

Это немного ломается, потому что шестнадцатеричный кодек требует четного числа цифр, поэтому вам нужно будет дополнить его и установить флаг для обработки отрицательных чисел. Вот типичная упаковка / распаковка:

def pack(num):
    if num <0:
       num = (abs(num) << 1) | 1    # Hack - encode sign as lowest bit.
    else:
       num = num << 1
    hexval = hex(num).rstrip("L")[2:]
    if len(hexval)%2 ==1: hexval = '0' + hexval
    return hexval.decode('hex')

def unpack(s):
    val = int(s.encode('hex'), 16)
    sign = -1 if (val & 1) else 1
    return sign * (val>>1)


for i in [10,4534,23467, 93485093485, 2**50, 2**60-1, -1, -20, -2**60]:
    assert unpack(pack(i)) == i

Несмотря на то, что требуется все необходимое для прокладки и т. Д., Я не уверен, что это намного лучше, чем ручное решение.

Answer 5

Я так понимаю, вы имеете в виду, что хотите использовать столько байтов, сколько вам нужно для представления числа? например если номер:

• 255 или меньше, вы бы использовали только 1 байт
• 65535 или менее 2 байта
• 16777215 или менее 3 байта
• и т. Д.

На Psion PDA у них обычно была какая-то схема упаковки, в которой вы читаете первый байт, определяете, установлен ли у него старший бит, а затем читаете другой байт, если он есть. Таким образом, вы будете просто читать байты, пока не прочитаете «полный» номер. Эта система работает достаточно хорошо, если большинство чисел, с которыми вы имеете дело, достаточно малы, поскольку вы обычно используете один или два байта на число.

Альтернатива состоит в том, чтобы иметь один (или более) байтов, представляющих общее количество использованных байтов, но в любом случае это в любом случае строка в Python. то есть это строка из базовых 256 цифр.

Answer 6

Это обобщает предыдущий ответ Клаудио . Он пытается использовать оптимальную длину в байтах. Он также поддерживает целые числа без знака и со знаком.

def int_to_bytes(i: int, *, signed: bool = False) -> bytes:
    length = (i.bit_length() + 7 + signed) // 8
    return i.to_bytes(length, byteorder='big', signed=signed)

def bytes_to_int(b: bytes, *, signed: bool = False) -> int:
    return int.from_bytes(b, byteorder='big', signed=signed)

# Test unsigned:
for i in range(1025):
    assert i == bytes_to_int(int_to_bytes(i))

# Test signed:
for i in range(-1024, 1025):
    assert i == bytes_to_int(int_to_bytes(i, signed=True), signed=True)

Answer 7

Как предлагает С.Лотт в комментарии, просто преобразуйте число в строку и упакуйте эту строку. Например,

x = 2 ** 12345
struct.pack("40s", str(x))