How to locate the bit in bits string?
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:
>>> 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) could be used to locate it, this transform cost
>>> too much memory (99 only needs 2Bytes, while string '1100011' needs
>>> 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.
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
More information about the Python-list