等比数列求和问题
谢谢_百度知道
等比数列求和问题
1/2+1/4+1/8+1/16+1/32+……到1/2的n次
提问者采纳
（1）等比数列的通项公式是：An=A1*q^（n－1）
若通项公式变形为an=a1/q*q^n(n∈N*),当q＞0时，则可把an看作自变量n的函数，点(n,an)是曲线y=a1/q*q^x上的一群孤立的点。
（2）求和公式：Sn=nA1(q=1)
Sn=A1(1-q^n)/(1-q)
=(a1-a1q^n)/(1-q)
=a1/(1-q)-a1/(1-q)*q^n ( 即A-Aq^n)
(前提：q不等于 1)这个数列首项是1/2,公比是1/2所以原式=1/2*(1-(1/2)^n)/(1-1/2)=1-(1/2)^n
提问者评价
其他类似问题
按默认排序
其他2条回答
设数列的和为S2S=1+1/2+1/4+1/8.....到1/2的n-1次方所以2S-S=S=1-1/2的n次方
Sn=1/2[（1-1/2ˇn)/1-q]
等比数列的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁如何利用matlab编程求解n！从n=1到n=20求和_百度知道
如何利用matlab编程求解n！从n=1到n=20求和
提问者采纳
y=1;for i=1;y 以上是求阶乘求和为funticon fun(x:n tem=i*tem:1:n;
y=y*i,n)sum=0tem=1for i=0; sum=sum+x^i&#47有内部函数为factorial(n)或者n=20
程序是错的
function fun(x,n)sum=0tem=1for i=0:n tem=i* sum=sum+endsum
其他类似问题
matlab的相关知识
其他1条回答
y=y+xa=f(20)
涨乱斥喝俪估符埔
（引用M文件f.m）(function y=f(k)y=0:k
x=x*i;) 结果;endy：a =
2;x=1;for i=1
等待您来回答
您可能关注的推广
下载知道APP
随时随地咨询
出门在外也不愁数列求和：S（n）=∑n/(2n+1)! n从1到无穷大...求解啊...._百度知道
数列求和：S（n）=∑n/(2n+1)! n从1到无穷大...求解啊....
提问者采纳
e^(-x)=1-x/1!+x^2/2!-x^3/3!+...+(-1)^n*x^n/n!+...
x∈R即：e^(-1)=1-1/1!+1/2!-1/3!+...+(-1)^n/n!+...=(1/2!-1/3!)+(1/4!-1/5!)+...+[1/(2n)!-1/(2n+1)!]+...=2*1/3!+2*2/5!+...+2*n/(2n+1)!+...=2S(n)故：S(n)=1/(2e)
提问者评价
谢谢~我懂了~之前没有乘2就直接拆分...
其他类似问题
数列求和的相关知识
其他2条回答
我毕业差不多十年了，现在给你个思路，具体我就不算了s(n+1) = ∑(n+1)/(2N+3)!=∑(n/(2n+3)!+1/(2n+3)!)
= ∑n/(2n+3)/(2n+2)/(2n+1)+∑1/(2n+3)！
=1/(2n+3)/(2n+2)∑n/(2n+1)+∑1/(2n+3)！
=s(n)/(2n+3)/(2n+2)+∑1/(2n+3)！当n-&无穷大时候，s(n+1) = s(n)所以s(n）=s(n)/(2n+3)/(2n+2)+∑1/(2n+3)！具体 ∑1/(2n+3)的求法忘记公式了不过书上应该有公式类似于求积分。
∑n/(2n+1)! =1/2*∑2n/(2n+1)!
=1/2*∑(2n+1-1)/(2n+1)!
=1/2*∑{1/2n!-1/(2n+1)!}
=1/2*(1/2!-1/3!+1/4!-1/5!....)泰勒公式e^x=1+x+x^2/2!... 所以e^(-1)=(1+(-1)+1/2!-1/3!+1/4!-1/5!....)= (1/2!-1/3!+1/4!-1/5!....), 所以结果为1/2*e^(-1) 即1/2e
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁2371人阅读
算是上一篇的续集[算法]计算某正整数换算成二进制后bit为1的个数,&,&by&//顺便求推荐：如何在WordPress中插入格式化的带语法高亮的代码或者数学公式，如果你知道的话，请直接在下面留言，谢谢~侃哥在准备去Cisco的面试，问我一道题：求二进制数中1的个数。看起来简单，不假思索地写下了num=0;while(x){num+=x&1;x&&1;}位运算，似乎已经够简单了。问我还有没有更简单的解法，我想了会儿没想出来，但我觉得应该有。网上一搜，就被一个巧妙的算法震惊了：num=0;while(x){x &= (x-1);num++;}相比我的算法，只有一点点改动；但我的算法循环的次数是和原数log 2相关的，而这个算法的循环次数只与原数中bit为1的数目相关，这样，它的循环次数必定少于我的。果然大长见识。在网上仔细搜了搜，发现好多神奇的算法，虽然没能全看懂，不过摘录几篇，大家一起学习学习~/************ 第一篇 **************/对于一个字节（8bit）的变量，求其二进制表示中“1”的个数，要求算法的执行效率尽可能地高。大多数的读者都会有这样的反应：这个题目也太简单了吧，解法似乎也相当地单一，不会有太多的曲折分析或者峰回路转之处。那么面试者到底能用这个题目 考察我们什么呢？事实上，在编写程序的过程中，根据实际应用的不同，对存储空间或效率的要求也不一样。比如在PC上的程序编写与在嵌入式设备上的程序编写 就有很大的差别。我们可以仔细思索一下如何才能使效率尽可能地“高”。【解法一】可以举一个八位的二进制例子来进行分析。对于二进制操作，我们知道，除以一个2，原来的数字将会减少一个0。如果除的过程中有余，那么就表示当前位置有一个1。以10 100 010为例；第一次除以2时，商为1 010 001，余为0。第二次除以2时，商为101 000，余为1。因此，可以考虑利用整型数据除法的特点，通过相除和判断余数的值来进行分析。于是有了如下的代码。代码清单2-1int Count(int v){int num = 0;while(v){if(v % 2 == 1){num++;}v = v/ 2;}}【解法二】使用位操作前面的代码看起来比较复杂。我们知道，向右移位操作同样也可以达到相除的目的。唯一不同之处在于，移位之后如何来判断是否有1存在。对于这个问题，再来看看一个八位的数字：10 100 001。在向右移位的过程中，我们会把最后一位直接丢弃。因此，需要判断最后一位是否为1，而“与”操作可以达到目的。可以把这个八位的数字与进行“与”操作。如果结果为1，则表示当前八位数的最后一位为1，否则为0。代码如下：代码清单2-2int Count(int v){int num = 0;While(v){num += v &0×01;v &&= 1;}}【解法三】位操作比除、余操作的效率高了很多。但是，即使采用位操作，时间复杂度仍为O（log2v），log2v为二进制数的位数。那么，还能不能再降低一些复杂度呢？如果有办法让算法的复杂度只与“1”的个数有关，复杂度不就能进一步降低了吗？同样用10 100 001来举例。如果只考虑和1的个数相关，那么，我们是否能够在每次判断中，仅与1来进行判断呢？为了简化这个问题，我们考虑只有一个1的情况。例如：01 000 000。如何判断给定的二进制数里面有且仅有一个1呢？可以通过判断这个数是否是2的整数次幂来实现。另外，如果只和这一个“1”进行判断，如何设计操作呢？我们知道的是，如果进行这个操作，结果为0或为1，就可以得到结论。如果希望操作后的结果为0，01 000 000可以和00 111 111进行“与”操作。这样，要进行的操作就是 01 000 000 &（01 000 000 – 00 000 001）= 01 000 000 &00 111 111 = 0。因此就有了解法三的代码：代码清单2-3int Count(int v){int num = 0;while(v){v &= (v-1);num++;}}【解法四】使用分支操作解法三的复杂度降低到O（M），其中M是v中1的个数，可能会有人已经很满足了，只用计算1的位数，这样应该够快了吧。然而我们说既然只有八位数据，索性直接把0~255的情况都罗列出来，并使用分支操作，可以得到答案，代码如下：代码清单2-4int Count(int v){int num = 0;switch (v){case 0×0:num = 0;case 0×1:case 0×2:case 0×4:case 0×8:case 0×10:case 0×20:case 0×40:case 0×80:num = 1;case 0×3:case 0×6:case 0xc:case 0×18:case 0×30:case 0×60:case 0xc0:num = 2;//…}}解法四看似很直接，但实际执行效率可能会低于解法二和解法三，因为分支语句的执行情况要看具体字节的值，如果a&=0，那自然在第1个case就得出了答案，但是如果a&=255，则要在最后一个case才得出答案，即在进行了255次比较操作之后！看来，解法四不可取！但是解法四提供了一个思路，就是采用空间换时间的方法，罗列并直接给出值。如果需要快速地得到结果，可以利用空间或利用已知结论。这就好比已经知道计算1+2+ … +N的公式，在程序实现中就可以利用公式得到结论。最后，得到解法五：算法中不需要进行任何的比较便可直接返回答案，这个解法在时间复杂度上应该能够让人高山仰止了。【解法五】查表法代码清单2-5/* 预定义的结果表 */int countTable[256] ={0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3,4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3,4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4,5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3,4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4,4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6,7, 6, 7, 7, 8};int Count(int v){//check parameterreturn countTable[v];}这是个典型的空间换时间的算法，把0~255中“1”的个数直接存储在数组中，v作为数组的下标，countTable[v]就是v中“1”的个数。算法的时间复杂度仅为O（1）。在一个需要频繁使用这个算法的应用中，通过“空间换时间”来获取高的时间效率是一个常用的方法，具体的算法还应针对不同应用进行优化。扩展问题1.&& 如果变量是32位的DWORD，你会使用上述的哪一个算法，或者改进哪一个算法？2.&& 另一个相关的问题，给定两个正整数（二进制形式表示）A和B，问把A变为B需要改变多少位（bit）？也就是说，整数A和B&的二进制表示中有多少位是不同的？摘自：/Articles/ArticleItem.aspx?Guid=edb3a02b-6d5e-42c7-b2a5-4ae4a18f4254#./************************* 第二篇 **********************/问题描述任意给定一个32位无符号整数n，求n的二进制表示中1的个数，比如n = 5（0101）时，返回2，n = 15（1111）时，返回4这也是一道比较经典的题目了，相信不少人面试的时候可能遇到过这道题吧，下面介绍了几种方法来实现这道题，相信很多人可能见过下面的算法，但我相信很少有人见到本文中所有的算法。如果您上头上有更好的算法，或者本文没有提到的算法，请不要吝惜您的代码，分享的时候，也是学习和交流的时候。普通法我总是习惯叫普通法，因为我实在找不到一个合适的名字来描述它，其实就是最简单的方法，有点程序基础的人都能想得到，那就是移位+计数，很简单，不多说了，直接上代码，这种方法的运算次数与输入n最高位1的位置有关，最多循环32次。int BitCount(unsigned int n)
unsigned int c = 0 ; // 计数器
while (n & 0)
if((n & 1) == 1) // 当前位是1
++ // 计数器加1
n &&= 1 ; // 移位
}一个更精简的版本如下int BitCount1(unsigned int n)
unsigned int c = 0 ; // 计数器
for (c = 0; n &&= 1) // 循环移位
c += n & 1 ; // 如果当前位是1，则计数器加1
}快速法这种方法速度比较快，其运算次数与输入n的大小无关，只与n中1的个数有关。如果n的二进制表示中有k个1，那么这个方法只需要循环k次即可。其原理是不断清除n的二进制表示中最右边的1，同时累加计数器，直至n为0，代码如下int BitCount2(unsigned int n)
unsigned int c = 0 ;
for (c = 0; ++c)
n &= (n - 1) ; // 清除最低位的1
}为什么n &= (n – 1)能清除最右边的1呢？因为从二进制的角度讲，n相当于在n – 1的最低位加上1。举个例子，8（1000）= 7（0111）+ 1（0001），所以8 & 7 = （1000）&（0111）= 0（0000），清除了8最右边的1（其实就是最高位的1，因为8的二进制中只有一个1）。再比如7（0111）= 6（0110）+ 1（0001），所以7 & 6 = （0111）&（0110）= 6（0110），清除了7的二进制表示中最右边的1（也就是最低位的1）。查表法动态建表由于表示在程序运行时动态创建的，所以速度上肯定会慢一些，把这个版本放在这里，有两个原因1. 介绍填表的方法，因为这个方法的确很巧妙。2. 类型转换，这里不能使用传统的强制转换，而是先取地址再转换成对应的指针类型。也是常用的类型转换方法。int BitCount3(unsigned int n)
unsigned char BitsSetTable256[256] = {0} ;
// 初始化表
for (int i = 0; i & 256; i++)
BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
unsigned int c = 0 ;
unsigned char * p = (unsigned char *) &
c = BitsSetTable256[p[0]] +
BitsSetTable256[p[1]] +
BitsSetTable256[p[2]] +
BitsSetTable256[p[3]];
}先说一下填表的原理，根据奇偶性来分析，对于任意一个正整数n1.如果它是偶数，那么n的二进制中1的个数与n/2中1的个数是相同的，比如4和2的二进制中都有一个1，6和3的二进制中都有两个1。为啥？因为n是由n/2左移一位而来，而移位并不会增加1的个数。2.如果n是奇数，那么n的二进制中1的个数是n/2中1的个数+1，比如7的二进制中有三个1，7/2 = 3的二进制中有两个1。为啥？因为当n是奇数时，n相当于n/2左移一位再加1。再说一下查表的原理对于任意一个32位无符号整数，将其分割为4部分，每部分8bit，对于这四个部分分别求出1的个数，再累加起来即可。而8bit对应2^8 = 256种01组合方式，这也是为什么表的大小为256的原因。注意类型转换的时候，先取到n的地址，然后转换为unsigned char*，这样一个unsigned int（4 bytes）对应四个unsigned char（1 bytes），分别取出来计算即可。举个例子吧，以（十六进制）为例，先写成二进制形式-8bit一组，共四组，以不同颜色区分，这四组中1的个数分别为4，4，3，2，所以一共是13个1，如下面所示。11&&= 4 + 4 + 3 + 2 = 13静态表-4bit原理和8-bit表相同，详见8-bit表的解释int BitCount4(unsigned int n)
unsigned int table[16] =
0, 1, 1, 2,
1, 2, 2, 3,
1, 2, 2, 3,
2, 3, 3, 4
unsigned int count = 0 ;
count += table[n & 0xf] ;
}静态表-8bit首先构造一个包含256个元素的表table，table[i]即i中1的个数，这里的i是[0-255]之间任意一个值。然后对于任意一个32bit无符号整数n，我们将其拆分成四个8bit，然后分别求出每个8bit中1的个数，再累加求和即可，这里用移位的方法，每次右移8位，并与0xff相与，取得最低位的8bit，累加后继续移位，如此往复，直到n为0。所以对于任意一个32位整数，需要查表4次。以十进制数为例，其对应的二进制数为，对应的四次查表过程如下：红色表示当前8bit，绿色表示右移后高位补零。第一次（n & 0xff）&&&&&&&&&&&&&第二次（(n && 8) & 0xff）&&第三次（(n && 16) & 0xff）第四次（(n && 24) & 0xff）int BitCount7(unsigned int n)
unsigned int table[256] =
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
return table[n & 0xff] +
table[(n && 8) & 0xff] +
table[(n && 16) & 0xff] +
table[(n && 24) & 0xff] ;
}当然也可以搞一个16bit的表，或者更极端一点32bit的表，速度将会更快。平行算法网上都这么叫，我也这么叫吧，不过话说回来，的确有平行的意味在里面，先看代码，稍后解释int BitCount4(unsigned int n)
n = (n & 0x) + ((n && 1) & 0x) ;
n = (n & 0x) + ((n && 2) & 0x) ;
n = (n & 0x0f0f0f0f) + ((n && 4) & 0x0f0f0f0f) ;
n = (n & 0x00ff00ff) + ((n && 8) & 0x00ff00ff) ;
n = (n & 0x0000ffff) + ((n && 16) & 0x0000ffff) ;
}速度不一定最快，但是想法绝对巧妙。 说一下其中奥妙，其实很简单，先将n写成二进制形式，然后相邻位相加，重复这个过程，直到只剩下一位。以217（）为例，有图有真相，下面的图足以说明一切了。217的二进制表示中有5个1完美法int BitCount5(unsigned int n)
unsigned int tmp = n - ((n && 1) & ) - ((n && 2) & );
return ((tmp + (tmp && 3)) & ) % 63;
}最喜欢这个，代码太简洁啦，只是有个取模运算，可能速度上慢一些。区区两行代码，就能计算出1的个数，到底有何奥妙呢？为了解释的清楚一点，我尽量多说几句。第一行代码的作用先说明一点，以0开头的是8进制数，以0x开头的是十六进制数，上面代码中使用了三个8进制数。将n的二进制表示写出来，然后每3bit分成一组，求出每一组中1的个数，再表示成二进制的形式。比如n = 50，其二进制表示为110010，分组后是110和010，这两组中1的个数本别是2和3。2对应010，3对应011，所以第一行代码结束后，tmp = 010011，具体是怎么实现的呢？由于每组3bit，所以这3bit对应的十进制数都能表示为2^2 * a + 2^1&* b + c的形式，也就是4a + 2b + c的形式，这里a,b,c的值为0或1，如果为0表示对应的二进制位上是0，如果为1表示对应的二进制位上是1，所以a + b + c的值也就是4a + 2b + c的二进制数中1的个数了。举个例子，十进制数6（0110）= 4 * 1 + 2 * 1 + 0，这里a = 1, b = 1, c = 0, a + b + c = 2，所以6的二进制表示中有两个1。现在的问题是，如何得到a + b + c呢？注意位运算中，右移一位相当于除2，就利用这个性质！4a + 2b + c 右移一位等于2a + b4a + 2b + c 右移量位等于a然后做减法4a + 2b + c&–(2a + b)&– a = a + b + c，这就是第一行代码所作的事，明白了吧。第二行代码的作用在第一行的基础上，将tmp中相邻的两组中1的个数累加，由于累加到过程中有些组被重复加了一次，所以要舍弃这些多加的部分，这就是&的作用，又由于最终结果可能大于63，所以要取模。需要注意的是，经过第一行代码后，从右侧起，每相邻的3bit只有四种可能，即000, 001, 010, 011，为啥呢？因为每3bit中1的个数最多为3。所以下面的加法中不存在进位的问题，因为3 + 3 = 6，不足8，不会产生进位。tmp + (tmp && 3)-这句就是是相邻组相加，注意会产生重复相加的部分，比如tmp = 659&= 001 010 010 011时，tmp && 3 = 000 001 010 010，相加得001&010&010&011000&001&010&010———————001&011&100&101001 + 101 = 1 + 5 = 6，所以659的二进制表示中有6个1注意我们想要的只是第二组和最后一组（绿色部分），而第一组和第三组（红色部分）属于重复相加的部分，要消除掉，这就是&所完成的任务（每隔三位删除三位），最后为什么还要%63呢？因为上面相当于每次计算相连的6bit中1的个数，最多是111111 = 77（八进制）= 63（十进制），所以最后要对63取模。位标志法感谢网友&提供struct _byte
unsigned a:1;
unsigned b:1;
unsigned c:1;
unsigned d:1;
unsigned e:1;
unsigned f:1;
unsigned g:1;
unsigned h:1;
long get_bit_count( unsigned char b )
struct _byte *by = (struct _byte*)&b;
return (by-&a+by-&b+by-&c+by-&d+by-&e+by-&f+by-&g+by-&h);
}指令法感谢网友&提供使用微软提供的指令，首先要确保你的CPU支持SSE4指令，用Everest和CPU-Z可以查看是否支持。unsigned int n = 127 ;
unsigned int bitCount = _mm_popcnt_u32(n) ;&References作者：出处：本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利.&/************************** 第三篇 ***********************/问题：给出一个整数，请设计算法计算该整数以二进制格式表示时的1的个数。例如，十进制整数150，二进制表示为，则1的个数为4个。要求算法效率尽可能的高。这是今天从一个blog 上看到的题目，乍一看到题目我没想到什么思路（显然，逐个bit位的数肯定不是最优算法）。Blog上给出了算法思路和示例，读后外加实践验证后才理解了其中的这个算法（另两个高级算法实在琢磨不清楚，还请高人看到后教我）：const UINT32 m1
const UINT32 m2
const UINT32 m4
= 0x0f0f0f0f;
const UINT32 m8
= 0x00ff00
const UINT32 m16 = 0x0000
/* This is a naive implementation, shown for comparison, and to help in
* understanding the better functions. It uses 20 arithmetic operations
* (shift, add, and).
*原来这还仅仅是一个比较“天真幼稚”的实现，用来使得读者更好的理解和比较其他的更高级的
*这个实现使用了20个算术操作符（包括移位、加号以及与操作）。--Adreaman
int popcount_1(UINT32 x)
x = (x & m1) + ((x && 1) & m1); /*第一步*/
x = (x & m2) + ((x && 2) & m2); /*第二步*/
x = (x & m4) + ((x && 4) & m4); /*第三步*/
x = (x & m8) + ((x && 8) & m8);
x = (x & m16) + ((x && 16) & m16);
}这个算法的设计思路是这样的（上面的例子是针对占位32bit的整数来举例的）：设原整数值为x，第一步：把x的32个bit分成16组（第32bit和第31bit一组，第30bit和第29bit一组……以此类推），然后将每一组的两bit 上的值（因为是二进制数，所以要么是0要么是1）相加并把结果还放在这两bit的位置上，这样，得到结果整数x1，x1的二进制（32bit）可以分为 16组，每一组的数值就是原来整数x在那两bit上1的个数。第二步：把第一步得到的结果x1的32bit，分成8组(第32、31、30、29bit一组，第28、27、26、25bit一组……以此类推)，然后每一组的四bit上的值相加并把结果还放在这四bit的位置上，这样，又得到结果整数x2，x2的二进制可以分为8组，每一组的数值就是原来整数x在那四bit上的1的个数。……这样一直分组计算下去，最终，把两个16bit上1的个数相加，得到原来整数x的32bit上1的个数。下面是我刚看这个算法时想要验证一下，写的验证程序，验证宽2bit、4bit、8bit、16bit和32bit的情况下，此算法的正确性。结果当然是没有问题啦。注意，逐个计算32bit的计算量太大，一般的机器大概需要1天左右才能把所有32bit的整数验证完毕。/* ============================================* Problem:*&& The fastest way to count how many 1s in a 32-bits integer.** Algorithm:*&& The problem equals to calculate the Hamming weight of a 32-bits integer,*&& or the Hamming distance between a 32-bits integer and 0. In binary cases,*&& it is also called the population count, or popcount.[1]**&& The best solution known are based on adding counts in a tree pattern*&& (divide and conquer). Due to space limit, here is an example for a*&& 8-bits binary number A=]* | Expression&&&&&&&&&&& | Binary&& | Decimal | Comment&&&&&&&&&&&&&&&&&&& |* | A&&&&&&&&&&&&&&&&&&&& |
|&&&&&&&& | the original number&&&&&&& |* | B = A & &&&&& |
| 1,0,1,0 | every other bit from A&&&& |* | C = (A&&1) &
| 0,1,1,0 | remaining bits from A&&&&& |* | D = B + C&&&&&&&&&&&& |
| 1,1,2,0 | # of 1s in each 2-bit of A |* | E = D & &&&&& |
| 1,0&&&& | every other count from D&& |* | F = (D&&2) &
| 1,2&&&& | remaining counts from D&&& |* | G = E + F&&&&&&&&&&&& |
| 2,2&&&& | # of 1s in each 4-bit of A |* | H = G & &&&&& |
| 2&&&&&& | every other count from G&& |* | I = (G&&4) &
| 2&&&&&& | remaining counts from G&&& |* | J = H + I&&&&&&&&&&&& |
| 4&&&&&& | No. of 1s in A&&&&&&&&&&&& |* Hence A have 4 1s.** [1] http://en.wikipedia.org/wiki/Hamming_weight** =============================================*/#includetypedef unsigned int UINT32;const UINT32 c2m1 = 0×1; // 01const UINT32 c4m1 = 0×5;& //0101const UINT32 c4m2 = 0×3;& //0011const UINT32 c8m1 = 0×55; //const UINT32 c8m2 = 0×33; //const UINT32 c8m4 = 0×0f; //const UINT32 c16m1 = 0×5555; //0101const UINT32 c16m2 = 0×3333; //0011const UINT32 c16m4 = 0×0f0f; //1111const UINT32 c16m8 = 0×00 //1111const UINT32 c32m1& = 0×;& // const UINT32 c32m2& = 0×;& // const UINT32 c32m4& = 0×0f0f0f0f;& // const UINT32 c32m8& = 0×00ff00& // const UINT32 c32m16 = 0×0000& // /*const UINT32 c64m1& = 0×5555; //const UINT32 c64m2& = 0×3333; //const UINT32 c64m4& = 0×0f0f0f0f0f0f0f0f; //const UINT32 c64m8& = 0×00ff00ff00ff00 //const UINT32 c64m16 = 0×0000ffff0000 //const UINT32 c64m32 = 0× //*/int popcount_2(UINT32 x){x = (x & c2m1) + ((x&&1) & c2m1);return (int)x;}int popcount_4(UINT32 x){x = (x & c4m1) + ((x&&1) & c4m1);x = (x & c4m2) + ((x&&2) & c4m2);return (int)x;}int popcount_8(UINT32 x){x = (x & c8m1) + ((x&&1) & c8m1);x = (x & c8m2) + ((x&&2) & c8m2);x = (x & c8m4) + ((x&&4) & c8m4);return (int)x;}int popcount_16(UINT32 x){x = (x & c16m1) + ((x&&1) & c16m1);x = (x & c16m2) + ((x&&2) & c16m2);x = (x & c16m4) + ((x&&4) & c16m4);x = (x & c16m8) + ((x&&8) & c16m8);return (int)x;}int popcount_32(UINT32 x){x = (x & c32m1) + ((x && 1) & c32m1);x = (x & c32m2) + ((x && 2) & c32m2);x = (x & c32m4) + ((x && 4) & c32m4);x = (x & c32m8) + ((x && 8) & c32m8);x = (x & c32m16) + ((x && 16) & c32m16);return (int)x;}/*int popcount_64(UINT32 x){x = (x & c64m1) + ((x && 1) & c64m1);x = (x & c64m2) + ((x && 2) & c64m2);x = (x & c64m4) + ((x && 4) & c64m4);x = (x & c64m8) + ((x && 8) & c64m8);x = (x & c64m16) + ((x && 16) & c64m16);x = (x & c64m32) + ((x && 32) & c64m32);return (int)x;}*//*笨算法，呵呵，但是肯定正确，用来验证比较*/int my(UINT32 x){int nCount = 0;int i = 1;for(i = 1; i != 0× ; i=i&&1){//printf(”0x%x”,i);if(x&i)nCount++;}return nC}int main(){UINT32 intx= 0;printf(”start!\n”);printf(”List for 2 bit number:\n”);for(intx = 0; intx!=0×3; intx++){if(my(intx) != (int)popcount_2(intx)){printf(”No.%d : real count %d; popcount_2 = %d\n”,intx,my(intx),popcount_2(intx));}}printf(”List for 4 bit number:\n”);for(intx = 0; intx!=0 intx++){if(my(intx) != (int)popcount_4(intx)){printf(”No.%d : real count %d; popcount_4 = %d\n”,intx,my(intx),popcount_4(intx));}}printf(”List for 8 bit number:\n”);for(intx = 0; intx!=0 intx++){if(my(intx) == (int)popcount_8(intx)){printf(”No.%d : real count %d; popcount_8 = %d\n”,intx,my(intx),popcount_8(intx));}}printf(”List for 16 bit number:\n”);for(intx = 0; intx!=0 intx++){if(my(intx) != (int)popcount_16(intx)){printf(”No.%d : real count %d; popcount_16 = %d\n”,intx,my(intx),popcount_16(intx));}}printf(”List for 32 bit number:\n”);for(intx = 0; intx!=0 intx++){if(my(intx) != (int)popcount_32(intx)){printf(”No.%d : real count %d; popcount_32 = %d\n”,intx,my(intx),popcount_32(intx));}}printf(”finish!\n”);return 0;}第三篇摘自：&是不是大长见识呢？其实对于我们电工的同学来说，与我们最接近的应该是那个调用SSE4指令集的算法，够邪恶的~
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：807883次
积分：12777
积分：12777
排名：第287名
原创：342篇
转载：78篇
译文：13篇
评论：1541条
(1)(1)(2)(2)(1)(1)(4)(2)(13)(1)(2)(1)(4)(5)(4)(4)(2)(4)(6)(1)(1)(1)(2)(1)(1)(1)(2)(3)(3)(1)(4)(2)(1)(1)(1)(6)(3)(3)(1)(2)(1)(2)(1)(2)(2)(5)(4)(5)(6)(8)(5)(3)(2)(4)(4)(7)(14)(5)(3)(2)(5)(7)(14)(9)(32)(6)(4)(15)(10)(3)(1)(2)(2)(4)(7)(11)(5)(3)(13)(20)(3)(8)(3)(1)(12)(25)(21)(2)