我正在寻找一种算法来解决,或者至少是以下问题的正确名称:
我有一组B位的位串.该算法应找到最小(定义为"具有最少位设置")位串S,以便:
对于所有的b在乙,存在一个移Ñ(在ℤ),使得
(S << N) & b == b.
如果它有帮助,每个b适合机器字,和| B | 大约是几百个.
我认为我们可以假设(不失一般性)S的LSB 和每个b为1.
这看起来像是某种多序列对齐问题.
如果我们能够找到每个ñ 我每个b 我在乙(我 = 1 .. | 乙 |),它看起来像小号只是按位或在所有(b 我 >> ñ 我).
我的直觉是,第一步是除去每个b从乙存在用于其另一比特串Ç在乙有的移位中号,使得b & (c << M) == b …