HihoCoder1410 Powers of Two

传送门：HihoCoder1410 Powers of Two

题目描述

测试样例

Sample Input
7Sample Output
2

题目大意

??给定一个正整数N，可以将N表示为2的几个正或负幂的和。例如：7=2²+2¹+2⁰或7=2³+(-2)⁰。
求最少的加数个数。

AC代码

#include<cstdio>
#include<algorithm>
using namespace std;
int fun(int n)
{int m=1;while(m<n)m<<=1;if(m==n)return 1;int t=min(n-(m>>1),m-n); // 选出差较小的return fun(t)+1;
}
int main()
{int n;scanf("%d",&n);printf("%d\n",fun(n));return 0;
}