将一个二进制数最右边的1之前的部分去掉余下部分称为这个数的二进制尾部,例如6(110)2的二进制尾部为2(10)2  40(101000)2的二进制尾部为8(1000)2

写一程序计算A到B之间所有数的二进制尾部总和

输入

输入文件仅一行包含两个用空格隔开的整数AB,其中1≤A≤B≤1015

输出

输出文件仅一行包含一个整数表示要求的二进制尾部和。注意答案不超过64位二进制整数Pascal中的int64C/C++中的long long。

样例

Input

5 9

Output

13

 

大体思路就是计算出A-B中有多少个数的Lowbit是Kdec 然后把所有的 K 和 个数 相乘即可。

每隔四个数出现一次lowbit为2的数

每隔八个数出现一次lowbit为4的数

依此类推 则有

ans+=binnum[i]*((b+binnum[i])/(2*binnum[i])-(a-1+binnum[i])/(2*binnum[i]));

所以还需要打一个lowbit的表就行了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
using namespace std;

unsigned long long binnum[100]={0},a,b,ans,upat;

void init1()
{
	binnum[0]=1;
	int c1=1;
	unsigned long long a=1;
	while (c1<=60)
	{
		a=a<<1;
		binnum[c1]=a;
		c1++;
	}
}

int main()
{
	freopen("BT.in","r",stdin);
	freopen("BT.out","w",stdout);
	init1();
	scanf("%lld%lld",&a,&b);

	upat=60;
	while (b<binnum[upat]) upat--;
	
	if (a==b)
	{
		printf("%lld\n",binnum[upat]);
		return 0;
	}
	
	for (int i=upat;i>=0;i--)  ans+=binnum[i]*((b+binnum[i])/(2*binnum[i])-(a-1+binnum[i])/(2*binnum[i]));
	printf("%lld\n",ans);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

 


发表评论

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.