参考书籍： 《数据结构（C++语言版）》作者：邓俊辉
内容： 统计二进制展开为1的位数
知识点： 位运算

问题

对于任意非负整数，统计其二进制展开中数位1的总数。

解答

比较直接的想法是从低位到高位遍历二进制展开的每一个数位，遇到1则计数器加1，遇到0则计数器不变。于是得到以下算法。

第一种实现

c++
int countOnes(unsigned int n){
    /*
    统计n的二进制展开式中1的位数
    把每次n与1按位与的结果加到统计结果上，然后右移一位，直到等于0
    复杂度为O(logn)，正比于位数
    */

    int count = 0;
    while(n){
        count += (n & 1);
        n >>= 1;
    }
    return count;
}

以上算法可以继续改进，使其复杂度最差不差于第一种实现。

第二种实现

c++
int countOnes1(unsigned int n){
    /*
    改良版本
    时间复杂度不超过countOnes()，正比于1的位数
    实现原理
    一个二进制数10010000，将其-1，得到10001111.可以发现，-1之后最低位的1左边部分不变，右边部分全变为1，自身变为0
    故可基于此设计出如下算法
    */

    int count = 0;
    while(n){
        count++;
        n = (n & (n-1));
    }
    return count;
}

该算法仍为对数复杂度，实际上是伪对数复杂度，若以输入所占的实际位数来衡量，则为线性复杂度。但是，利用一些位运算的技巧，可以使其复杂度降为 $O(\log{\log{n}})$ ，若记输入规模为 $r=\log{n}$ 位，则复杂度为 $O(\log{r})$ 。

第三种实现

c++
#define POW(c) (1 << c)
#define MASK(c) (((unsigned long) -1) / (POW(POW(c)) + 1)) //这里用了一些数学技巧，我觉得太难想到了，这里只是留个印象，若不理解，直接像下面这样定义也行
// MASK(0) = 55555555(h) = 01010101010101010101010101010101(b)
// MASK(1) = 33333333(h) = 00110011001100110011001100110011(b)
// MASK(2) = 0f0f0f0f(h) = 00001111000011110000111100001111(b)
// MASK(3) = 00ff00ff(h) = 00000000111111110000000011111111(b)
// MASK(4) = 0000ffff(h) = 00000000000000001111111111111111(b)

#define ROUND(n,c) ((n & MASK(c)) + ((n >> POW(c)) & MASK(c)))
// 记n0 = ROUND(n,0), n1 = ROUND(n0,1)
// 想要看懂这个运算在干什么，最关键的就是看懂ROUND(n,0)的意义
// 假设n为八位二进制数 00101101 ，ROUND(n,0)的行为是数出每相邻两位的1的数量（这里不是任意相邻的两位，而是00 10 11 01这种相邻，我们称每对数字为“一块”，这里一共有4块）
// 具体是如何做到的？此时MASK(0)是 01010101 ，因为周期性，我们考察任意一块（即n的一对数字）的行为，比如第三块 11
// 11与01按位与，得到01，然后11右移一位得到01与01按位与，得到01。这里的行为实际上就是在把这一块里的每一位都与1按位与，相加得到的就是这一块里位是1的数量
// 如此 n0 = ROUND(n,0) = 00011001，每对数字的值就是n的每对数字的1的个数
// 再进行ROUND(n0,1)，把相邻两对的值加起来，n1 = ROUND(n0,1) = 00010011，此时每对数字为4个，它们的值表示n的前四位后四位分别有多少个1
// 最后进行ROUND(n1,2)，得到00000100，这个值就是n的八位中1的个数
// 理解了以上，下面的函数行为就好理解了

int countOnes2(unsigned long n){
    /*
    究极改良版本，时间复杂度为O(logW)，W为实际参与运算的位宽，w为O(logn)级别，则算法时间复杂度为O(loglogn)
    使用了一些位运算技巧，该技巧在csapp的位运算实验中也有使用
    */

    n = ROUND(n,0);
    n = ROUND(n,1);
    n = ROUND(n,2);
    n = ROUND(n,3);
    n = ROUND(n,4);

    return n;

}

总结

这是第一篇开始记录学习过程的blog，希望我能坚持，go！