Как работает эта реализация bitset :: count ()?
Вот реализация std::bitset::count с 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);
}
Может кто-нибудь объяснить мне, как это работает? в чем прикол _Bitsperhex?
Решение
_Bitsperhex содержит количество установленных битов в шестнадцатеричной цифре, проиндексированных этой цифрой.
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
Функция извлекает одну цифру за раз из значения, с которым она работает, путем ANDing с 0xF (двоичный код 1111), ищет количество установленных битов в этой цифре и суммирует их.
Другие решения
_Bitsperhex является целочисленным массивом из 16 элементов, который отображает число в [0..15] диапазон к числу 1 биты в двоичном представлении этого числа. Например, _Bitsperhex[3] равно 2, который является числом 1 биты в двоичном представлении 3,
В остальном все просто: каждое многобитное слово во внутреннем массиве _Array интерпретируется как последовательность 4-битных значений. Каждое 4-битное значение передается через _Bitsperhex таблица для подсчета битов.
Это немного другая реализация описанного здесь метода на основе таблицы поиска: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable. При ссылке они используют таблицу из 256 элементов и разбивают 32-битные слова на четыре 8-битных значения.