14

マスクとビット演算子を使用して、指定された数のビット数（またはブール値のarraで真の要素数）を確認し、すべてのビットがオンになっているかどうかを確認する方法を知っています。数値が任意の長さであると仮定すると、アルゴリズムはO（n）時間で実行されます。ここで、nは数値のビット数です。漸近的に優れたアルゴリズムはありますか？それは不可能だと思いますが、どうすれば正式に証明できますか？

4

7 に答える 7

23

Bit Twiddling Hacksには、次のようないくつかの方法があります。

ビットセットを数える、ブライアン・カーニハンのやり方

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

Brian Kernighanの方法は、設定されたビットと同じ数の反復を実行します。したがって、上位ビットのみが設定された32ビットワードがある場合、ループを1回だけ通過します。

実行中のアルゴリズムの例：

128 == 10000000 2、1ビットセット

128 & 127 ==   0    10000000 & 01111111 == 00000000

177 == 10110001 2、4ビットセット

177 & 176 == 176    10110001 & 10110000 == 10110000
176 & 175 == 160    10110000 & 10101111 == 10100000
160 & 159 == 128    10100000 & 10011111 == 10000000
128 & 127 ==   0    10000000 & 01111111 == 00000000

255 == 11111111 2、8ビットセット

255 & 254 == 254    11111111 & 11111110 == 11111110
254 & 253 == 252    11111110 & 11111101 == 11111100
252 & 251 == 248    11111100 & 11111011 == 11111000
248 & 247 == 240    11111000 & 11110111 == 11110000
240 & 239 == 224    11110000 & 11101111 == 11100000
224 & 223 == 192    11100000 & 11011111 == 11000000
192 & 191 == 128    11000000 & 10111111 == 10000000
128 & 127 ==   0    10000000 & 01111111 == 00000000

アルゴリズムの複雑さに関する言語に依存しない質問に関しては、O（ n）よりもうまくいくことはできません。ここで、 nはビット数です。どのアルゴリズムも、数値のすべてのビットを調べる必要があります。

これについて注意が必要なのは、nの定義に注意を払わず、nを「ビットシフト/マスキング命令の数」などにする場合です。nがビット数の場合、単純なビットマスク（&）でさえすでにO（n）演算です。

それで、これはO（ n）ビットテストよりもうまく行うことができますか？いいえ。O（ n
） 未満の追加/シフト/マスク操作で実行できますか？はい。

于 2012-12-11T15:47:18.957 に答える
7

私はいつもこれを使います：

int
count_bits(uint32_t v)
{
        v = v - ((v >> 1) & 0x55555555);
        v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
        return ((v + (v >> 4) & 0xf0f0f0f) * 0x1010101) >> 24;
}

整数のサイズを知っている必要があります。

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

于 2012-12-11T15:51:34.777 に答える
4

1ビットをカウントするBrianKerninghanのアルゴリズム。

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

これと他のビットをいじるハックをここで読んでください：ビットをいじるハック。

于 2012-12-11T15:49:32.373 に答える
3

この計算を行う最も速い方法は、blレジスタにバイト値が含まれているテーブル配列edx[bl]を使用することです。数値が1バイトの場合、答えは1つの命令です。

 mov eax, [edx:bl]

数値に多くのバイトが含まれている場合（たとえば、ebpが指す配列）、バイトをループします（ここで、ecxは数値を含む配列のバイト数です）。

    sub ecx, 1
    mov eax, 0
 DoNextByte:
    mov bl, [ebp:ecx]
    add eax, [edx:bl]
    test ecx, ecx
    jz Done:
    sub ecx, 1
    jmp DoNextByte:
 Done:
    ; answer is in eax

これは、これを行うための絶対的に最速の方法であり、どの数学計算よりも高速です。Artのソリューションのシフト命令はCPUに非常にコストがかかることに注意してください。

Kernighanのソリューションの問題は、アセンブリで手動でコーディングした場合でも、私のアルゴリズムよりも遅いということです。Cでコンパイルされた場合、おそらく多くのメモリアクセスが生成され、必要なクロックサイクル数を超えても速度が低下します。

バイトからカウントへのマッピングがこの命令のすぐ隣にインライン化されている場合、データテーブル全体がCPUキャッシュにあるため、非常に高速であることに注意してください。この場合、Cプログラムは近づきません（20倍以上遅いと考えてください）。

于 2012-12-11T20:19:24.063 に答える
1

また、各バイトの#bitsを保持するルックアップテーブルを使用して、数値をバイトに分割し、ルックアップ値を合計することもできます。

それでもO（ビット数）になりますが、係数は小さくなります。

于 2012-12-11T19:12:23.317 に答える
1

あなたが探している形式のタイプは「敵対的な証拠」だと思います。

O（n）よりも高速に実行されるアルゴリズムAがあるとします。次に、nが十分に大きい場合、Aはビットiを調べてはなりません。次に、Aは正しくないはずだと主張します。「敵対者」は、ビットiの値が反対であることを除いて同一である2つの文字列s1とs2をAに与えます。アルゴリズムAはs1とs2に同じ値を返すため、攻撃者はAを「だまして」間違った答えを出しました。したがって、正しいアルゴリズムはありません。o（n）時間で実行されているAは存在しません。

于 2013-01-22T06:30:06.770 に答える
0

さて、ここでは順序統計、漸近表記、「ビッグO」について混乱が生じているようです。

ブライアン・カーニハンのアルゴリズムが操作の数の点で優れていることは正しいです。ただし、漸近的に優れているというのは正しくありません。

これは、big-Oの定義からわかります。

定義上、 nが十分に大きくなるとf（n）≤kg（n）となる関数g（n）が存在する場合、関数はO（f（n））であることを思い出してください。

ここで、 wをワードに設定されたビット数として定義しましょう。さらに、上記で観察されたように、単一ワードの実行時間は、設定されたビット数の関数であることに注意してください。その関数をc（w）と呼びます。単語の幅が固定されていることはわかっています。これをwwと呼びます。明らかにどの単語でも、0≤c （w） ≤wwであり、もちろん、最悪の場合はc（w） = c（ww）です。したがって、このアルゴリズムの実行時間は、最悪の場合、nc（ww）です。

したがって、nの場合、実行時間は≤nc（ww）です。つまり、n≤nc （ww）であるため、定義上、このアルゴリズムの実行時間は漸近的な最悪の場合のO（n）になります。

于 2013-01-03T20:56:42.633 に答える