Find the longest prefix of bit arrays

Question

I'm trying to find a fast algorithm that search the longest prefix of multiple bit arrays. In my application, those bit arrays can be infinitely long and of variable length. For example, if I have those bit arrays:

0b1011001
0b1001101
0b1001010
0b1010100

The longest prefix would be 10. I'm currently ORing and NANDing the bit arrays to find their common 0s and 1s and XORing the results together.

OR
0b1011111

NAND
0b0111111

XOR
0b1100000

Is there a any faster solution?

Answer 1

On your approach

It scales well (linear) on the number of bit-arrays.

It does not scale very well on the size of the bit-arrays, ideally it should scale based on the length of the common prefix, instead of the sizes of the bit-arrays.

At a low level

Bit-Operations on individual bytes/words from a bit array should be much faster than walking along the bits one at a time. (Not sure how much low level control Python can give you, though).

First Suggestion

If this were a low-level language like C, I would solve this in a way similar to you, but with a couple of ideas from the other answers.

In my example, I will assume that the computer is a 64-bit machine.

I start by (OR NAND XOR) just the first 64-bits of each bit-array, (These are basic operations on a 64-bit machine, and complexity is just O( # of arrays ) ).

Then quickly find the position of the first set bit in the result, (most computers have some fast method of this built in or at least in optimized assembly code, for C, If there is a set bit, return that value.

Otherwise, repeat on the next 64-127 bits of each bit-arrays.

(You will need to deal somehow with bit-arrays of different lengths, probably by finding the minimum length bit-array of the bunch, and then using that as the max.)

The benefit of this approach is that it is linear in number of bit-arrays, and is linear is length of the common-prefix.

Second Suggestion

If there is a large number of bit-arrays, you can get a speed-up by using parallelism.

First you can run the OR at the same time as the NAND.

With more ingenuity, you could apply the following:

If I have 4 bit-arrays A,B,C,D

Instead of (((A OR B) OR C) OR D)

I could do (A OR B) OR (C OR D).

In both cases, the same number of OR are done.

But the second approach can be parallelized effectively (and actually doing it the second way may be faster on a single-core machine, since oftentimes the CPU will actually have more than one ALU anyway.)

Writing the logic out is a little trickier, since you can't use a single for-loop with a single temporary variable holding the result of the ORs.

You could imagine storing the sub-results in an array with length one half of the number of bit-arrays. Store the subresult of A OR B in array[0] and C OR D in array[1], then do array[0] OR array[1]. (and you could store that result in a new array of half the length, or overwrite values in your array to save space and memory allocations).

Partition the work into large enough chunks to keep the whole computer busy without introducing too much overhead.

With enough Processors you could approach a complexity of the log of the number of bit-arrays instead of linear. But in practice, getting a 5-times speed-up on a 6-core machine would probably be pretty good.