Manera pitónica de iterar sobre los bits del número entero

Question

Vamos a a=109 o 1101101 en binario. ¿Cómo puedo iterar sobre bits de este número, por ejemplo: [64, 32, 8, 4, 1]

Answer 1

Hay un truco para conseguir justo de la 1 de la representación binaria sin tener que iterar sobre todo del 0 intervenir:

def bits(n): 
    while n: 
     b = n & (~n+1) 
     yield b 
     n ^= b 


>>> for b in bits(109): 
    print(b) 


1 
4 
8 
32 
64 

Answer 2

Mi enfoque:

def bits(number): 
    bit = 1 
    while number >= bit: 
     if number & bit: 
      yield bit 
     bit <<= 1 

No creo que hay una función incorporada para ello.

También me pregunto si no hay un mejor enfoque para lo que sea que esté haciendo. Hay muchas posibilidades de que realmente no desee iterar sobre los bits como este. Pueden ser una forma mucho mejor.

Por curiosidad me corrió un poco de tiempo en los métodos publicada aquí, mis resultados:

Winston 2.35238099098 
F.J. 6.21106815338 
F.J. (2) 5.21456193924 
Sven 2.90593099594 
Duncan 2.33568000793 
freegnu 4.67035484314 

F. J. convierte en una cadena, supongo que perjudica a su actuación. Los diversos intentos de optimización ayudan, pero no lo suficiente, Sven produce el revés de todos los demás, lo que podría ser una ventaja si realmente lo necesitabas. El enfoque de Duncan gana speedwise (a duras penas)

De nuevo con 340282366920938463463374607431768211457 en lugar de 109:

Winston 44.5073108673 
F.J. 74.7332041264 
Sven 47.6416211128 
Duncan 2.58612513542 

Niza, Duncan! Cabe señalar que este es el mejor caso para el método de Duncan, por lo que no siempre tendrá esta ventaja dramática.

Answer 3

Python 2.7:

def binary_decomposition(x): 
    p = 2 ** (int(x).bit_length() - 1) 
    while p: 
     if p & x: 
      yield p 
     p //= 2 

Ejemplo:

>>> list(binary_decomposition(109)) 
[64, 32, 8, 4, 1] 

Answer 4

>>> [2**i for i, v in enumerate(bin(109)[:1:-1]) if int(v)] 
[1, 4, 8, 32, 64] 

Obviamente, el orden se invierte aquí, se podía ya sea sólo tiene que utilizar este o revertir el resultado:

>>> [2**i for i, v in enumerate(bin(109)[:1:-1]) if int(v)][::-1] 
[64, 32, 8, 4, 1] 

edit: Aquí es una versión ligeramente más largo que debería ser más eficiente:

from itertools import takewhile, count 
[p for p in takewhile(lambda x: x <= 109, (2**i for i in count())) if p & 109] 

Answer 5

La eficiencia de la respuesta de FJ se puede mejorar de manera espectacular.

from itertools import count,takewhile 
[2**i for i in takewhile(lambda x:109>2**x,count()) if 109&2**i][::-1] 

me gusta trazadores de líneas uno :)

I hicieron un timeit.Timer.timeit rápida() en contra de este y @Duncan. Duncan aún gana pero no el delineador está al menos en la misma clase.

from timeit import Timer 
duncan="""\ 
def bits(n): 
while n: 
    b=n&(~n+1) 
    yield b 
    n^=b 
""" 
Duncan=Timer('list(bits(109))[::-1]',duncan) 
Duncan.timeit() 
4.3226630687713623 
freegnu=Timer('[2**i for i in takewhile(lambda x:109>2**x,count()) if 109&2**i][::-1]','from itertools import count,takewhile') 
freegnu.timeit() 
5.2898638248443604 

Answer 6

Ejemplo solución de una línea:

[1 << bit for bit in xrange(bitfield.bit_length()) if bitfield & (1 << bit)] 

O:

[bit for bit in (1 << n for n in xrange(bitfield.bit_length())) if bitfield & bit] 

Notas:

• uso gama en Python 3
• pensar acerca de la comprobación bitfie ld es> = 0

Answer 7

S.O. no me deja poner esto como un comentario, pero aquí hay un ejemplo línea por línea de cómo funciona la solución Duncan's. Espero que esto aclare lo que está pasando.

Usemos el número decimal 109 como un ejemplo:

# 109 is .............. 0110 1101 
# ~109 is -110 which is 1001 0010 NOTE: It's -110 instead of -109 because of 1's compliment 
# ~109+1 is -109....... 1001 0011 
# 109 AND ~109 is...... 0000 0001 = 1 <---- 1st value yielded by the generator 
# 109 XOR 1 is......... 0110 1100 = n = 108 

# 108.................. 0110 1100 
# ~108+1= -108......... 1001 0100 
# 108 AND -108......... 0000 0100 = 4 <---- 2nd value yielded by the generator 
# 108 XOR 4............ 0110 1000 = n = 104 

# 104.................. 0110 1000 
# ~104+1............... 1001 1000 
# 104 AND -104......... 0000 1000 = 8 <---- 3rd value yielded by the generator 
# 104 XOR 8............ 0110 0000 = n = 96 

# 96................... 0110 0000 
# ~96+1................ 1010 0000 
# 96 AND -96........... 0010 0000 = 32 <---- 4th value yielded by the generator 
# 96 XOR 32............ 0100 0000 = n = 64 

# 64................... 0100 0000 
# ~64+1................ 1100 0000 
# 64 AND -64........... 0100 0000 = 64 <---- 5th value yielded by the generator 
# 64 XOR 64............ 0000 0000 = n = 0; thus, the while loop terminates.