首页 > 代码库 > hnu Counting ones 统计1-n 二进制中1的个数
hnu Counting ones 统计1-n 二进制中1的个数
| Counting ones |
| Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB |
| Total submit users: 18, Accepted users: 16 |
| Problem 13030 : No special judgement |
| Problem description |
| Carl is right now the happiest child in the world: he has just learned this morning what the bi- nary system is. He learned, for instance, that the binary representation of a positive integer k is a string anan-1 ... a1a0 where each ai is a binary digit 0 or 1, starting with an = 1, and such that k = Σai × 2i(i from 0 to n). It is really nice to see him turning decimal numbers into binary numbers, and then adding and even multiplying them. Caesar is Carl‘s older brother, and he just can‘t stand to see his little brother so happy. So he has prepared a challenge: "Look Carl, I have an easy question for you: I will give you two integers A and B, and you have to tell me how many 1‘s there are in the binary representation of all the integers from A to B, inclusive. Get ready". Carl agreed to the challenge. After a few minutes, he came back with a list of the binary representation of all the integers from 1 to 100. "Caesar, I‘m ready". Caesar smiled and said: "Well, let me see, I choose A = 1015 and B = 1016. Your list will not be useful". Carl hates loosing to his brother so he needs a better solution fast. Can you help him? |
| Input |
| A single line that contains two integers A and B (1 ≤ A ≤ B ≤ 1016). |
| Output |
| Output a line with an integer representing the total number of digits 1 in the binary representation of all the integers from A to B, inclusive. |
| Sample Input |
Sample input 11000000000000000 10000000000000000Sample input 22 12Sample input 39007199254740992 9007199254740992 |
| Sample Output |
Sample output 1239502115812196372Sample output 221Sample output 31 |
| Problem Source |
| ICPC Latin American Regional 2013 |
1 #include<iostream> 2 #include<stdio.h> 3 #include<cstring> 4 #include<cstdlib> 5 using namespace std; 6 typedef long long LL; 7 8 LL ans[65]; 9 LL fac[65];10 LL a[66],alen;11 void init()12 {13 fac[1]=ans[1]=1;14 fac[2]=ans[2]=2;15 for(int i=3;i<=60;i++)16 {17 fac[i] = 2*fac[i-1]+ans[i-1]-1;18 ans[i]=ans[i-1]*2;19 }20 }21 void get(LL n)22 {23 alen = 0;24 while(n)25 {26 a[++alen]=(n&1);27 n=n>>1;28 }29 }30 LL solve()31 {32 LL sum =0;33 LL k = 0;34 for(int i=alen;i>=1;i--)35 {36 if(a[i]==1)37 {38 sum = sum+fac[i]+k*ans[i];39 k++;40 }41 }42 return sum;43 }44 int main()45 {46 LL n,m;47 init();48 while(scanf("%I64d%I64d",&n,&m)>0)49 {50 get(m);51 LL sum = solve();52 get(n-1);53 sum = sum-solve();54 printf("%I64d\n",sum);55 }56 return 0;57 }
hnu Counting ones 统计1-n 二进制中1的个数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。