ACM_lowbit

lowbit

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

long long ans = 0;
for(int i = 1; i < = n; i ++)
    ans += lowbit(i)
lowbit(i)的意思是将i轉化成二進制數之後，隻保留最低位的1及其後面的0，截斷前面的内容，然後再轉成10進制數
比如lowbit(7),7的二進制位是111，lowbit(7) = 1,6 = 110(2),lowbit(6) = 2,同理lowbit(4) = 4,lowbit(12) = 4,lowbit(2) = 2,lowbit(8) = 8,每輸入一個n，求ans
      

Input:

多組資料，每組資料一個n(1 <= n <= 5*10^8)      

Output:

每組資料輸出一行，對應的ans.      

Sample Input:

1
2
3
      

Sample Output:

1
3
4
解題思路：lowbit函數來源于樹狀數組，其含義是得到該數的二進制從右往左第一個非0位所表示的10進制數。這道題直接暴力枚舉相加肯定是會逾時的，是以需要推導一下有無求和公式。首先簡單暴力輸出前1000個數的lowbit值，其中int lowbit（int x）{return x&-x;}發現有如下規律：
1   3   5   7   9 ...... lowbit(i)=20
2   6  10  14  18 ......lowbit(i)=21
4  12  20  28  36 ......lowbit(i)=22
8  24  40  56  72 ......lowbit(i)=23
從上表中，可以知道每一行的lowbit值是相等的。
拿n=9舉個栗子：第一行有5個數，ans+=5*1,ans=5;第二行中有2個數，ans+=2*2,ans=9;第三行中有1個數，ans+=1*4,ans=13;第四行中有1個數，ans+=1*8,ans=21;求和完畢。現在的問題就是求解每一行有多少個lowbit值相等的數字，從所舉栗子來看，假設p是所在行的lowbit值的指數，每一行有mp個數（數字的大小在n的範圍内），則p=0時，m0=(9-20)/(20+1)+1=8/2+1=5；當p=1時，m1=(9-21)/(21+1)+1=7/4+1=2；當p=2時，m2=(9-22)/(22+1)+1=5/8+1=1；當p=3時，m3=(9-23)/(23+1)+1=1/16+1=1。而(int)log2(9)=3，即剛好枚舉到p=3這一行，是以每一行在n的範圍内相同lowbit值的數字求和公式為∑((n-2i)/(2i+1)+1)*2i,OK，推導完畢！
AC代碼：      

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int n;
 6     while(cin>>n){
 7         int p=log2(n);long long ans=0;
 8         for(int i=0;i<=p;++i)
 9             ans+=((n-(1<<i))/(1<<(i+1))+1)*(1<<i);
10         cout<<ans<<endl;
11     }
12     return 0;
13 }      

 注意：左移<<運算符的優先級比雙目運算符-還低，是以要加括号。

轉載于:https://www.cnblogs.com/acgoto/p/9033817.html