【NYOJ222】整数中的1

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 27 日
#include<stdio.h>
int a[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 main()
{
	/*freopen("Input.txt","r",stdin);
	freopen("2.txt","w",stdout);*/
	//freopen("2.txt","r",stdin);
	int n=0,m=0,k=0;
	//scanf("%d",&n);
	while(scanf("%d%d",&m,&k)!=EOF)
	{
		//scanf("%d",&m);
		/*m=256-1-n;
		m=n-256-1;
		m=m^(m>>1);
		m=m^(m>>2);
		m=m^(m>>4);
		m=m^(m>>8);
		m=m^(m>>16);
		printf("%d\n",m&1);
		m=(m&0x55555555)+((m>> 1)&0x55555555);
		m=(m&0x33333333)+((m>> 2)&0x33333333);
		m=(m&0x0f0f0f0f)+((m>> 4)&0x0f0f0f0f);
		m=(m&0x00ff00ff)+((m>> 8)&0x00ff00ff);
		m=(m&0x0000ffff)+((m>>16)&0x0000ffff);
		printf("%d\n",m);*/
		for(;m<=k;m++)
		{
			unsigned char *ptr=(unsigned char *)&m;
			n+=(a[ptr[0]]+a[ptr[1]]+a[ptr[2]]+a[ptr[3]]);
		}
		printf("%d\n",n);
	}
	return 0;
}        


下边的是数学推理出的方法:

 
#include<cstdio>
unsigned f[]={0,1,4,12,32,80,192,448,1024,2304,5120,11264,24576,53248,114688,245760,524288,1114112,2359296,4980736,10485760,22020096,46137344,96468992,201326592,419430400,872415232,1811939328};
int getpos(int n)
{
	int cnt=0;
	while(n)
	{
		cnt++;
		n>>=1;
	}
	return cnt;
}
int count1(int num)
{
    int i=0;
    while(num)
    {
     num&=(num-1);
     i++;
    }
    return i;
}
int getsub(int s)
{
	s|=s>>1;
	s|=s>>2;
	s|=s>>4;
	s|=s>>8;
	s|=s>>16;
	return s=~s;
}
int g(int m)
{
	if(!(m&(m-1))) 
	{
		int n=getpos(m);
		return f[n-1];
	}
	return g((m&(-m)))+g((m&(m-1)))+count1((getsub(m&(-m))&(m&(m-1))))*(m&(-m));
}
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	printf("%d",g(b+1)-g(a));
}        

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日