设函数 $f(n)$ 返回正整数 $n$ 的二进制表示中 1 的个数. 证明: 若 $n=2k+1$, 则 $f(n)=f(k)+1$.
设函数 $f(n)$ 返回正整数 $n$ 的二进制表示中 1 的个数.
证明: 若 $n=2k+1$, 则 $f(n)=f(k)+1$; 若 $n=2k$, 则 $f(n)=f(k)$.
Hint:
\[k=a_0 2^m+a_1 2^{m-1}+\cdots+a_{m-1}2+a_m\]
\[N=2k+1=a_0 2^{m+1}+a_1 2^{m}+\cdots+a_{m-1} 2^2+ a_m 2+ 1\]
请编程实现.