[精华] 关于用二分法求解32位整数二进制中1的个数的算法

来源(ChinaUnix.net)

From: http://www.chinaunix.net/jh/23/794901.html

[精华] 关于用二分法求解32位整数二进制中1的个数的算法

--------------------------------------------------------------------------------

http://www.chinaunix.net 作者:liubinbj 发表于:2006-07-20 15:57:49
【发表评论】【查看原文】【C/C++讨论区】【关闭】

[2006/07/20]变更:
原贴名为《放出一个可能是世界上最快的判断32位整数二进制中1的个数的算法》经过大家讨论后发现名不符实,改名!本帖中的测试数据是错误的,主要是循环体被优化掉了,实际运行情况相反,观贴请注意。

[2006/07/20]在做补充说明:
经过争论我们发现了connet提供的算法是目前最快的一种,比我在这篇帖子里提到的要快,我在测试代码时犯了错误,主要是优化方面的问题,所以出现了错误的实验数据,还望不要误导大家!内容就不一一改动了,用批判的眼光来看这个帖子就好。

卫星发射失败,损失了一颗高精度定位卫星:em02::em02::em02:
对此问题感兴趣的请参考http://www.everything2.com/index.pl?node_id=1181258

[2006/07/20]做一些补充说明:

因为昨天搞这个算法时已经比较晚,又感觉还对付,就简单地贴了上来,首贴确实简单了点,引起一些不必要的争论。

首先说下我的机器,PM 1.73G,2M缓存的那种,512M内存,系统是Ubuntu 6.06,编译器gcc 版本 4.0.3 (Ubuntu 4.0.3-1ubuntu5),
所有的测试来源于我的机器,有人报告说PIII 500上我的算法不够快,不知道什么原因,我没这个测试条件了,也请大家在不同的机器上测试。

我的算法是基于二分法,假定一个and(&)加一次判断(0或1)为一次基本操作,最笨的方法是按位来作基本操作,这需要32次基本操作,而且对任何数的判断时间是常数。下面来分析我的算法:

step 1: 一个32位整数首先被分成两个16位来判断,如果有一个部分全为0,则这16位都不用再判断了,这个步骤消耗了2个基本操作时间。
0000011111000001-1010101010101011
step 2:再2分一次成为4个部分,同样消耗两个基本操作
00000111-11000001-10101010-10101011
step 3:再2分一次成为8个部分,同样消耗两个基本操作
0000-0111-1100-0001-1010-1010-1010-1011
step 4:然后判断每个部分是否全为0,消耗8个操作
step 5:到这里就不再2分了,直接按位来判断,一共32次基本操作可以把全部的位1找出来

这样可以看出,如果这个数是0xFFFFFFFF全为1的情况,那么判断次数是2+2+2+8+32=48次,这比按位操作32次多消耗50%但这个数是一个极端的例子。另一个极端例子是0x00000000,这时算法只需要两个基本操作就完成了,比32次减少了93.75%的操作数。通过实验发现,随机数的情况下,算法的判断次数应该比32次要小,个人估计可能是在20次左右(也许有人能证明,需要用到概率论)。

根据测试,在我的系统上把0xFFFFFFFF这种极端情况作为唯一的数据来循环测试多次,计算速度仍比其他算法要快,我没有搞清楚是什么道理。如果是随机数测试,结果同样比其他算法快速。

我的博客里有人留言用汇编移位判断溢出来计算可能会更快,不过我分析这也需要32次基本操作,不过是把&替换成移位操作<<,判断(0或1)是不能少的,具体能达到多少速度,我不知道,因为好久没写汇编了,也许汇编会快些,因为是底层语言。但我这里探讨的是c语言的写法。

和大家共同探讨!

//下面是老贴内容
标题就放了个大卫星呵呵(说明一下,是我目前发现的最快的,别较真)不过我的算法确实比较快,如果你有更快的算法请让我了解并改进。

在坛子里混了些时日,看到过几次计算32位整数二进制中1的个数的算法,大体如此:


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




还有一个更快的算法来源于[url=http://www.beliefxn.com/read.asp?id=616]http://www.beliefxn.com/read.asp?id=616,原作者说是“一个效率极高的算法”,比较而言,仍比我的算法差很多,下面是他的代码:

unsigned int func(unsigned int x)
{
    x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL); // 0-2 in 2 bits
    x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL); // 0-4 in 4 bits
#if 1
    // Version 1
    x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL); // 0-8 in 8 bits
    x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL); // 0-16 in 16 bits
    x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL); // 0-31 in 32 bits
    return x;
#else
    // Version 2
    x = (x + (x >> 4)) & 0x0f0f0f0fUL; // 0-8 in 4 bits
    x += x >> 8; // 0-16 in 8 bits
    x += x >> 16; // 0-32 in 8 bits
    return x & 0xff;
#endif
}




这里面有两个版本,但都不如我的算法快:

//我的算法
int func2(unsigned int n){
	
	int count=0;
	//高16位
	if(n&0xFFFF0000) {
		//高8
		if(n&0xFF000000) {
			//高4
			if(n&0xF0000000) {
				if(n&0x10000000) count++;
				if(n&0x20000000) count++;
				if(n&0x40000000) count++;
				if(n&0x80000000) count++;
			}
			//低4
			if(n&0x0F000000) {
				if(n&0x01000000) count++;
				if(n&0x02000000) count++;
				if(n&0x04000000) count++;
				if(n&0x08000000) count++;
			}			
		}
		//低8
		if(n&0x00FF0000) {
			//高4
			if(n&0x00F00000) {
				if(n&0x00100000) count++;
				if(n&0x00200000) count++;
				if(n&0x00400000) count++;
				if(n&0x00800000) count++;
			}
			//低4
			if(n&0x000F0000) {
				if(n&0x00010000) count++;
				if(n&0x00020000) count++;
				if(n&0x00040000) count++;
				if(n&0x00080000) count++;
			}	
		}
	}
	
	//低16位
	if(n&0x0000FFFF) {
		//高8
		if(n&0x0000FF00) {
			//高4
			if(n&0x0000F000) {
				if(n&0x00001000) count++;
				if(n&0x00002000) count++;
				if(n&0x00004000) count++;
				if(n&0x00008000) count++;
			}
			//低4
			if(n&0x00000F00) {
				if(n&0x00000100) count++;
				if(n&0x00000200) count++;
				if(n&0x00000400) count++;
				if(n&0x00000800) count++;
			}	
		}
		//低8
		if(n&0x000000FF) {
			//高4
			if(n&0x000000F0) {
				if(n&0x00000010) count++;
				if(n&0x00000020) count++;
				if(n&0x00000040) count++;
				if(n&0x00000080) count++;
			}
			//低4
			if(n&0x0000000F) {
				if(n&0x00000001) count++;
				if(n&0x00000002) count++;
				if(n&0x00000004) count++;
				if(n&0x00000008) count++;
			}	
		}
	}

	return count;
}




我的代码运行比上面的代码快很多,具体看测试代码:

/*
程序目的:试图给出一个最快的算法求整数中包含多少个bit 1
作者:liubin
Email: liubinbj@sina.com
*/
#include <sys/time.h> 
    static struct timeval _tstart, _tend;
    static struct timezone tz;

    void time_start(void)
    {
        gettimeofday(&_tstart, &tz);
    }
    void time_end(void)
    {
        gettimeofday(&_tend,&tz);
    }

    double time_val()
    {
        double t1, t2;

        t1 =  (double)_tstart.tv_sec + (double)_tstart.tv_usec/(1000*1000);
        t2 =  (double)_tend.tv_sec + (double)_tend.tv_usec/(1000*1000);
        return t2-t1;
    }

/*
//这个算法比下一个慢
int func(unsigned int n) {
	int count=0;
	while(n>0) {
		n&=(n-1);
		count++;
	}
	return count;
}
*/
//
unsigned int func(unsigned int x)
{
    x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL); // 0-2 in 2 bits
    x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL); // 0-4 in 4 bits
#if 0
    // Version 1
    x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL); // 0-8 in 8 bits
    x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL); // 0-16 in 16 bits
    x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL); // 0-31 in 32 bits
    return x;
#else
    // Version 2
    x = (x + (x >> 4)) & 0x0f0f0f0fUL; // 0-8 in 4 bits
    x += x >> 8; // 0-16 in 8 bits
    x += x >> 16; // 0-32 in 8 bits
    return x & 0xff;
#endif
}


//我的算法
int func2(unsigned int n){
	
	int count=0;
	//高16位
	if(n&0xFFFF0000) {
		//高8
		if(n&0xFF000000) {
			//高4
			if(n&0xF0000000) {
				if(n&0x10000000) count++;
				if(n&0x20000000) count++;
				if(n&0x40000000) count++;
				if(n&0x80000000) count++;
			}
			//低4
			if(n&0x0F000000) {
				if(n&0x01000000) count++;
				if(n&0x02000000) count++;
				if(n&0x04000000) count++;
				if(n&0x08000000) count++;
			}			
		}
		//低8
		if(n&0x00FF0000) {
			//高4
			if(n&0x00F00000) {
				if(n&0x00100000) count++;
				if(n&0x00200000) count++;
				if(n&0x00400000) count++;
				if(n&0x00800000) count++;
			}
			//低4
			if(n&0x000F0000) {
				if(n&0x00010000) count++;
				if(n&0x00020000) count++;
				if(n&0x00040000) count++;
				if(n&0x00080000) count++;
			}	
		}
	}
	
	//低16位
	if(n&0x0000FFFF) {
		//高8
		if(n&0x0000FF00) {
			//高4
			if(n&0x0000F000) {
				if(n&0x00001000) count++;
				if(n&0x00002000) count++;
				if(n&0x00004000) count++;
				if(n&0x00008000) count++;
			}
			//低4
			if(n&0x00000F00) {
				if(n&0x00000100) count++;
				if(n&0x00000200) count++;
				if(n&0x00000400) count++;
				if(n&0x00000800) count++;
			}	
		}
		//低8
		if(n&0x000000FF) {
			//高4
			if(n&0x000000F0) {
				if(n&0x00000010) count++;
				if(n&0x00000020) count++;
				if(n&0x00000040) count++;
				if(n&0x00000080) count++;
			}
			//低4
			if(n&0x0000000F) {
				if(n&0x00000001) count++;
				if(n&0x00000002) count++;
				if(n&0x00000004) count++;
				if(n&0x00000008) count++;
			}	
		}
	}

	return count;
}

#include <math.h>

int main()
{

	//顺序数的检验,1亿个
	unsigned long i;
	printf("begin test func\n");
	time_start();
	for(i=0;i<100000000;i++)
	{
		func(i);
	}
	time_end();
	printf("test func use %0.4f seconds\n",time_val());
	printf("begin test func2\n");
	time_start();
	for(i=0;i<100000000;i++)
	{
		func2(i);
	}
	time_end();
	printf("test func2 use %0.4f seconds\n",time_val());
	printf("end\n");

	//随机数的检验,1亿个
	srand();
	printf("begin test func random\n");
	time_start();
	for(i=0;i<100000000;i++)
	{
		func(rand());
	}
	time_end();
	printf("test func random use %0.4f seconds\n",time_val());
	printf("begin test func2 random\n");
	time_start();
	for(i=0;i<100000000;i++)
	{
		func2(rand());
	}
	time_end();
	printf("test func2 random use %0.4f seconds\n",time_val());

	//正确性检查
	printf("test func2 correction\n");
	for(i=0;i<1000000;i++)
	{
		unsigned int p=rand();
		if(func2(p)!=func(p)) { 
			printf("func2 error on %u",p);
			break;
		}
	}

	printf("finist correction test\n");
}





编译代码

gcc -O2 -o bit bitcount.c



我的机器输出:


begin test func
test func use 0.2185 seconds
begin test func2
test func2 use 0.1433 seconds
end
begin test func random
test func random use 5.2226 seconds
begin test func2 random
test func2 random use 3.9320 seconds
test func2 correction
finist correction test



可以看出我的算法比第二种方法快了许多。

结论:

虽然第一种方法在形式上很完美和简洁,但实际进行科学计算时仍嫌优化不够。第二种算法思路是好的,总体也不错,但还是有很大的优化余地。我的方法目前是最快的,但是否是世界最快,要看各位评说,也许还能有更快的算法,但应该优化的余地不会太大了。



[ 本帖最后由 liubinbj 于 2006-7-20 17:01 编辑 ]



Link: http://www.asm32.net/article_details.aspx?id=1402


浏览次数 646 发布时间 2006/7/21 2:33:52 从属分类 ARITHMETIC 【评论】【 】【打印】【关闭
 
| www.asm32.net | 2006版 | 资料中心 | linux | asm/asm32 | C/C++ | VC++ | java | Python | 书签 | ASP.Net书签 | 京ICP备09029108号-1