5

std::bitset::countMSVC 2010での実装は次のとおりです。

size_t count() const
    {   // count number of set bits
    static char _Bitsperhex[] = "\0\1\1\2\1\2\2\3\1\2\2\3\2\3\3\4";
    size_t _Val = 0;
    for (int _Wpos = _Words; 0 <= _Wpos; --_Wpos)
        for (_Ty _Wordval = _Array[_Wpos]; _Wordval != 0; _Wordval >>= 4)
            _Val += _Bitsperhex[_Wordval & 0xF];
    return (_Val);
    }

誰かがこれがどのように機能しているのか説明できますか? トリックは_Bitsperhex何ですか？

4

2 に答える 2

9

_Bitsperhexセットされたビットの数を 16 進数で含み、数字でインデックス付けされます。

digit: 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
value: 0    1    1    2    1    2    2    3    1    2    2    3    2    3    3    4
index: 0    1    2    3    4    5    6    7    8    9    A    B    C    D    E    F

この関数は、0xF (2 進数の 1111) と AND 演算することによって、処理している値から一度に 1 桁を取得し、その桁に設定されているビット数を調べて、それらを合計します。

于 2012-09-07T19:19:33.693 に答える
4

_Bitsperhex[0..15]範囲内の数値をその数値1のバイナリ表現のビット数にマップする 16 要素の整数配列です。たとえば、_Bitsperhex[3]は に等しく2、これは1のバイナリ表現のビット数です3。

あとは簡単です。内部配列の各マルチビット ワードは_Array、4 ビット値のシーケンスとして解釈されます。各 4 ビット値は、上記の_Bitsperhexテーブルを介して供給され、ビットをカウントします。

これは、http: //graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTableで説明されているルックアップ テーブル ベースの方法のわずかに異なる実装です。リンクでは、256 要素のテーブルを使用し、32 ビット ワードを 4 つの 8 ビット値に分割します。

于 2012-09-07T19:19:58.983 に答える