Efektywne pakowanie liczb całkowitych o dowolnej wielkości w Pythonie

Question

Funkcja struct.pack() umożliwia konwertowanie liczb całkowitych do 64 bitów na ciągi bajtów. Jaki jest najbardziej efektywny sposób na spakowanie jeszcze większej liczby całkowitej? Wolałbym nie dodawać zależności od niestandardowych modułów, takich jak PyCrypto (która zapewnia num_to_bytes()).

Answer 1

Zgodnie z sugestią S.Lott w komentarzu, po prostu przekonwertuj liczbę na ciąg i spakuj ten ciąg. Na przykład,

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

Answer 2

Zakładając plakat chce pakować dużą liczbę całkowitą jako ciąg binarny, czyli nie używać jeden bajt pamięci za cyfrę w numerze. Jednym ze sposobów na osiągnięcie tego wydaje się być:

import marshal 

a = 47L 
print marshal.dumps(a) 

Drukuje:

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

Nie mogę powiedzieć, że rozumiem, jak interpretować te bity, teraz ...

Answer 3

I wziąć to masz na myśli, że chcesz tylko użyć tyle bajtów, ile potrzebujesz, aby reprezentować numer? na przykład jeśli liczba jest:

• 255 lub mniej byłoby użyć tylko 1 bajt
• 65535 lub mniej 2 bajty
• 16777215 lub mniej 3 bajty
• etc etc

Na Psion PDA zwykle mają trochę schematu pakowania, w którym czytasz pierwszy bajt, wykrywają, czy ma on najwyższy ustawiony bit, a następnie odczytuje inny bajt, jeśli ma. W ten sposób po prostu przeczytasz bajty, dopóki nie przeczytasz "pełnego" numeru. Ten system działa całkiem dobrze, jeśli większość liczb, z którymi masz do czynienia, jest dość mała, ponieważ normalnie używasz tylko jednego lub dwóch bajtów na liczbę.

Alternatywą jest mieć jeden (lub więcej) bajtów reprezentujących liczbę całkowitych bajtów używanych, ale w tym momencie to w zasadzie ciąg w Pythonie tak. tj. jest ciągiem 256 znaków bazowych.

Answer 4

Czy oznacza coś takiego:

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)) 

która zwraca:

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

ja po prostu nie wiem, co zrobić z negatywów ... Nie jestem aż tak obeznany z twidlingiem bitowym.

EDIT: Innym rozwiązaniem (które trwa około 30% szybszy od moich testów):

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 5

Jest to nieco hacky, ale można przejść przez reprezentację ciąg szesnastkowy, a tam do binarnych kodek hex:

>>> 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 

łamie trochę bo kodek hex wymaga parzystą liczbę cyfr, więc trzeba za to pad, i trzeba ustawić flagę obsłużyć liczb ujemnych.Oto generic pakietu/rozpakować:

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 

ze wszystkimi błahy dla dopełnienia itp wymagane, nie jestem pewien, że to o wiele lepiej niż ręcznie walcowane rozwiązanie chociaż.