Voltear bits en python

Question

Dado un número entero n, quiero alternar todos los bits en la representación binaria de ese número en el rango decir inferior a superior. Para hacer esto hago lo siguiente [bit_string es una cadena que contiene 1 y 0 y es una representación binaria de n]

for i in range(lower,upper+1): 
    n ^= (1 << len(bit_string)-1-i) #Toggle the ith bit 

Entonces, también necesito para determinar que da un rango, digamos inferior a superior, cómo muchos bits de código son set.My de hacerlo es la siguiente:

number_of_ones = 0 
for i in range(lower,upper+1): 
    if(n & (1 << len(bit_string)-1-i)): #Check the ith bit 
     number_of_ones+=1 

Pero, si n es muy grande, creo que estos algoritmos serían lento. ¿Hay alguna manera de hacer que estas dos operaciones sean más rápidas/más eficientes?

Usted

Answer 1

Para el "volteo" Gracias, se puede hacer un solo mapa de bits (por otros en todas las posiciones de interés) y un único o-exclusiva:

n ^= ((1<<upper)-1)&~((1<<lower)-1) 

para el bit-cuenta, una vez que se aísla (n & máscara) para la misma "máscara" que el RHS anterior, cortándola en por ejemplo Cortes de 8 bits y buscar los conteos de 8 bits en una tabla de búsqueda (solo un simple list o array.array para prepararse de antemano) es el enfoque más rápido.

gmpy tiene algunas operaciones útiles y rápidas de manipulación de bits y conteo, esp. más rápido que las ofertas nativas de Python si se trata de cadenas de bits muy largas (más que una palabra de una máquina, por lo que en Python serían long instancias).

Answer 2

No sé Python, así que estoy pensando en esto desde un punto mathsy agorithmy puro de vista ...

Se me ocurre que para la primera parte de un método más eficiente podría ser la construcción de una máscara de los bits que quiere cambiar primero como un entero. Para facilitar la vida, asumiré que estás contando tus límites inferior y superior del bit menos significativo que es 0 y el más significativo es 31 (o lo que sea apropiado para la longitud de un int en tu caso).

Si desea que los bits n a m (m> n) se inviertan, entonces la representación binaria del número 2^(m + 1) -2^n tendrá estos bits establecidos. Luego haga un XOR y realice todos los intercambios de una vez. La computadora debe ser capaz de hacer esto de una vez, probablemente en lugar de un intercambio por bit.

En cuanto al conteo, no estoy seguro. Hay formas de contar la cantidad de bits configurados en un número. No estoy seguro si obtiene una ganancia en eficiencia para usar la máscara de bits anterior con un AND a 0 fuera de todos los bits que no le importa contar y luego usar esos algoritmos o si es mejor que los modifique para que funcionen para usted . Sin embargo, no sé cómo funcionan fuera de mi cabeza. :)

Answer 3

def bitflip(n,range): 
    bitfliplen = range[1]-range[0] 
    return n^((2**bitfliplen-1) << (range[0])) 

de reproducción:

>>> a = 47727124L 
>>> b = bitflip(a,(5,10)) 
>>> print "a: {0:b}\nb: {1:b}".format(a,b) 
a: 10110110000100001000010100 
b: 10110110000100000111110100 
>>> 

Answer 4

Para el recuento de bits, una vez que haya enmascarado fuera del rango que interesa, ver la rutina bitCount() en el python BitManipulation wiki page que implementa el esquema de Brian Kernighan:

def bitCount(int_type): 
    count = 0 
    while(int_type): 
     int_type &= int_type - 1 
     count += 1 
    return(count)