Pythonic способ перебирать биты целого числа

Question

Давайте a=109 или 1101101 в двоичном формате. Как перебрать биты этого числа, например: [64, 32, 8, 4, 1]

Answer 1

Есть хитрость, заключающаяся в том, чтобы просто получить 1 из двоичного представления без необходимости перебирать все промежуточные 0:

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

Мой подход:

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

Не думаю, что для этого есть встроенная функция.

Мне также интересно, нет ли лучшего подхода к тому, что вы делаете. Есть хороший шанс, что вы действительно не хотите перебирать биты, подобные этой. Они могут быть намного лучше.

Из любопытства я проверил некоторые методы, опубликованные здесь, мои результаты:

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

F.J. Преобразование в строку, я предполагаю, что вредит его производительности. Различные попытки оптимизации помогают, но недостаточно, Свен производит противоположность всем остальным, что может быть преимуществом, если вам это действительно нужно. Подход Дункана выигрывает по скорости (едва)

Снова с 340282366920938463463374607431768211457 вместо 109:

Winston 44.5073108673
F.J. 74.7332041264
Sven 47.6416211128
Duncan 2.58612513542

Отлично, Дункан! Следует отметить, что это в значительной степени лучший вариант для метода Дункана, поэтому он не всегда будет иметь столь существенное преимущество.

Answer 3

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

Очевидно, что здесь порядок обратный, вы можете либо использовать это, либо изменить результат:

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

edit: Вот немного более длинная версия, которая должна быть более эффективной:

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

Answer 4

Python 2.7:

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

Пример:

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

Answer 5

ТАК не позволю мне поместить это как комментарий, но вот построчный пример того, как Дункан работает.Надеюсь, это проясняет, что происходит.

Давайте использовать десятичное число 109 в качестве примера :

# 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.

Answer 6

Пример однострочного решения:

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

Или:

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

Примечания:

• использовать диапазон в Python 3
• подумайте о проверке битового поля>> 0

Answer 7

Эффективность ответа FJ может быть значительно улучшена.

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

Мне нравятся один вкладыши:)

Я сделал быстрый timeit.Timer.timeit () против этого и @Duncan,Дункан все еще выигрывает, но не один лайнер по крайней мере в том же классе.

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