単一ビット/複数ビットの判定方法

投稿者: | 2017-04-02

禁手判定では四々、三々を判定するために「四が2つ以上あるか?」「見かけの三が2つ以上あるか?」をチェックします。REAL Coreではパターンの検索結果をビットで持つので「四/見かけの三が2つ以上あるか?」は「ビット列[math]b[/math]に1が2つ以上あるか?」を調べることに対応します。

「ビット列[math]b[/math]に1が2つ以上あるか?」を調べる一番愚直な方法はビット列[math]b[/math]中の1の数(PopCountと言います)を数えてその値が2以上かどうかを調べる方法です。PopCountもそれなりに高速に求めることができますが、REAL Coreではより高速な判定方法を実装しています。

PopCountが2以上かどうかさえわかれば良いので

  1. ビット列[math]b[/math]の1の数が0個
  2. ビット列[math]b[/math]の1の数が1個

のいずれでもなければ「ビット列[math]b[/math]に1が2つ以上ある」ことがわかります。「ビット列[math]b[/math]の1の数が0個」は

b == 0

で簡単に判定できます。

「ビット列[math]b[/math]の1の数が1個」かどうかを高速に判定する方法として[math]b\ne 0[/math]の時

!(b & (b-1))

で判定できることが知られています。

もし、[math]b[/math]の[math]n[/math]桁目のみに1が立つとすると[math](b-1)[/math]は[math]0[/math]〜[math]n-1[/math]桁目にのみ1が立つのでANDをとると0になります。逆に[math]b[/math]に1が2つ以上立っていると[math](b-1)[/math]の1の最上位は[math]b[/math]と同じなのでANDを取っても非ゼロになります。最後にNOTをとることで[math]b[/math]の1の数が1つの時のみtrueになる結果が得られます。

参考情報

スポンサーリンク

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください