A bitwise common prefix algorithm in Python
Is my algorithm slow because it has problems?


Yes. The fundamental problem is that it always processes every character of the input.

There are some obvious improvements which don't address this fundamental problem:


Since the common prefix can't be more than min_len, truncate both strings to min_len before encoding them.
bin returns a string, so str(bin(...)) is overkill.
bin(int(a[::-1].encode('hex'), 16) ^ int(b[::-1].encode('hex'), 16)) is also overkill: what you care about is the position of the lowest set bit of int(a[::-1].encode('hex'), 16) ^ int(b[::-1].encode('hex'), 16). You can extract the lowest set bit directly from the integer as

differences = int(a[::-1].encode('hex'), 16) ^ int(b[::-1].encode('hex'), 16)
least_significant_difference = differences ^ (differences - 1)


(That actually gives a binary number which is all 1s from the lowest set bit to the least significant bit).

Then you can either convert to string and find the length, or take the logarithm base 2.


But the fundamental problem is still there: the fastest code is the code which isn't executed, and when the prefix is very short then a simple loop from the start which compares characters is hard to beat. If you really have to beat it, I think you're probably looking at writing some C which coerces a pointer to (16-bit?) characters into a pointer to 64-bit integers and uses that to compare a block of characters at a time. Beware endianness.