acdream 1154 Lowbit Sum
先贴代码，以后再写题解。。。
首先，直接枚举肯定是会超时的，毕竟n就有10^9那么多。。。
对于每个数，我们先把它转化为二进制；例：21-->10101；
对于00001~10101，可以分为几个部分：
00001~10000；
10001~10100；
10101
因为对于每个数，从最右边的1截断，于是就可以理解为为：
00001~10000:；
001~100；
1；
设s[i]为二进制从右边数第 i+1 个数为1 （且其他数都为0）的lowbit sum；
则 s[i]=s[i-1]*2+2^i-2^(i-1)；
则lowbit sum（21）=s[0]+s[2]+s[4];
设i=4；即 10000；
可分为 ：
00001~01000 s[i-1];
01001~01111 s[i-1]-lowbit(01000)=s[i-1]-2^(i-1); （从最右边的1截断，即可理解为 00001~00111 ）
10000 lowbit(10000)=2^i;
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 using namespace std; 6 7 typedef long long ll; 8 9 ll s[100]; 10 11 ll init (int n){ 12 if (s[n]) 13 return s[n]; 14 s[n]=init (n-1)*2-(1<<(n-1))+(1<<n);//cout<<s[n]<<" "; 15 return s[n]; 16 } 17 18 int main (){ 19 int n; //while (cin>>n&&n) cout<<(1024>>n)<<endl; 20 ll ans=1; 21 int temp=2; 22 memset (s,0,sizeof s); 23 s[0]=1; 24 init (30); //for (int i=0;i<=30;i++) cout<<s[i]<<" "; 25 while (~scanf ("%d",&n)){ 26 ans=0; 27 for (int i=0;n&&i<30;i++) { 28 if (n&1) 29 ans+=s[i];//cout<<ans<<endl; 30 n>>=1; 31 //n/=2; 32 } 33 printf ("%lld ",ans); 34 } 35 return 0; 36 }