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.

4
demandé sur Andrew Hubbs 2011-03-17 03:40:31

5 réponses

reversed_ = sum(1<<(numbits-1-i) for i in range(numbits) if original>>i&1)
7
répondu John La Rooy 2011-03-17 00:47:28

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]
8
répondu Dudi b 2017-05-23 11:51:44

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.

4
répondu Justin Peel 2011-03-17 00:50:35
Les tableaux d'indexation Numpy

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.

3
répondu dadaist 2016-02-20 12:52:38

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.

2
répondu dfan 2011-03-17 00:52:36