hpu 问题 H: KACA的杨辉计数

问题 H: KACA的杨辉计数

时间限制: 1 Sec  内存限制: 128 MB

题目描述

KACA突然对杨辉三角起了兴趣，所以他观察了这些神奇的数字。

他发现杨辉三角的第3行有1个偶数，第5行有3个偶数，第6行却只有2个偶数。他发现这些偶数的分布似乎并不规则，所以他准备去数一数偶数的个数。然而他数了好久，发现这是个困难的任务，所以他想要求助ACMer。

输入

多组测试数据。

每一组占一行，只有一个数字n(0<n<10^9)代表第n行。

输出

对于每一组数据，输出一个数字代表杨辉三角第n行的偶数个数。

样例输入

1
3
5

样例输出

0
1
3

思路：找规律，比较坑，统计n-1这个数的二进制形式中的1的个数；

脑补一个：k=__builtin_popcount(n-1);用来搜索二进制中多少个1 ;

#include<iostream>
#include<math.h>
#include<stdio.h>
using namespace std;
typedef long long ll;
ll sdp(ll a)
{
	ll ans=0,j;
	while(a)
	{
		if(a%2==1)
		{
			ans++;
		}
		a>>=1;
	}
	return ans;
}
int main()
{
    ll n,k,m;
    while(scanf("%lld",&n)!=EOF)
	{
		k=sdp(n-1);
        m=pow(2,k);
        printf("%lld\n",n-m);
    }
    return 0;
}