ZOJ - Summer 2018 - Contest 2 by Astolfo - Problems - 1002: Hazard and The Triangle

Hazard and The Triangle

Time Limit: 1 Second      Memory Limit: 262144 KB      Score: 1

I'm Eden Hazard,the so-called "superb passer". In a match in the group stage,three players surrounding me tried to block my advance,which,of course,failed. However,at that moment,they formed a triangle,which reminds me of an interesting problem about Pascal's triangle.

The first element and the last element of each row in a Pascal's Triangle is , and the -th element of the -th row equals to the sum of the -th and the (-)-th element of the (-)-th row.Here's an example.

I wonder how many elements in the -th row of a Pascal's Triangle are odd numbers.

Input

There are several test cases (no more than ).

There is an integer  in each case.

Output

For each test case, output the number of odd numbers in the -th line.

Input

3
4
5

Output

2
4
2

Output

解题思路：杨辉三角第 n 行的奇数个数，2^( n-1 中二进制 1 的个数)。

AC 代码

#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll numOf1(ll n)
{
    ll cnt = 0;
    while(n){
        cnt++;  // 只要 n 不为 0,则其至少有一个 1
        n = n & (n - 1);
    }
    return cnt;
}
int main()
{
    ll n;
    while(~scanf("%lld",&n))
    {
        if(n<=0) puts("0");
        else cout<<(1LL<<NumberOf1(n-1))<<endl;
    }
    return 0;
}