Enveloppe d'entiers de taille arbitraire efficace en Python

Question

La fonction struct.pack() permet de convertir des entiers de chaînes allant de 64 bits à des octets. Quel est le moyen le plus efficace d'emballer un nombre entier encore plus grand? Je préférerais ne pas ajouter de dépendance aux modules non standards comme PyCrypto (qui fournit num_to_bytes()).

Answer 1

Comme suggéré par S.Lott dans un commentaire, il suffit de convertir le nombre en une chaîne et d'emballer cette chaîne. Par exemple,

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

Answer 2

En supposant que l'affiche veut emballer un grand nombre entier comme une chaîne binaire, à savoir ne pas utiliser un octet de stockage par chiffre du numéro. Une façon de faire cela semble être:

import marshal 

a = 47L 
print marshal.dumps(a) 

Cette impression:

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

Je ne peux pas dire que je comprends comment interpréter ces bits, en ce moment ...

Answer 3

I prenez-le, vous voulez dire que vous voulez seulement utiliser autant d'octets que nécessaire pour représenter le nombre? par exemple. si le nombre est:

• 255 ou moins vous utiliseriez seulement 1 octet
• 65535 ou moins 2 octets
• 16777215 ou moins 3 octets
• etc etc

Sur la Psion PDA ils ont habituellement un certain schéma d'empaquetage dans lequel vous lisez le premier octet, détectez s'il a le bit le plus élevé et lisez un autre octet s'il l'a fait. De cette façon, vous continuerez à lire les octets jusqu'à ce que vous lisiez le nombre "complet". Ce système fonctionne assez bien si la plupart des numéros que vous traitez sont assez petits, car vous n'utiliserez normalement qu'un ou deux octets par numéro. L'alternative est d'avoir un (ou plusieurs) octets représentant le nombre total d'octets utilisés, mais à ce stade, il s'agit en fait d'une chaîne en Python de toute façon. c'est-à-dire qu'il s'agit d'une chaîne de 256 chiffres de base.

Answer 4

Voulez-vous dire quelque chose comme ceci:

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

qui retourne:

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

Je ne suis pas sûr de ce qu'il faut faire ... négatifs Je ne suis pas familier avec peu de twidling.

EDIT: Une autre solution (qui coûte environ 30% plus rapide par mes tests):

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

C'est un peu hacky, mais vous pouvez passer par la représentation de chaîne hexagonale, et il en binaire avec le codec 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 

Il casse un peu parce que le codec hexadécimal nécessite un nombre pair de chiffres, vous aurez donc besoin de pad pour cela, et vous aurez besoin de définir un indicateur pour gérer les nombres négatifs.Voici un pack générique/déballer:

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 

Avec tous les tripoter pour le rembourrage etc nécessaire, je ne suis pas sûr qu'il est bien mieux qu'une solution à la main bien.