-
@ThothChildren
- 2018.10.18
- PV 294
1が立ってる最下位bitを見つけたい
ー 概要 ー
ビット列の中から1が立っている位置を高速に見つけるアルゴリズムについて紹介します.
この章を学ぶ前に必要な知識
条件
- ビット列が入力
- ハッシュしてシフト数を引き出すため、あらかじめテーブル作成が必要
効果
- 高速にビット列の中から1が立っている最下位ビットが求まる
解 説
ビット列の中から1が立っている位置を高速に見つけるアルゴリズムについて紹介します.
まず、下記に方法を示しました.
理解するには以下二つの知識が必要になります. | 1が立ってる最下位bitを見つけたい | ||
1.必要な知識 | |||
あるビット列で1が立っている最下位bitだけを残す方法があります.
x&(-x)で得ることができます. | 最下位の1が立つbitだけ残したい | ||
De Bruijn列は、ある文字の集まりを使って作れる文字の組み合わせを全て一度だけ使い作られた文字列.
ex) aとbを使って3文字の組み合わせを全て表示する文字列は、aaababbbaa. | De Bruijn列 | ||
2.方法 | |||
C++
| 1が立ってる最下位bitを見つける方法 | ||
以下に実現する方法（コード）を示した.
コメントも含めているので参照願います.
0. ハッシュをキーに引き出せるテーブルの作成が必要.
0x03F...を6ビットずつ切り出して"table[6bitのキー] = 何番目"を記録していく.
1. まず1が立っている最下位bitだけ残す.(知識リンク参照)
2. x_and_m_xに1の値を入れて、それをあらかじめ作ってある0x03F....の値と掛け合わせる.
x_and_m_xは特定の桁のみが1になっているので、これは桁数分シフトするのと同じ処理になる.
3. x_and_m_x * 0x03F...を行うと0x03Fが左シフトすることになるが、このように行なった結果、得られた数値の上位6bitで何ビットしたかがtableからわかる.
("table[6bitのキー] = 何番目"をtableに保存しているため)
4. 上位6bitを得るため、全体を58bit右シフト.
5. 得られた値をtableに入れて、いくらシフトしたか求める. | 1が立ってる最下位bitを見つける方法 | ||
| 処理の概要 |
この章を学んで新たに学べる
Comments
Reasons
知識: De Bruijn列
De Bruijn列(ドゥブリュエイン列)はある文字または数字の集まりから指定長さの組み合わせを考える時に、それらの組み合わせを必ず一つ含む列."a,b"を使った3文字の列を考えると、"aaa","aab","aba","baa","bbb","bba","bab","abb"なので"aaababbbaa"がDe Bruijn列.
