<<展開

1が立ってる最下位bitを見つけたい

Facebookシェア Twitterツイート LINEで送る Googleシェア このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
Up
0
Down

要約

概要

ビット列の中から1が立っている位置を高速に見つけるアルゴリズムについて紹介します.
ー 条件 ー
  • ビット列が入力
  • ハッシュしてシフト数を引き出すため、あらかじめテーブル作成が必要
ー 効果 ー
  • 高速にビット列の中から1が立っている最下位ビットが求まる

解  説

ビット列の中から1が立っている位置を高速に見つけるアルゴリズムについて紹介します. まず、下記に方法を示しました. 理解するには以下二つの知識が必要になります.
1が立ってる最下位bitを見つけたい

1.必要な知識

あるビット列で1が立っている最下位bitだけを残す方法があります. x&(-x)で得ることができます.
最下位の1が立つbitだけ残したい
De Bruijn列は、ある文字の集まりを使って作れる文字の組み合わせを全て一度だけ使い作られた文字列. ex) aとbを使って3文字の組み合わせを全て表示する文字列は、aaababbbaa.
De Bruijn列

2.方法

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
{
    int x = 0b0100101011000;
    ulong x_and_m_x = ( ulong ) ( x & -x );
    //x_and_m_x = 0b0000000001000;
    int i = ( int ) ( ( x_and_m_x * 0x03F566ED27179461UL ) >> 58 );
    //x_and_m_x * 0x03F566ED27179461ULは、0x03F566ED27179461ULを最下位bit桁分左Shiftしているのと同じ.
    // 0x03F566ED27179461ULは Da Buijn列. 0x03F566ED27179461UL = 0b 0000 0011 1111 0101 0110 0110 1110 1101 0010 0111 0001 0111 1001 0100 0110 0001.
    //上位6ビットはいくらシフトするかでそれぞれ別の値になる.(Da Buijn列の性質)
    //x_and_m_x * 0x03F566ED27179461UL = "0001 11"11 1010 1011 0011 0111 0110 1001 0011 1000 1011 1100 1010 0011 0000 1000。
    //(x_and_m_x * 0x03F566ED27179461UL)  >> 58 =
    //  000111 ←これが↓のtableのキーになる.
    return table[ i ];
}
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列.
知識: 最下位の1が立つbitだけ残したい
高速にビット列が与えられたときに1が立っているビットの中で最下位の1だけを残して他のbitを全て0にする方法についてまとめます.