How to locate the bit in bits string?

[Tim Chase]

Li Wang wrote:
> 2009/4/29 Tim Chase <python.list at 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