Pythonic way to iterate over bits of integer


Question


Let's a=109 or 1101101 in binary. How do I iterate over bits of this number, eg: [64, 32, 8, 4, 1]


Answer 1:


There's a trick for just getting the 1's out of the binary representation without having to iterate over all the intervening 0's:

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:


My approach:

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

I don't think there is a builtin function for it.

I also wonder if there isn't a better approach to whatever you are doing. There's a good chance you don't really want to iterate over the bits like this. They may be a much better way.

Out of curiosity I ran some timing on the methods posted here, my results:

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

F.J. converts to a string, I'm guessing that hurts his performance. The various optimisation attempts help, but not enough Sven produces the reverse of everybody else, which might be an advantage if you really needed that. Duncan's approach wins speedwise (just barely)

Again with 340282366920938463463374607431768211457 instead of 109:

Winston 44.5073108673
F.J. 74.7332041264
Sven 47.6416211128
Duncan 2.58612513542

Nice, Duncan! It should be noted that this is pretty much the best case for Duncan's method, so it won't always have this dramatic an advantage.




Answer 3:


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

Obviously the order is reversed here, you could either just use this or reverse the result:

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

edit: Here is a slightly longer version that should be more efficient:

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

Example:

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



Answer 5:


S.O. won't let me put this as a comment, but here's a line-by-line example of how Duncan's solution works. Hopefully this clarifies what's happening.

Let's use the decimal number 109 as an example:

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


The efficiency of F.J.'s answer can be dramatically improved.

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

I like one liners :)

I did a quick timeit.Timer.timeit() against this and @Duncan. Duncan still wins but not the one liner is at least in the same class.

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 7:


Example one-line solution:

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

Or:

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

Notes:

  • use range in Python 3
  • think about checking bitfield is >= 0


来源:https://stackoverflow.com/questions/8898807/pythonic-way-to-iterate-over-bits-of-integer


码神部落- 版权声明 1、本主题所有言论和图片纯属会员个人意见,与码神部落立场无关。
2、本站所有主题由该帖子作者发表,该帖子作者屌丝范儿码神部落享有帖子相关版权。
3、码神部落管理员和版主有权不事先通知发贴者而删除本文。
4、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者屌丝范儿码神部落的同意。
5、帖子作者须承担一切因本文发表而直接或间接导致的民事或刑事法律责任。
6、本帖部分内容转载自其它媒体,但并不代表本站赞同其观点和对其真实性负责。
7、如本帖侵犯到任何版权问题,请立即告知本站,本站将及时予与删除并致以最深的歉意。

最新回复 (0)
    • 码神部落
      2
        立即登录 立即注册 GitHub登录
返回
发新帖
作者最近主题: