"1"的个数
Time Limit:10000MS Memory Limit:65536K
Total Submit:59 Accepted:11
Case Time Limit:1000MS
Description
何老板给你两个非负整数x和y(x<=y),在区间[x,y]中的所有整数，也即是x,x+1,x+2,...,y-1,y这些数字，每个数字对应的二进制数可能包含若干个“1”。总共有多少个“1”呢？
何老板想知道：区间[x,y]中所有数字对应的二进制数中，1总共有多少个？
Input
第一行，两个整数x和y (0<=x<=y<=2,000,000,000)
Output
一行，一个整数，表示所求的结果
Sample Input
1 3
Sample Output
4
Hint
样例说明，在区间[1,3]中共1,2,3三个数字，对应的二进制数分别是1,10,11,数字“1”共出现了4次
Source
改编自NYOJ222
00000
0000 1
000 1 0
000 1 1
00 1 00
00 1 0 1
00 1 1 0
00 1 1 1
0 1 000
0 1 00 1
0 1 0 1 0
0 1 0 1 1
0 1 1 00
0 1 1 0 1
0 1 1 1 0
0 1 1 1 1
1 0000
1 000 1
1 00 1 0
右起第1位，每隔1就会出现 1个1
右起第2位，每隔2就会出现 2个1
……
右起第 k 位，每隔 2^ k-1 就会出现 2^ k-1 个1
区间[0,x]区间中1的个数规律：
右起第2位， 1的个数=((X+1)/4)*2+((X+1)%4)-2(若(x+1)%4<=2则无加号后的一坨)
右起第3位， 1的个数=((X+1)/8)*4 +((X+1)%8)%4 (若(x+1)%8<=4则无加号后的一坨)
……
右起第 k 位，1的个数=((X+1)/2^k)*2^k-1+((X+1)%2^k)%2^k-1(若(x+1)%2^k<=2^k-1则无加号后的一坨)
注意中间结果也会溢出，保险起见都用long long
最终结果是[0,b]中1的数量减去[0,a-1]中1的数量
#include<cstdio>
#include<iostream>
using namespace std;
long long a,b;
long long _c(long long x){
long long p=1,cnt=0;
while((p*2)<=x){
p*=2;
cnt++;
}
return cnt;
}//计算x二进制位数
int main(){
long long i,j,p=1,w1,w2;
cin>>a>>b;
if(a==1||a==0)w1=1;
else w1=_c(a-1)+1;
if(b==1||b==0)w2=1;
else w2=_c(b)+1;
long long ans1=0,ans2=0;
for(i=1;i<=w1;i++){
p*=2;
ans1+=(a/p)*(p/2);
if(i!=1)//以下判断 (x+1)%2^k<=2^k-1的情况（下一个循环一样）
if(a%p>p/2)
ans1+=(a%p)-(p/2);
}
p=1;
for(i=1;i<=w2;i++){
p*=2;
ans2+=((b+1)/p)*(p/2);
if(i!=1)
if((b+1)%p>p/2)
ans2+=((b+1)%p)-(p/2);
}
cout<<ans2-ans1;
}
