将一个二进制数最右边的1之前的部分去掉余下部分称为这个数的二进制尾部，例如6(110)2的二进制尾部为2(10)2 40(101000)2的二进制尾部为8（1000）2
写一程序计算A到B之间所有数的二进制尾部总和
输入
输入文件仅一行包含两个用空格隔开的整数A和B，其中1≤A≤B≤1015。
输出
输出文件仅一行包含一个整数表示要求的二进制尾部和。注意答案不超过64位二进制整数，即Pascal中的int64和C/C++中的long long。
样例
Input
5 9
Output
13
大体思路就是计算出A-B中有多少个数的Lowbit是Kdec 然后把所有的 K 和 个数 相乘即可。
每隔四个数出现一次lowbit为2的数
每隔八个数出现一次lowbit为4的数
依此类推 则有
|
1 |
ans+=binnum[i]*((b+binnum[i])/(2*binnum[i])-(a-1+binnum[i])/(2*binnum[i])); |
所以还需要打一个lowbit的表就行了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#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; } |