Inverser les bits de Python entier

Si vous êtes après plus de vitesse, vous pouvez utiliser la technique décrite dans http://leetcode.com/2011/08/reverse-bits.html

def reverse_mask(x):
    x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1)
    x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2)
    x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4)
    x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8)
    x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16)
    return x

def reverse_bit(num):
    result = 0
    while num:
        result = (result << 1) + (num & 1)
        num >>= 1
    return result

nous n'avons pas vraiment besoin de convertir l'entier en binaire, puisque les entiers sont en fait binaire en Python.

l'idée inverse est comme faire l'inversion dans l'espace des entiers.

def reverse_int(x):
    result = 0
    pos_x = abs(x)
    while pos_x:
        result = result * 10 + pos_x % 10
        pos_x /= 10
    return result if x >= 0 else (-1) * result

pour chaque boucle, le nombre original laisse tomber le bit le plus à droite(en binaire). Nous obtenons ce bit de droite et multiplions 2 ( <<1 ) dans la boucle suivante lorsque le nouveau bit est ajouté.

il n'y a pas besoin, et aucune façon, de"convertir un entier décimal en représentation binaire". Tous les entiers Python sont représentés en binaire; ils sont simplement convertis en décimal lorsque vous les Imprimez pour plus de commodité.

si vous voulez suivre cette solution au problème d'Inversion, vous n'avez qu'à trouver le numbits approprié . Vous pouvez soit le spécifier à la main, soit calculer le nombre de bits nécessaires pour représenter un entier n avec n.bit_length() (nouveau en Python 2.7 et 3.1).

Cependant, pour 65, cela vous donnerait 7, car il n'y a aucune raison pour que 65 nécessite plus de bits. (Vous pouvez arrondi au plus proche multiple de 8...)

vous pouvez tester le dernier bit d'un nombre en utilisant un décalage et un masque. Par exemple, le bit 6 de 65 est (65 >> 6) & 1 . Vous pouvez régler un peu de la même façon en déplaçant 1 à gauche du bon nombre de fois. Ces aperçus vous donnent le code comme ceci (qui inverse x dans un champ de 'N' bits).

def reverse(x, n):
    result = 0
    for i in xrange(n):
        if (x >> i) & 1: result |= 1 << (n - 1 - i)
    return result

print bin(reverse(65, 8))

une autre façon de le faire est de faire une boucle à travers les bits à la fois d'extrémité et d'échange l'un l'autre. J'ai appris ça dans EPI python book.

i = 0; j = 7
num = 230
print(bin(num))
while i<j:
    # Get the bits from both end iteratively
    if (x>>i)&1 != (x>>j)&1:
        # if the bits don't match swap them by creating a bit mask
        # and XOR it with the number 
        mask = (1<<i) | (1<<j)
        num ^= mask
    i += 1; j -= 1
print(bin(num))

la meilleure façon de faire est d'effectuer peu à peu le déplacement

def reverse_Bits(n, no_of_bits):
    result = 0
    for i in range(no_of_bits):
        result <<= 1
        result |= n & 1
        n >>= 1
    return result
# for example we reverse 12 i.e 1100 which is 4 bits long
print(reverse_Bits(12,4))