# 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[] = "\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); }

Can someone explain to me how this is working? what's the trick with _Bitsperhex?

## Answers

_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.