Minimal combination of a bit string set with a shift algorithm

Question

I am looking for an algorithm to solve, or at least the correct name for the following problem:

---

I have a set of B bit strings. The algorithm should find the minimum (defined as "with the minimum set of bits") bitstring S , which:

For all b in B, there is a shift N (in ℤ ) such that (S << N) & b == b .

---

If this helps, each b is inserted into the machine word, and | B | is about a couple of hundred.

---

I think we can assume (without loss of generality) that LSB S and each b is 1.

It looks like some kind of multiple-alignment problem.

If we find every N _i for every b _i in B (i = 1 .. | B |), it looks like S is only bit or all (b _i > N _i ).

My intuition is the first step - to remove each b from B for which there is another bit string c in B and some shift M such that b & (c << M) == b . What's next?

Answer 1

My particular instance of B was small enough to be brute force, with a few tricks to crop the search.

With functions already defined

• snoob , returns the next highest number with the same number of bits set (as defined in Hacker Delight, Figure 2-1 (or originally, HAKMEM clause 175))
• popcount , returns a 1-bit number in its argument
• clz , returns the number of consecutive zeros at the most significant end of its argument

The pseudocode for my solution is as follows:

 min_ones = max popcount(b) for b in B max_ones = popcount(~0) for i = 0 .. |B|-1: while !(B[i] & 1): B[i] >>= 1 found_ones = false for ones = min_ones .. max_ones: if found_ones: break for S = (1 << ones)-1; clz(S) > 0; S = snoob(S): if !(S & 1): continue for b in B: found = false for N = 0 .. clz(b) - clz(S): if (S >> N) & b == b: found = true break if !found: break if found: print(S) found_ones = true 

The first cycle shifts to the right each b, so its least significant bit is 1; this allows us to use only right shifts for N later.

The loop over S begins with the smallest number with the ones bits set; the loop stop condition is not entirely correct, but it works well enough for my purposes.

The cycle over N begins with the alignment of LSB S and b, and then proceeds to the most significant single-digit values ​​of S and b.

---

I am currently leaving the question as unsolved to see if the correct solution appears without brute force or until someone says the problem is NP-hard.