5

解決するアルゴリズム、または少なくとも次の問題の適切な名前を探しています。

ビット文字列のセットBがあります。アルゴリズムは、次のような最小の (「ビット セットが最も少ない」と定義される) ビット文字列Sを見つける必要があります。

Bのすべてのb に対して、となるシフトN ( ℤ</a> 内) が存在します。(S << N) & b == b

それが役立つ場合、各bは機械語に収まります。ビ| 数百のオーダーです。

Sと各bの LSB は 1 であると (一般性を失うことなく) 仮定できると思います。

これは、ある種の複数の配列アラインメントの問題のように見えます。

B ( i = 1 .. | B |)の各b iに対して各N iを見つけることができれば、 Sはすべてのビットごとの論理和 ( b i >> N i ) のように見えます。

私の直感では、最初のステップは、Bに別のビット文字列cが存在し、そのようなシフトMが存在するBからすべてのbを削除することです。次は何ですか？b & (c << M) == b

4

1 に答える 1

0

Bの私の特定のインスタンスは、検索を絞り込むためのいくつかのトリックを使用して、力ずくで従うのに十分なほど小さいものでした。

以下の関数が既に定義されている場合、

  • snoob、同じ数のビットが設定された次の最大数を返します (Hacker's Delight 図 2-1 (または元々は HAKMEM item 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の最上位 1 ビットに揃えます。

今のところ、適切な非ブルート フォース ソリューションが登場するかどうか、または問題が NP 困難であると誰かが言うまで、未解決のままにしておきます。

于 2016-04-17T06:42:32.297 に答える