Li Wang wrote:
2009/4/29 Tim Chase <python.l...@tim.thechases.com>:
Li Wang wrote:
If I use an integer to represent bits:
[snip]
Hummm, I have tried this method too, the problem is its time
complexity. If the length of my bits is n, then the time complexity is
O(n). When I tried to implement this in practice, it did consume a lot
of time.
I'm not sure I follow here -- your original post said that you
have an integer. With an integer, my function is O(1) as you
request. It sounds like you're *not* representing your bits as
an integer. Either that, or it's a gargantuan number (say, more
than 64 bits? Maybe more than 1k bits?) that you want to
bit-slice. In that case, you need to know a bit more about the
storage structure. However, assuming it's a raw bit-stream, you
might be able to do something like this (untested, but should be
fairly close)
data = file('source.bin').read()
def get_bit(source, bit):
idx, bit = divmod(bit, 8)
byte = ord(source[len(source) - (1+idx)])
return (byte >> bit) & 1
print get_bit(data, 3141592) # the 3,141,592nd bit
you might have to tweak for endian'ness.
-tkc
--
http://mail.python.org/mailman/listinfo/python-list
