这个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位值。