How to locate the bit in bits string?

[David Smith]

Li Wang wrote:
> 2009/4/29 Tim Chase <python.list at tim.thechases.com>:
>> Li Wang wrote:
>>> Hi:
>>>
>>> If I use an integer to represent bits:
>>> e.g. 99 represents '1100011'
>>>
>>> How can I locate, say the second bit of 99(i.e. '1')?
>>>
>>> Although bin(99)[4] could be used to locate it, this transform cost
>>> too much memory (99 only needs 2Bytes, while string '1100011' needs
>>> 7Bytes).
>>>
>>> Anyone knows how to locate  the second bit without using bin() function?
>> You mean
>>
>>  def get_bit(number, bit):
>>    return (number >> bit) & 1
>>
>> ?
>>
> 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.
> 
> So do you know how could I locate the bit in O(1) time? Transform it
> into a string is a method, but takes too much space (when I try to
> process a 2M file, it used more than 100M memory.....).
> 
> Thank you very much.
> 
>> -tkc
>>
>>

So... I can only conclude you are looking for bit x in the entirety of a
file.  First you'll have to figure out what byte to look at w/ a little
integer division, then read to that point and test for the specific bit
-- I'm thinking a bitwise and operation with a bit mask.  Should be
really fast.


--David