5

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

我有一组B位串。该算法应该找到一个最小的（定义为“设置最少的位”）位串S，使得：

对于B中的所有b，存在一个移位N（在ℤ</a> 中）使得.(S << N) & b == b

如果有帮助，每个b都适合一个机器字，并且 | 乙| 是几百的数量级。

我认为我们可以假设（不失一般性）S和每个b的 LSB为 1。

在我看来，这就像某种多序列比对问题。

如果我们可以为B中的每个b i找到每个N i ( i = 1 .. | B |)，那么看起来S只是所有 ( b i >> N i ) 的按位或。

我的直觉是，第一步是从B中删除每个b ，其中在B中存在另一个位串c和一些移位M使得. 下一步是什么？b & (c << M) == b

4

1 回答 1

0

我的特定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 难的。

于 2016-04-17T06:42:32.297 回答