c - f(n) = n + f(floor(n/2)) 是否存在封闭形式？

Question

我有以下递归公式：

  f(0) = 0
  f(1) = 1
  f(n) = n + f(floor(n/2))

可以用代码表示为：

  int f(int n) {
    int s = 0;
    for (; n; n >>= 1)
      s += n;
    return s;
  }

是否有一种封闭形式可以让我f(n)一步计算？

如果没有，我还能做些什么来f(n)更快地计算吗？

Answer 1

在OEIS上搜索给出了这个系列：

A005187: a(n) = a([n/2]) + n; 1/sqrt(1-x) 展开的分母也是 2^a(n)；还有 2n - 2n 的二进制扩展中 1 的数量。

所以第二部分给出了 的公式2*n - bitcount(2*n)。您可以使用一些有效的位计数实现来计算它，例如 gcc 的__builtin_popcount.

Answer 2

还要注意 bitcount(2n) = bitcount(n)

推导如下：

让 n = sum(b[j] 2^j) for j=0...N

假设 b[N] = 1。定义

(a) F(n) = n + F(n/2) = n+n/2+n/4+... = 2 * n - (1/2 + 1/4 + ... 1/2 ^N) 按几何级数

这个函数 F 是一个实值函数。现在对于设置的每个位 b[j]，floor 函数减去 b[j](sum(1/2^k, k=1...j+1))。这是因为它实际上取出了 1/2，但是随着它的传播，随后的术语被添加了。

所以

(b) f(n) = floor(F(n)-sum(b[j] sum(1/2^k, k=1...j+1)，对于 j=0...N-1 )

将 (a) 代入 (b) 给出

(c) f(n) = floor(2n - (1/2 + 1/4 + ... 1/2^(N+1)) - sum (b[j] (sum(1/2^(k ), 对于 k=1..j+1), 对于 j=0...N-1))

好的，这部分很酷！观察当 b[j] 为 1 时，如果从粗体表达式中偷偷 1/2^(j+1) 到斜体的 sum 中，sum 里面的 sum 变成 1，这意味着

b[j] (sum(1/2^(k), for k=1..j+1), for j=0...N-1) = sum(b[j], for j=0. ..N-1)

所以方程（c）简化为

f(n) = floor(2*n - sum(b[j], for j=0...N-1) - remainder)
f(n) = 2*n - bitcount(n-2^N) - 1    ; because remainder >0 and <1
f(n) = 2*n - bitcount(n)            ; b[N]=1, so bitcount(n)=bitcount(n-2^N)+1

其中余数是 sum(1/2^j, j=1,..N+1 and b[j-1]==0)，但这个总和总是 >0 且 < 1（最多为 1-1 /2^(N+2) 和至少 1/2^(N+1)，所以它可以作为 -1 移出地板。

还要注意 bitcount 运行时间可以等于设置的位数（http://gurmeet.net/puzzles/fast-bit-counting-routines/）。一些处理器将其作为单独的指令。

不确定乳胶是否在这里有效，但没有数学符号会很痛苦。我一直不得不编辑它，因为看起来总是有问题。

Answer 3

The function grows as follows - 

f(n) = n + f(n/2)
f(n/2) can be further simplified as - 

n/2 + f(n/4)

If we keep doing this, we will see n + n/2 + n/4 + n/8.....upto log n terms
= n (1 + 1/2 + 1/4 + 1/8...log n terms)
= n[ (1- (1/2)^log n)/(1/2)]
= 2n [1 - (1/2)^log n]

The term (1/2)^log n will become smaller and smaller as n increases, therefore the 2n term dominates. Hence f(n) belongs to big Theta (n)