ACdream OJ 1154 Lowbit Sum

題目連結~~>

做題感悟：這題是昨天ACdream的手速賽的一題，開始時直接進不去，不對是一直進不去，後來從群裡讀了D題的題意，打了一下表發現有規律，但是為時已晚樓管要關門了隻好先放着了，今天寫了一下成功AC。

解題思路：

                (1)  隻要自己列舉一下前 15 個左右的數的二進制，就會發現： 1 每 2 個數出現一次 ， 2 每  4 個數出現一次， 4 每 8 個數出現一次，隻要 1<< i 的出現次數的循環為 1<<(i+1) ，這樣把所有的加起來求和便可。

                (2) 網上挖掘的：規律題：如果熟悉樹狀數組的話說不定可以直接得到答案，如果不熟悉的話可以打表看一下，可以發現前幾項lowbit 大概是 1 ， 2 ， 1 ， 4 ， 1， 2， 8......... 發現奇數項都是 1 ， 這是lowbit 運算導緻的，然後偶數項提出來，如果除以 2 ，發現就會變成 1 ， 2 ， 1， 4 .......... 然後就有感覺是疊代了，最終得到公式 : ans ( x ) = 2 * ans( x / 2 ) + x/2 + (x&1) ;

代碼：

#include<stdio.h>
#include<cmath>
#include<string.h>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stdlib.h>
#define INT long long int
using namespace std ;
const int INF = 99999999 ;
const int MY = 20 + 10 ;
const int MX = 62500 + 10 ;
INT n ;
int main()
{
    while(~scanf("%lld",&n))
    {
        // 2 倍循環
        INT sum=0,x=0,m ;
        sum+=n/2+n%2 ; // 先計算 1 的個數
        for(int i=1 ;   ;i++)
        {
            m=n-(1<<i) ;
            if(m<0)  break ;
            sum+=((m/(1<<(i+1)))+1)*(1<<i) ;
        }
        cout<<sum<<endl ;
    }
    return 0 ;
}