要计算一个整数对应的二进制数有多少位是 1，常用的方法是使用位移：

        #include <climits>  // for CHAR_BIT
        #include <cstddef>  // for size_t

        const std::size_t LONG_BIT = sizeof(long) * CHAR_BIT;

        int nlbits_on(unsigned long n)
        {
            int cnt = 0;
            for (std::size_t i = 0; i != LONG_BIT; ++i)
            {
                cnt += n & 1;
                n >>= 1;
            }
   
            return cnt;
        }

这里，我要介绍的是另外一种方法。请看以下二进制数：

        01110011

这个数一共有 5 个 1。有没有看出什么苗头？没错，将这个数的每一位相加正好是 5。由此可得，算一个字节里 1 的个数的方法如下：

        int nbbits_on(unsigned char n)
        {   // 假设 char 是 8 位的
            n = ((n & 0xAA) >> 1) + (n & 0x55);
            n = ((n & 0xCC) >> 2) + (n & 0x33);
            n = ((n & 0xF0) >> 4) + (n & 0x0F);

            return n;
        }

这个函数第一次将奇数位与偶数位相加。因为每对奇偶位相加的和不会超过“两位”，所以赋值回 n 后，n 的每“两位”保存着前面奇偶位相加的和。然后，再以“两位”为单位进行奇偶相加，结果每“四位”保存着前面相加的和。以此类推，最终算出一个字节里 1 的个数。

本文版权归 蚂蚁的 C/C++ 标准编程 以及 作者 Antigloss 共同所有，转载请注明原作者和出处。谢谢。