求32位无符号数的二进制形式中1的个数，这是个经典的题目。求解这个题目，我们常规的做法就是将此二进制数右移31次，每次移位后判断最低位的那个是否为1，如果是1，那么计数加1。
那么还有没有更优的解法来减少移位和运算次数呢？
在1972年MIT人工智能实验室发布的一本备忘录中，提到了一个非常有趣的算法来解决这个问题，下面我们先来看一下这个算法是怎么做的？

unsigned int count(unsigned int n)
{
    unsigned int temp= n - ((n>>1)&033333333333) - ((n>>2)&011111111111)
    return ((temp+(temp>>3))&030707070707) %63;
}

刚刚看到上面的这个一脸懵逼，这是怎么来的？
其实就是分治法。

1. 一个自然数的多项式表示。

只要是一个自然数不会导致32位无符号数溢出，那么这个自然数就可以用以2为底的多项式表示。
p(n)₂ = a_n2ⁿ+a_n-12^n-1+a_n-22^n-2+...+a₂2²+a₁2¹+a₀2⁰
a_i取值[0,2)。根据计算机二进制表示，sum{a_i}就是1的个数。
那么如果以4为底呢？
p(n)₄ = a_n4ⁿ+a_n-14^n-1+a_n-24^n-2+...+a₂4²+a₁4¹+a₀4⁰
a_i取值范围[0,4)。根据计算机二进制表示，相当于把其每两位分割成一组，单独将每一组数取出，其值就是a_i，比如说假设一个8位的二进制数(01101011)₂，
p(n)₄ =1*4³+2*4²+2*4¹+3*4⁰
这样我们就将这个二进制以每份2位进行分割，我们只需要知道每一个系数的数字对应的二进制1的个数，然后累加即可。
以此类推，
p(n)_2^x=a_n(2^x)ⁿ+a_n-1(2^x)^n-1+a_n-2(2^x)^n-2+...+a₂(2^x)²+a₁(2^x)¹+a₀(2^x)⁰
此式就表示将二进制数以x位为一组进行分割，下面我们只需要知道每个系数对应的二进制1的个数，累加即可。
我们完成了分割。
那么我们应该怎样计算每个系数对应的二进制个数呢？
假设以3位一组分割，
对于其中一个系数a_i，我们只需要向右移动两次，每次与(001)₂,将结果累加。
a_i=a_i&(001)₂+a_i>1&(001)₂+a_i>2&(001)₂
对于32位无符号整数。以3位为一组分割
temp=p(n)_2³&010101010101+p(n)_2³>1&010101010101+p(n)_2³>2&010101010101式子中的常数为八进制数
那么这个temp所表示的数也可以表示为3位一组分割的多项式形式，并且temp的系数a_i就是p(n)_2³中对应第i项系数二进制形式1的个数。
我们只需要将temp 求的∑₀ⁿa_i
也就是说我们现在需要利用某种手段消掉每一项中底的幂次方。
怎么办？巧了，还真有这样的公式

2. n^N%(n−1)=1

对于任意一个自然数n，其N次方始终可以用n-1取模，结果为1

证明：
1.假设n^(k-1)% (n-1) = 1成立
2.那么n^k% (n-1)=[(n-1)*n^(k-1)+n^(k-1)]%(n-1)=0+n^k−1%(n−1) = n^k−1%(n−1) = 1
依然成立
3.又有 n^(1-1)% (n-1) = 1
顾n^N%(n−1)=1结论成立。

3. 多项式求系数和

下面我们回到多项式消去底，对系数求和的问题上来。
p(n)_N=a_nNⁿ+a_n-1N^n-1+a_n-2N^n-2+...+a₂N²+a₁N¹+a₀N⁰
下面用到的是(a+b)%c = (a%c+b%c)%c
p(n)_N%(N-1) = [a_nNⁿ%(N-1)+a_n-1N^n-1%(N-1)+a_n-2N^n-2%(N-1)+...+a₂N²%(N-1)+a₁N¹%(N-1)+a₀N⁰%(N-1) ]%(N-1)
=(a_n+a_n-1+a_n-2+...+a₂+a₁+a₀)%(N-1)
如果能保证∑₀ⁿa_i < N-1
那么p(n)_N%(N-1) = a_n+a_n-1+a_n-2+...+a₂+a₁+a₀
由本文章节1中说得出的结论temp变量的多项式中，系数和是二进制数1的个数，那么这个系数和一定<=32
也就是说N-1>32,N>33
N是一个以2的幂次方，最小的分割单位是6位，才可以满足当前多项式求系数和的公式。
所以我们对原数P(n)的二进制数以6位为间隔进行分割，那么我们只需要通过>,&将P(n)每一组中的系数转换成二进制1的个数保存起来，这样我们就得到一个多项式temp，temp和P(n)都是以6位为一组分割的，不同的是P(n)的系数是表示的是这一组的实际值，而temp的系数表示的是P(n)的系数中二进制1的个数,那么temp多项式中的系数和表示的是P(n)二进制中1的个数。
代码如下

//注意：0开头的常数均为8进制数
void count(unsigned int n)
{
    unsigned int temp= 
          (n &010101010101)
     +((n>>1)&010101010101)
     +((n>>2)&010101010101)
     +((n>>3)&010101010101)
     +((n>>4)&010101010101)
     +((n>>5)&010101010101);
 return (temp%63);
}

我们再对这段代码进行优化。
4.代码优化
我们知道temp变量中系数是原数中1的个数，元素中1的个数最大为6，即(000110)₂，所以只需呀3位有效位即可，所以我们在计算位数时，先以每3位为一组计算temp，然后再将temp转化成以6位为一组的形式，即前三位向后移3位+后3位.

//注意：0开头的常数均为8进制数
void count(unsigned int n)
{
    unsigned int temp= 
         (n &011111111111)
    +((n>>1)&011111111111)
    +((n>>2)&011111111111);
 temp = (temp + (temp>>3)) &030707070707;
 return (temp%63);
}

此方法减少了运算过程。
我们还可以优化每3位中组内的计算
(a2²+b2¹+c2⁰)-(a2¹+b2⁰)-(a2⁰) = a+b+c
相当于
n-(n>1&03)-(n>2&01) = a+b+c; 03,01 均为八进制数
又简化了一次运算

void count(unsigned int n)
{
   unsigned int temp= n - ((n>>1)&033333333333) - ((n>>2)&011111111111)
  temp= (temp+(temp>>3))&030707070707;
    return temp%63;
}

经过一次分割，利用系数保存原始数据中每一组1的个数，然后多项式求系数和，然后优化求解每组求1个数的过程，最终得到了这个内有乾坤的算法。