How to locate the bit in bits string?

[Tim Chase]

>>  data = file('source.bin').read()
>>  def get_bit(source, bit):
>>    idx, bit = divmod(bit, 8)
>>    byte = ord(source[len(source) - (1+idx)])
>>    return (byte >> bit) & 1
>
> My understanding is: when doing this step, every bit in the byte will
> be shifted bit-long. If it is get_bit(data, 100), and the source.bin
> has 200bits in it. this single step (i.e. return (byte >> bit) & 1)
> will take 200 + 199 + 198 + ... + 101 times bit shifting operation.
> That's my understanding of the this function.


The function extracts the byte that contains the bit of interest, 
and then extracts the corresponding bit from that byte.  More 
verbosely:

   idx, bit = divmod(bit, 8)
   # idx is now the Nth byte from the end we want
   # bit is now 0-7 for the bit inside the corresponding byte

   offset = len(source) - (1+idx)
   # convert the left-hand idx to a right-hand idx

   byte = ord(source[offset]))
   # we now have the byte containing the bit we want

   # my original O(1) bit-extract
   return (byte >> bit) & 1

it only shifts once because it can precisely target the exact 
byte without having to visit the other bytes.  Trust me...it's 
O(1) for extracting a single bit (unless indexed access to "data" 
is not O(1), but that would assume something other than a string 
or list data-type...like a data-stream or generator).

-tkc