Comment inverser les bits significatifs d'un entier en python?
Quelle est la meilleure façon d'inverser les bits significatifs d'un entier en python et d'en extraire le nombre entier résultant?
par exemple, j'ai les nombres 1,2,5,15 et je veux inverser les bits comme cela:
original reversed
1 - 0001 - 1000 - 8
2 - 0010 - 0100 - 4
5 - 0101 - 1010 - 10
15 - 1111 - 1111 - 15
étant donné que ces nombres sont des entiers de 32 bits, comment faire cela en python? La partie sur laquelle je ne suis pas sûr est comment déplacer des bits individuels en python et s'il y a quelque chose de drôle à utiliser un champ 32bit comme un entier par la suite.
PS ce n'est pas un devoir, j'essaie juste de programmer la solution à un puzzle logique.
5 réponses
reversed_ = sum(1<<(numbits-1-i) for i in range(numbits) if original>>i&1)
C'est un moyen rapide de le faire:
Je l'ai eu de ici
BitReverseTable256 = [0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF]
v = 32 # any int number will be reverse 32-bit value, 8 bits at time
c = BitReverseTable256[v & 0xff] << 24 |
BitReverseTable256[(v >> 8) & 0xff] << 16 |
BitReverseTable256[(v >> 16) & 0xff] << 8 |
BitReverseTable256[(v >> 24) & 0xff]
Si vous voulez vraiment 32 bits plutôt que 4, alors voici une fonction pour faire ce que vous voulez:
def revbits(x):
return int(bin(x)[2:].zfill(32)[::-1], 2)
en gros, je suis en train de convertir en binaire, en enlevant le " 0b " devant, en remplissant de zéros jusqu'à 32 caractères, en inversant, et en convertissant de nouveau en un entier.
il pourrait être plus rapide de faire le travail de bit réel comme dans la réponse de gnibbler.
fournissent une notation concise pour l'application de permutations d'inversion de bits.
import numpy as np
def bitrev_map(nbits):
"""create bit reversal mapping
>>> bitrev_map(3)
array([0, 4, 2, 6, 1, 5, 3, 7], dtype=uint16)
>>> import numpy as np
>>> np.arange(8)[bitrev_map(3)]
array([0, 4, 2, 6, 1, 5, 3, 7])
>>> (np.arange(8)[bitrev_map(3)])[bitrev_map(3)]
array([0, 1, 2, 3, 4, 5, 6, 7])
"""
assert isinstance(nbits, int) and nbits > 0, 'bit size must be positive integer'
dtype = np.uint32 if nbits > 16 else np.uint16
brmap = np.empty(2**nbits, dtype=dtype)
int_, ifmt, fmtstr = int, int.__format__, ("0%db" % nbits)
for i in range(2**nbits):
brmap[i] = int_(ifmt(i, fmtstr)[::-1], base=2)
return brmap
quand bit inversant de nombreux vecteurs on veut stocker la cartographie de toute façon.
l'implémentation inverse les représentations littérales binaires.
ce est le premier lien que j'ai trouvé sur Google pour "python bitwise" et il a un assez bon résumé de la façon de faire bit-twiddling en Python.
si vous ne vous souciez pas trop de la vitesse, la solution la plus simple est de passer par chaque bit-place du nombre original et, si elle est définie, définir le bit correspondant de votre valeur de retour.
def reversed( x, num_bits ):
answer = 0
for i in range( num_bits ): # for each bit number
if (x & (1 << i)): # if it matches that bit
answer |= (1 << (num_bits - 1 - i)) # set the "opposite" bit in answer
return answer
je suis sûr que vous pourriez le faire avec une compréhension, aussi. Si vous vraiment besoin de vitesse, vous auriez probablement faire 8 bits à la fois avec 256 valeurs précalculées table de recherche.