和二进制有关的面试题

baindeglace

最近在准备工作面试， 看了不少有趣的数学题。再来分享一道。
考虑这样一个函数:
$f : N \to N$, $f(n)$为$n$的二进制表示中$11$出现的次数，
比如： $(11)_{10} = (1011)_2$一共出现了$1$次 $11$. 于是$f(11) = 1$.
再比如：$(15)_{10} = (1111)_2$一共出现了$3$次 $11$. 于是$f(15) = 3$.

问：
$f(64)$=?
$\sum_{i = 0}^64 f(i)$ = ?
$\sum_{i = 0}^96 f(i)$ = ?
更一般的
$\sum_{i = 0}^{2^n} f(i)$ = ?
$\sum_{i = 0}^{2^n + 2^{n-1}} f(i)$ = ?

zeroieme

临睡前瞄一眼
数列递归公式——数列通项公式——数列和公式

mathe

这个不能算算法题，是纯粹的数学题。属于计数问题，可以直接求出公式解。
由于显然$f(2^n)=0$,所以我们首先需要计算\(\sum_{i=0}^{2^n-1}f(i)\)
我们把这$2^n$个数都看成n比特二进制数进行运算并不影响结果，
这$2^n$个数中第h和第h+1比特都是1的数有$2^{n-2}$个，所以马上有
\(\sum_{i=0}^{2^n-1}f(i)=(n-1)2^{n-2}\)
而
\(\sum_{i=2^n}^{2^n+2^{n-1}-1}f(i)\)中，类似前面算法可以先得出后面n-2个相邻比特贡献了$(n-2)2^{n-3}$
而最高两比特贡献了$2^{n-2}$,所以结果应该是\(\sum_{i=2^n}^{2^n+2^{n-1}-1}f(i)=n2^{n-3}\)