9

符号なしの M ビット整数 (M は 8、16、32、64 のいずれか) があり、その中にさまざまな 0 ビットが含まれているとします。

...111 000 11 00 1 0000 1 0 1 00000 111...

0 <= N <= M の数値 N を指定すると、サイズが <=N の整数の 0 のすべてのグループを埋めたいと思います。したがって、上記の整数に対して N=3 が与えられた場合、結果は次のようになります。

...111 111 11 11 1 0000 1 1 1 00000 111...

サイズが > 3 であるため、ゼロの 4 グループと 5 グループは反転されていないことに注意してください。

C/C++ で効率的な実装を作成するにはどうすればよいですか? 私ができる巧妙なちょっとしたいじりがあると思いますが、どこから始めればよいかわかりません。ビットパターンを伝播するために乗算が使用されているのを見たことがありますが、この種の可変長チェックでは使用されていません。ルックアップ テーブルも同じ理由で苦痛に思えます。適切に配置された 1 の減算は、一連のビットを反転させることができますが、何を減算するかを理解するのは難しいように見えます。

編集：明確にするために、 M はコンパイル時に固定されていますが、 N は実行時に変化する可能性があります。

4

4 に答える 4

10

次のようなことを試してください：

x = ~x;
for (i=0; i<N; i++) x&=x/2;
for (i=0; i<N; i++) x|=x*2;
x = ~x;

not 操作は、1 ではなく 0 が一番上に「シフトイン」するという事実を説明するためのものです。最上位のビットを手動で取り込むことで回避できます。&=との|=ステップも逆になります。

ところで、これが機能する場合は、これらのループを使用するのではなく、N ごとに展開されたバージョンを作成することをお勧めします。

于 2012-12-11T06:22:26.953 に答える
5 
x = ~x;
for (j = 1; j <= N/2; j *= 2) x &= (x >> j);
x &= (x >> (N - j + 1));
for (j = 1; j <= N/2; j *= 2) x |= (x << j);
x |= (x << (N - j + 1));
x = ~x;

R..によるソリューションと同じアイデアですが、少し最適化されています。

さらに最適化するには、2 番目のループを削除することができます。

t = ~x;
m = x & (t << 1);
for (j = 1; j <= N/2; j *= 2) t &= (t >> j);
t &= (t >> (N - j + 1));
t |= ((m - t) & ~m);
x = ~t;

ここでは、残りのループのみがビット グループをシフトします (前のバリアントとまったく同じ) が、2 番目のループの代わりに、単純なビット単位のトリックを使用して、N よりも長いグループを復元します。

例 (N = 4):

input string  110000100000011
inverted one  001111011111100
loop iter. 1  000111001111100
loop iter. 2  000001000011100
one more iter 000000000001100

各ビット グループの前に少なくとも 1 つのゼロ ビットがあるため、最初のループ反復は適切に機能します。その結果、各ビット グループの前に少なくとも 2 つのゼロ ビットがあります。そのため、2 回目のループ反復で一度に 2 ビットずつシフトすることができます。同じ理由で、3 番目のループ反復は一度に 4 ビットずつシフトする場合があります。ただし、この例では 2 ビットを超えるシフトは必要ありません。ループは既にビット グループを 3 ビット シフトしているので、それらをさらに N-3=1 ビットだけシフトする必要があります (これはループの後の次の行で行われます)。

小さい方のビット群はなくなりましたが、大きい方は一対のビットで表されます。残りのグループを再構築するには、2 番目のループを使用できます。

starting with 000000000001100
loop iter. 1  000000000011100
loop iter. 2  000000001111100
one more iter 000000011111100
result        111111100000011

または、2 番目のループの代わりに、ビット単位のトリックを使用することもできます。

m             010000100000000
t             000000000001100
m-t           010000011110100
(m-t) & ~m    000000011110100
t|((m-t)&~m)  000000011111100
result        111111100000011

m各グループの始まりを示します。m-tシフトアウトされたすべてのビットを復元します。次の操作で の未使用ビットがクリアされますm。復元されたビットとシフト ループの後に残っているビットを結合するには、もう 1 つの操作が必要です。

ベンチマーク結果 (AMD K8、GCC 4.6.3 -O2)、秒:

N one_loop two_loops unoptimized
1     3.9     4.2       3.3
2     4.6     6.2       5.2
3     4.6     6.2       7.1
4     5.6     7.9       8.9
5     5.6     7.9      11.3
6     5.6     7.9      13.3
15    6.7    10.0      46.6
于 2012-12-11T11:08:28.170 に答える
3

編集:この問題については、が比較的大きくR..ない限り、 の解決策の方が優れています(私のマシンでは、 のクロスオーバー ポイントは 周辺にありますが、考えられるすべての 32 ビット数値でテストしているため、意図した用途を表していない可能性があります)。だから私はその解決策に賛成しましたが、一言でs のスパンを反復処理する方法を示しているため (または小さな変更s を使用して)、他の目的に役立つ可能性があるため、ここに残しておきます。NM = 32N = 1801

範囲と前の 1 がマークされた例を次に示します。

111 000 11 00 1 0000 1 0 1 00000 111
  1 000  1 00        1 0

これらの範囲のそれぞれから「1」を引くとします: (実際の 1 ではなく、範囲に対して)

  0 111  0 11        0 1

そしてそれを元に戻します：

111 111 11 11 1 0000 1 1 1 00000 111

いいですね。したがって、1減算するすべての s を計算する必要があります。これは、0N 以下のサイズのすべての範囲の最後の位置になります。また、範囲のサイズを計算するには、前1のものも見つける必要があります。

したがって、基本的には、末尾のビットをすべての s またはすべての sに設定するように注意しながら、 lastと0last を交互に検索して、 s のすべてのスパンを見つける必要があります。範囲が大きすぎない場合は、最後の位置のビットを減算し、最後の 1 の位置に戻すことができます。これにより、スパン内のすべての s が s に変わります。あまり明確ではなかったので、コードを試してみましょう。01100101

最初に、次の小さな関数があります。

unsigned int last_one(unsigned int k) { return k & -k; }
unsigned int last_zero(unsigned int k) { return (k + 1) & ~k; }

効果があると確信できるまで試してみてください。どちらも単一の 1 ビットを返すか、何もない場合はゼロを返すことに注意してください。last_{one,zero}

次に、スパンはどれくらいですか？位置を見つける必要があるため、sを数えるのは少し0面倒です (それほど難しくはありませんが、不要です)。しかし、実際の数は気にしません。と比較する方法を知る必要があるだけですN。しかし、最後のもの (マーカー)に対する最後のもの(マーカー) の比率が最大 2 NNである場合、スパンのサイズは最大ビット数であることがわかります。10

それでは、すべてをまとめてみましょう。

unsigned long fill_in_runs(unsigned long val, int N) {
  unsigned long k = val;
  while (k) {
    unsigned long last_zero = (k + 1) & ~k;
    k -= last_zero - 1;
    if (k) {
      unsigned long last_one = k & -k;
      if ((last_one >> N) <= last_zero) 
        val += last_one - last_zero;
      k += last_one - 1;
    } else if (last_zero > (1UL << (M - N - 1)))
      val -= last_zero;
  }
  return val;
}
于 2012-12-11T06:36:27.327 に答える
1

以下のコードはあなたの要件に必要なことを行うことができると信じていますが、それでも最適化できるかどうかはあなた次第です...

#define BIT_GROUP   4

int main()
{
    uint32_t i, j, n;
    uint8_t bit_pos, zero_bit_pos, count;

    i = n = 0xaa05;

    printf("%x\n", i);

    while (n)
    {
        if (n & 1)
            printf("1");
        else
            printf("0");

        n >>= 1;
    }
    printf("\n");

    n = i;
    bit_pos = count = 0;
    while(n)
    {
        if(!(n & 1))
        {
            if(count <= BIT_GROUP)
            {
                zero_bit_pos = bit_pos;
                count++;
            }
            else
            {
                zero_bit_pos = 0;
                count = 0;
                j = 0;
            }
            if(count <= BIT_GROUP)
            {
                j = ((1 << count) - 1);
            }
        }
        else
        {
            j <<= ((zero_bit_pos + 1) - count);
            i |= j;
            j = 0;
            zero_bit_pos = 0;
            count = 0;
        }
        bit_pos++;
        n >>= 1;
    }

    n = i;
    while (n)
    {
        if (n & 1)
            printf("1");
        else
            printf("0");

        n >>= 1;
    }
    printf("\n");
    printf("%x\n", i);


    return 0;
}

それが役に立てば幸い！！！！！！

于 2012-12-11T09:40:54.370 に答える