这个bitset :: count()的实现如何工作?

这是使用MSVC 2010实现std::bitset::count

 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 >= 4) _Val += _Bitsperhex[_Wordval & 0xF]; return (_Val); } 

有人可以向我解释这是如何工作的吗? _Bitsperhex的诀窍是_Bitsperhex

_Bitsperhex包含hex数字中的设置位数,由数字索引。

 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 ABCDEF 

该函数通过与0xF(二进制1111)进行AND运算,从它所使用的值一次检索一个数字,查找该数字中的设置位数,并对它们求和。

_Bitsperhex是一个16元素的整数数组,它将[0..15]范围内的数字映射到该数字的二进制表示中的1位数。 例如, _Bitsperhex[3]等于2 ,这是3的二进制表示中的1位数。

其余的很简单:内部数组_Array每个多位字_Array被解释为一个4位值序列。 每个4位值通过上面的_Bitsperhex表进行计数以计算这些位。

它是这里描述的基于查找表的方法的略微不同的实现: http : //graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable 。 在链接处,它们使用256个元素的表,并将32位字拆分为4个8位值。