最小位串集合与移位算法

Question

我正在寻找一种算法来解决,或者至少是以下问题的正确名称:

---

我有一组B位的位串.该算法应找到最小(定义为"具有最少位设置")位串S,以便:

对于所有的b在乙,存在一个移Ñ(在ℤ),使得(S << N) & b == b.

---

如果它有帮助,每个b适合机器字,和| B | 大约是几百个.

---

我认为我们可以假设(不失一般性)S的LSB 和每个b为1.

这看起来像是某种多序列对齐问题.

如果我们能够找到每个ñ _我每个b _我在乙(我 = 1 .. | 乙 |),它看起来像小号只是按位或在所有(b _我 >> ñ _我).

我的直觉是,第一步是除去每个b从乙存在用于其另一比特串Ç在乙有的移位中号,使得b & (c << M) == b.下一步是什么？

Answer 1

我的B的特定实例足够小，可以通过暴力破解，并使用一些技巧来修剪搜索。

已经定义了以下函数，

• snoob，返回具有相同位数设置的下一个最高数字（如 Hacker's Delight 图 2-1 中所定义（或最初为 HAKMEM 第 175 项））
• popcount, 返回其参数中 1 位的数量
• clz，返回其参数最高有效端的连续零的数量

我的解决方案的伪代码如下：

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

第一个循环右移每个b，因此其 LSB 为 1；这使得我们以后只能对 N 使用右移。

S上的循环从设置位的最小数字开始ones；循环停止条件不太正确，但对于我的目的来说它已经足够好了。

N上的循环从S和b的 LSB 对齐开始，然后转到S和b对齐的最高有效一位。

现在，我将这个问题悬而未决，看看是否有合适的非暴力解决方案出现，或者直到有人说这个问题是 NP 困难的。