64ビット整数のすべてのビットと32ビット整数を比較する

Question

小さなチェッカーソルバーを作成するという考えで遊んでいました。最初は、非常にコンパクトなチェッカーボードの表現を作ってから、ゲームツリーなどを作っていきます。

標準チェッカーボードは、8行、及び4官能列を（チェッカーだけ対角線移動することができる）を有しています。それは私たちに32ポジションを与えます！各位置は、情報の3ビット... kingビット、及びcolorビットを必要...ので00は10が王ブラック、11は赤色王であり、01は非キング赤ある、非キングブラックあります。これは私たちに働くいい数である64を与えます（長い整数の正確なサイズ）。

isOccupiedビット各チェッカーの位置は空でもよいし、上記の4つの状態のいずれかで満たされるので、各チェッカーにも1つの追加ビットが必要です。私は64州を64ビットintに、32州を32ビット整数に変換することにしました。

私たちはいくつかの背景を持っているので、私は次のような問題があります。「このボードには赤チェッカーがいくつあるの？それほど悪くはありません...私たちの64ビット整数はこのようなデータを保持しています：

king_color_king_color_king_colorだから011001は赤、黒、キング、赤を意味します。

色情報だけを取得するには、01010101 ... 01というビットマスクを使用できます。これは、0x5555555555555555の16進数です。それは王のビットをゼロにし、色のビットを残すだけです。マスクとのANDing後の011001の例では010001です。ビット（popcount、bitcount）を数えると、赤の数が得られます。

ああ、待って！これらの色は「使用中」でない場合があります。指定されたチェッカーが使用されているかどうかを調べるには、32ビットintをチェックする必要があります。だから、私たちは占有されている32の整数に対して011を持っていると言っています。つまり、上記の最初のチェッカー01（赤ではない王）...は実際には占有されていません。そこに別のチェッカーを移動する場合、2つのキングカラービットを更新する必要がある場合とそうでない場合があります。だから、

32bit = 011 
64bit = 011001 

赤が続く黒王に続いて3つのチェッカー位置...前の赤だったと空のチェッカーを、表す一緒にすべてを置きます。私たちは64ビットで010101マスク動作を行うたら我々が得る：

64bitWithMask = 010001 
32bit=011 

は単純に我々は... 2つの赤を持っているが、我々は実際には1アクティブを持っている...私は何をしたいことは、本質的で奇数ビットを取るされます64ビットの文字列と32ビット文字列の各ビットとの論理和...

1 AND 0, 0 AND 1, 1 AND 1は、赤チェッカーの数を表す001を返します。

または同等に、011 & 101 = 001を取得するために64bitWithMask簡単かつ32ビットとその後 64bitWithMaskOddBits = 101に変換します。

正式には、長さ2Xのビット列を取り出し、奇数ビットだけを取って長さXに減らす方法はありますか？私は非常にループ、ifsなどを避け、論理（と、またはxor、否定など）を使用することだけを試みています。

もちろん、私の32ビットと64ビットの文字列を使って適切なレッド数を得る別の方法がある場合は、もちろんです。 ありがとう！

EDIT：

私が提起した問題を解決するには、エレガント受け入れ答えに以下の解決が、私の実際のアプリケーションのためのよりよい解決策は私にたくさんの節約2 32への64ビット表現を分割することでしたさ私が必要とするものを抽出する操作の助けを借りてLukeGとTehtmiの両方に感謝します！私はビット操作のこの新しいテクニック「並列」にさらされてうれしいです。

Answer 1

数字から半角の数字に1つおきのビットを圧縮するのは、各ビットが異なる量だけシフトする必要があるため、ややこしいことです。しかし、個々のビットを個別に処理するよりも少ない操作しか必要としない巧妙な方法があります。 64ビットの場合は、この（擬似コード）のように見える：

x = x & 0x5555555555555555 
// or for the alternate bits: x = (x >> 1) & 0x5555555555555555 
x = (x | (x >> 1)) & 0x3333333333333333 
x = (x | (x >> 2)) & 0x0f0f0f0f0f0f0f0f 
x = (x | (x >> 4)) & 0x00ff00ff00ff00ff 
x = (x | (x >> 8)) & 0x0000ffff0000ffff 
x = (x | (x >> 16)) & 0x00000000ffffffff 

ここで（初期マスクの後に）32ビット数の各ステップでビットに何が起こっているかの実例は次のとおり

0a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p 
00ab00cd00ef00gh00ij00kl00mn00op 
0000abcd0000efgh0000ijkl0000mnop 
00000000abcdefgh00000000ijklmnop 
0000000000000000abcdefghijklmnop 

たとえば、ビットgは、右に9をシフトする必要があります。したがって、2の累乗の要素9 = 1 + 8を見てください。したがって、gは>> 1のステップと>> 8のステップにシフトされます。

この種のビットアルゴリズムは「並列」と記述されることがあります。あなたはこれをチェックアウトすることに興味がありますfamous list。これは、ここで起こっていることに非常に密接に関連しているインターリーブを含みます。

この種のコードの標準的な免責事項は、一般的には扱いにくいため、重大なプロジェクトで使用されるべきではない実際にはパフォーマンス上の問題です（そして、たとえそうであっても、コードで何が行われるべきかを明確にしてください）。パフォーマンスの問題がなく、依然としてビット操作を使用したい場合は、理解しやすく扱いやすいので、ループソリューションが依然として望ましいかもしれません。

Answer 2

ループを使用しないとこれを行う方法はありません。

編集：私はtehtmiによって間違っていることが判明しました。 Wile私はまだこの答えの終わりに提案された "代替ソリューション"は手元の問題を解決するより良い方法だと思う、tehtmiは非常に興味深い解決策を提示し、あなたがまだいなければ、スクロールアップしupvoteする必要があります。

私はこれにアプローチする2つの方法を見ています。あなたが達成したいものに近づく

最初のものは、次のとおりです。赤の位置の

uint32_t occupied; 
uint64_t data; 

uint32_t occupiedWithRed; 
for (auto i = 0; i < 32; ++i) { 
    occupiedWithRed |= (data >> i) & occupied & (1 << i); 
} 

カウントはoccupiedWithRedでセットされたビットの数になります。

簡単に（そしておそらくより速い）方法は次のとおりです。

uint32_t occupied; 
uint64_t data; 

auto count = 0; 
for (auto i = 0; i < 32; ++i) { 
    if ((data >> (2 * i)) & (occupied > i)) ++count; 
} 

それとも、完全に異なる何かをする：としては、あなたの3つの異なる32でデータを区切った場合、あなたの人生を容易にでき、コメントで指摘されました符号なし整数。赤と黒を区別するためのもの、自由と占有を区別するためのものと、王と王の区別のためのもの。あなたの仕事はこのようにかなり簡単になります。これはビット単位の問題であり、ハミングウェイトの計算になります。

Answer 3

32占有ビットと比較するために偶数ビットまたは奇数ビットを収集する代わりに、私はむしろ逆の方向に進み、それらを奇数位置のみに行くように64ビット整数に分配します。さらに、別の64ビット整数で偶数の位置にシフトします。

次に、奇数または偶数の占有整数を位置情報整数の偶数または奇数ビットと簡単に比較できます。