求一段区间中，每个十进制数所对应的二进制数中连续的1的个数之和。
设dp[i][0]代表长度为i的二进制数，首位为0，所含有的连续的1的个数之和。
dp[i][1]代表长度为i的二进制数，首位为1，所含有的连续的1的个数之和。
a: d[i][1]=d[i-1][0]+d[i-1][1]+(1<<(i-2));
b: d[i][0]=d[i-1][0]+d[i-1][1];
这里面有一个需要注意的地方是，假设有一个数字是111，那么它含有2个连续的1，具体体现在
方程上是分两次计算的，一个是a式中的第二项，i位为1，加上长度为i-1的二进制数，首位为1，所含有的连续的1的个数之和，
那么已经算了一次111，另外一个是a式中的第三项，i位和i-1位为1，第i-2位之后任意枚举，这是也计算了一次111.
同理1111也是一样的，初始时d[i][1]=d[i-1][0]，一个是a式中的第二项，i位为1，加上长度为i-1的二进制数，首位为1，所含有的连续的1的个数之和，
那么d[i][1]=d[i-1][0]+2,另外一个是a式中的第三项，i位和i-1位为1，第i-2位之后任意枚举，那么d[i][1]=d[i-1][0]+2+1.
d[i][1]=d[i-1][0]+3;所以这里对长度为3以上的连续的1处理是，通过两种方式，叠加处理。
计算时，从高位到低位，按位枚举，如果当前位是1，说明就是上界，i-1位之后可以任意枚举，如果当前位是0，只能当前缀，此时什么都不加。
#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
using namespace std;
#define maxn 35
LL d[maxn][maxn];
LL digit[maxn];
LL C[maxn][maxn];
void init()
{
memset(d,,sizeof(d));
d[][]=;
for(int i=;i<maxn;i++)
for(int j=;j<=;j++)
{
d[i][]=d[i-][]+d[i-][]+(<<(i-));
d[i][]=d[i-][]+d[i-][];
} }
LL solve(LL x)
{
LL len=,xx=x;
while(x>)
{
digit[++len]=x%;
x>>=;
}
digit[len+]=; //初始化前缀为0，0是没有任何影响的，后面一位可能会用到前面一位
LL ans=;
int flag=;
for(int i=len;i>=;i--) //当前位是1，就是上界，i-1位之后可以任意枚举，否则只能当前缀。
{
if(digit[i]==) //如果当前位是1,i-1位可以任意枚举，如果当前位是0，那么说明是上界
ans+=d[i-][]+d[i-][];
if(flag)
{
if(digit[i]==) //只有前缀不是上界的时候，才可以任意枚举
ans+=flag * ( << (i-)); //i位填0
}
if(flag && (digit[i+]== && digit[i]==))
{
flag++;
}
else if(!flag && digit[i+]== && digit[i]==)
{
flag=;
}
}
return ans;
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t,Case=;
scanf("%d",&t);
init();
LL n=;
while(t--)
{
scanf("%lld",&n);
printf("Case %d: %lld\n",++Case,solve(n+));
}
return ;
}
Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu
Description
A bit is a binary digit, taking a logical value of either 1 or 0 (also referred to as "true" or "false" respectively). And every decimal number has a binary representation which is actually a series of bits. If a bit of a number is 1 and its next bit is also 1 then we can say that the number has a 1 adjacent bit. And you have to find out how many times this scenario occurs for all numbers up to N.
Examples:
Number Binary Adjacent Bits
12 1100 1
15 1111 3
27 11011 2
Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.
Each case contains an integer N (0 ≤ N < 231).
Output
For each test case, print the case number and the summation of all adjacent bits from 0 to N.
Sample Input
7
0
6
15
20
21
22
2147483647
Sample Output
Case 1: 0
Case 2: 2
Case 3: 12
Case 4: 13
Case 5: 13
Case 6: 14
Case 7: 16106127360