Питонический способ перебора битов целого числа

Ответ 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

Ответ 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. конвертирует в строку, я предполагаю, что это вредит его производительности. Различные попытки оптимизации помогают, но недостаточно Sven создает обратную сторону всех остальных, что может быть преимуществом, если вам это действительно нужно. Подход Дункана побеждает быстрее (едва)

Опять с 340282366920938463463374607431768211457 вместо 109:

Winston 44.5073108673
F.J. 74.7332041264
Sven 47.6416211128
Duncan 2.58612513542

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

Ответ 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]

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

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

Ответ 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]

Ответ 5

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

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

Ответ 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