5

下面是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？

4

2 回答 2

9

_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

该函数通过与 0xF（二进制 1111）进行与运算，一次从它正在使用的值中检索一个数字，查找该数字中设置的位数，并将它们相加。

于 2012-09-07T19:19:33.693 回答
4

_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 位值。

于 2012-09-07T19:19:58.983 回答