bitset :: count（）的这个实现是如何工作的？

2018-06-03 18:12:29

这是MSVC 2010中std::bitset::count的实现：

size_t count() const
    {   // count number of set bits
    static char _Bitsperhex[] = "112122312232334";
    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

该函数通过与0xF（二进制1111）进行AND运算，一次从其处理的值中检索一个数字，查找该数字中设置的位数，然后求和它们。

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

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

这是在这里描述的基于查找表的方法稍微不同的实现：http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable。在链接处，他们使用一个由256个元素组成的表格并将32位字分成4个8位值。

链接地址: http://www.djcxy.com/p/12593.html

上一篇: How does this implementation of bitset::count() work?

下一篇: MSVC equivalent to