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 1adjacent 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 < 2³¹).

Output

For each test case, print the case number and the summation of all adjacent bits from 0 to N.

思路与1140相似

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; typedef long long ll; vector
      
        digit; int n; ll pow2[32]; ll dp[32][2]; ll getSum(int pos){ ll res = 0; for(int i = pos; i >= 0; i--){ res *= 2; res += digit[i]; } return res+1; } ll dfs(int pos,int pre,int zero,int done){ if(pos==-1) return 0; if(!zero && !done && ~dp[pos][pre]) return dp[pos][pre]; ll res = 0; int end = done digit[pos]:1; for(int i = 0; i <= end; i++){ if(pre==1&&i==1){ if(done&&i==end){ res += getSum(pos-1); }else{ res += pow2[pos]; } } res += dfs(pos-1,i,zero&&i==0,done&&i==end); } if(!done && !zero) dp[pos][pre] = res; return res; } ll solve(ll x){ digit.clear(); while(x){ digit.push_back(x%2); x /= 2; } return dfs(digit.size()-1,0,1,1); } void init(){ pow2[0] = 1; for(int i = 1; i <= 31; i++){ pow2[i] = pow2[i-1]*2; } memset(dp,-1,sizeof dp); } int main(){ int ncase,T=1; cin >> ncase; init(); while(ncase--){ cin >> n; printf("Case %d: %lld\n",T++,solve(n)); } return 0; }