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
--
http://mail.python.org/mailman/listinfo/python-list
