How to locate the bit in bits string?

Li Wang li.wang.d at gmail.com
Tue Apr 28 17:24:02 CEST 2009


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
>
>
>
>
>



-- 
Li
------
Time is all we have
and you may find one day
you have less than you think



More information about the Python-list mailing list