How to locate the bit in bits string?
David Smith
dns4 at cornell.edu
Tue Apr 28 21:22:22 CEST 2009
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
More information about the Python-list
mailing list