7

たぶん、私が考えているメモリマネージャーを高速化するのに役立つ次の問題で私を助けることができます (解決策が存在するかどうかはわかりません-解決策は見つかりませんでした)。

32 ビットのレジスタがあり、n 個の連続したセット ビットがあるかどうかを調べる必要があります。ある場合、それらのオフセットは何ですか。例えば、レジ​​スターが次の値を保持している場合:

3、4、5、6、28

私が持っているアトミック操作はすべて、通常のビット単位の操作 (&、|、~、…) であり、最下位ビット オフセット (上記のレジスタの 3) も見つけます。アルゴリズム (存在すると仮定) – アトミック操作は 5 回までにする必要があります。

4

4 に答える 4

3

それを行うアルゴリズムがある場合、最悪の場合の複雑さは少なくともO(m-n)です。ここmで、 はレジスタ内のビット数であり、nは探している連続したセット ビットの数です。すべてのビットが設定されている場合、アルゴリズムは正確にアイテムを出力する必要があるため、これは簡単にわかりますm-n。そのため、複雑さはこれ以上低くなりません。

編集

ここに同様の問題に対するエレガントな解決策があります整数のビットをループし、ルビーで longes1シーケンスの長さを見つけます。

n探している実行の長さが事前にわかっている場合、このアルゴリズムはnステップのみを必要とします。オフセットは、さらに約 5 つのステップで、アルゴリズムの最後の前のステップの末尾のゼロの数から復元できます。これは非常に効率的ではありませんが、おそらくループスルー ソリューションよりも優れています。特に小さなn.

編集2

nが事前にわかっている場合、必要な一連のシフトを把握できます。たとえば、7 ビットの実行を探している場合は、次のようにする必要があります。

x &= x >> 1
x &= x >> 3
x &= x >> 1
x &= x >> 1

ポイントは、@ harold が示唆するように、 が偶数の場合はn/2ビットを右にシフトし、奇数のn場合は 1 だけ右にシフトし、それに応じて更新することです (いずれか)。これらの値をその場で見積もるのはコストがかかりますが、事前に計算しておけばかなり効率的です。nnn = n - 1 or n = n / 2

編集3

さらに良いことに、 と の間である限り、どのシフトを行ってもn、正確な手順が必要になります。以下のコメントを参照してください。ceil(log(2,n))floor(n/2)2^floor(log(2,n-1))

于 2012-08-21T11:22:36.110 に答える
1

可能なすべてのバイト値（0〜255）について、最初のビット数、最後のビット数、バイト内の連続する最長ビット数、およびこのシーケンスのオフセットを計算します。たとえば、の場合、0x11011101最初に2ビット、最後に1ビットがあり、その中に3つの連続したビットのシーケンスがあります。

この値を4つの配列、たとえば、、、、に格納startしendます。longestlongest_offset

次に、32ビットの数値を4バイトの配列と見なし、次のようにこれらのバイトを反復処理します。

int search_bit_sequence(uint32 num, int desired) {
  unsigned char *bytes = (unsigned char *)#
  int i, acu;
  for (acu = i = 0; i < 4; i++) {
    int byte = bytes[i];
    acu += start[byte];
    if (acu >= desired)
      return (i * 8 - (acu - start[byte]));

    if (longest[byte] >= desired)
      return ( i * 8 + longest_offset[byte]);

    if (longest[byte] < 8)
      acu = end[byte];
  }
  return -1; /* not found */
}

更新：CPUのエンディアンにより、ループの方向を変更する必要がある場合があることに注意してください。

于 2012-08-21T11:49:27.860 に答える
1

Qnan によって投稿されたリンクは、一般的なケースに対するエレガントなソリューションを示しています。

m の特定の値については、さらに最適化することができます。

たとえば、m == 4 の場合、次のように実行できます。

x &= (x >> 1);
x &= (x >> 2);
// at this point, the first bit set in x indicates a 4 bit set sequence.

m == 6 の場合:

x &= (x >> 1);
x &= (x >> 1);
x &= (x >> 3);

結局、これは素因数分解 m に帰着します。

アップデート

また、 の値が大きい場合は、考えられるすべての位置でビット シーケンスをチェックする方が実際にはコストがかからないことにも注意してください。

たとえば、m = 23 の場合、パターンは 0 ～ 9 の位置からのみ開始できます。

于 2012-08-21T12:25:29.523 に答える
0

この質問と回答を確認して、次のアイデアを思いつきました。

int i = n-1;
uint32_t y = x;
while(y && i--) {
    y = y & (y << 1);
};

連続するセット ビットyがある場合、上記の操作の後は非ゼロになります。n次に行うことは、そこに設定されている最も重要でない値を見つけることです。次のコードは、最下位ビットを除くすべての設定ビットを取り除きます。

z = y - (y & (y-1));

ビットセットが 1 つしかないので、ビットの位置を見つける必要があります。32 ケースの switch ステートメントを使用できます。

static inline int get_set_position(const uint32_t z) {
    switch(z) {
        case 0x1:
            return 0;
        case 0x2:
            return 1;
        ....
        .... // upto (1<<31) total 32 times.
    }
    return -1;
}

最終的に結果を得るには、 を減らす必要がありますn-1。したがって、全体の手順は次のとおりです。

static inline int get_set_n_position(const uint32_t x, const uint8_t n) {
    if(!n) return -1;
    int i = n-1;
    uint32_t y = x;
    while(y && i--) {
        y = y & (y << 1);
    };
    if(!y) return -1;
    uint32_t z = y - (y & (y-1));
    if(!z) return -1;
    int pos = get_set_position(z);
    if(pos < 0) return -1;
    assert(pos >= (n-1));
    return pos - (n-1);
}

現在、ビッグエンディアンが懸念されています。ビッグエンディアンの get_set_position() を変更して機能させるだけでよいと思います(連続したセットビットの定義がエンディアンネスに基づいて変更されると仮定します)。

gcc が提供する builtin_ctzl を使用するテスト済みのコードを共有させてください。

OPP_INLINE int get_set_n_position(BITSTRING_TYPE x, const uint8_t n) {
    if(!n || n > BIT_PER_STRING) return -1;
    int i = n-1;
    while(x && i--) {
        x = x & (x << 1);
    };
    if(!x) return -1;
    int pos = __builtin_ctzl(x);
    return pos - (n-1);
}

32 は定数であるため (@Qnan が気づいたように)、コードは O(1) 時間で動作します。ここでも、レジスタのサイズが異なる場合、O(n) で機能します。

注: コメントと単体テストのおかげで、バグを修正しました。

于 2016-06-19T01:04:45.860 に答える