How to locate the bit in bits string?

casevh casevh at gmail.com
Wed Apr 29 04:52:00 CEST 2009


On Apr 28, 5:39 pm, Li Wang <li.wan... at gmail.com> wrote:
> 2009/4/29 Tim Chase <python.l... at tim.thechases.com>:
>
> >> I want to concatenate two bits string together: say we have '1001' and
> >> '111' which are represented in integer. I want to concatenate them to
> >> '1001111' (also in integer form), my method is:
> >> ('1001' << 3) | 111
> >> which is very time consuming.
>
> > You omit some key details -- namely how do you know that "1001" is 4 bits
> > and not "00001001" (8-bits)?  If it's a string (as your current code shows),
> > you can determine the length.  However, if they are actually ints, your code
> > should work fine & be O(1).
>
> Actually, what I have is a list of integer numbers [3,55,99,44], and
> by using Huffman coding or fixed length coding, I will know how the
> bits-length for each number. When I try to concatenate them (say
> 10,000 items in the list) all together, the speed is going down
> quickly (because of the shifting operations of python long).
>
>
>
> > This can be abstracted if you need:
>
> >  def combine_bits(int_a, int_b, bit_len_b):
> >    return (int_a << bit_len_b) | int_b
>
> >  a = 0x09
> >  b = 0x07
> >  print combine_bits(a, b, 3)
>
> > However, if you're using gargantuan ints (as discussed before), it's a lot
> > messier.  You'd have to clarify the storage structure (a byte string?  a
> > python long?)
>
> I am using a single python long to store all the items in the list
> (say, 10,000 items), so the work does become messier...

Using GMPY (http://code.google.com/p/gmpy/) may offer a performance
improvement. When shifting multi-thousand bit numbers, GMPY is several
times faster than Python longs. GMPY also support functions to scan
for 0 or 1 bits.

>
> > -tkc
>
> > PS:  You may want to CC the mailing list so that others get a crack at
> > answering your questions...I've been adding it back in, but you've been
> > replying just to me.
>
> Sorry, this is the first time I am using mail-list....and always
> forgot "reply to all"
>
> Thank you very much:D
>
>
>
> --
> 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