hiho一下 第168周 扩展二进制数

8

4

从低位到高位考虑

如果是偶数，最低位必须为0或者1

如果是奇数，最低位必须为1

例如，如果（1000）2=（8）10

最低位两种情况0或者2

如果为0 只需要考虑除了最低位的其他位数，（100）2=（4）10

然后考虑（100）情况与之前（1000）情况一样

如果为2,，那么其他几位的情况则为（100）2-（1）2 =  （11）2=（3）10  为什么是这样的呢？如果最低位为2 那么2*2^0=1*2^1 也就是说，如果我这位是2那么必须 在前面一位抢一个1过来，所以最后一位为2那么（100）2-（1）2 = （11）2   然后（11）2作为继续递归的数

递归最后只有0或者1两种情况，而这两种情况则都返回1种情况表示

如果数字为奇数那么，最低位必须为1

考虑情况，则从(N-1)/2 从偶数情况开始。

#include<stdio.h>
#pragma warning(disable:4996)
int function(int n)
{
	if (n == 0 || n == 1) return 1;

	if (n % 2 == 0)  return function(n / 2) + function(n / 2 - 1);
	else return  function((n - 1) / 2);
}
int main()
{
	int n;
	scanf("%d", &n);
	printf("%d\n", function(n));
	return 0;
}