How does this implementation of bitset::count() work?
Here's the implementation of std::bitset::count with MSVC 2010:
size_t count() const
{ // count number of set bits
static char _Bitsperhex[] = " 112122312232334";
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);
}
Can someone explain to me how this is working? what's the trick with _Bitsperhex ?
_Bitsperhex contains the number of set bits in a hexadecimal digit, indexed by the digit.
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
The function retrieves one digit at a time from the value it's working with by ANDing with 0xF (binary 1111), looks up the number of set bits in that digit, and sums them.
_Bitsperhex is a 16 element integer array that maps a number in [0..15] range to the number of 1 bits in the binary representation of that number. For example, _Bitsperhex[3] is equal to 2 , which is the number of 1 bits in the binary representation of 3 .
The rest is easy: each multi-bit word in internal array _Array is interpreted as a sequence of 4-bit values. Each 4-bit value is fed through the above _Bitsperhex table to count the bits.
It is a slightly different implementation of the lookup table-based method described here: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable. At the link they use a table of 256 elements and split 32-bit words into four 8-bit values.
链接地址: http://www.djcxy.com/p/12594.html