写一个算法来找到 F（N）从1设置为1，在所有数字为n的n个任意给定值的位数。

Write an algorithm to find F(n) the number of bits set to 1, in all numbers from 1 to n for any given value of n.

复杂性应该是 O（log n）的

例如：

1: 001
2: 010
3: 011
4: 100
5: 101
6: 110

于是

F(1) = 1,  
F(2) = F(1) + 1 = 2,
F(3) = F(2) + 2 = 4,
F(4) = F(3) + 1 = 5,
etc.

我只能设计一个 O（N）算法。

推荐答案

要解决这类问题的方法是写出来的前几个值，并寻找一个模式

The way to solve these sorts of problems is to write out the first few values, and look for a pattern

Number  binary   # bits set   F(n)
1       0001     1            1
2       0010     1            2
3       0011     2            4
4       0100     1            5
5       0101     2            7
6       0110     2            9
7       0111     3            12
8       1000     1            13
9       1001     2            15
10      1010     2            17
11      1011     3            20
12      1100     2            22
13      1101     3            25
14      1110     3            28
15      1111     4            32

这需要一些盯着的，但有些人认为你注意到前8的二进制再presentations最后8个数字是完全一样的，除了第8有一个 0 在MSB的（最显著位）的，而最后8有一个 1 。因此，例如计算 F（12），我们可以只取 F（7），并添加到它的组比特中8号，9，10，11和12。但是，这是相同的设定位的0的数，1，2，3和4的（即 F （4））的，再加上多了一个为每个号码！

It takes a bit of staring at, but with some thought you notice that the binary-representations of the first 8 and the last 8 numbers are exactly the same, except the first 8 have a 0 in the MSB (most significant bit), while the last 8 have a 1. Thus, for example to calculate F(12), we can just take F(7) and add to it the number of set bits in 8, 9, 10, 11 and 12. But that's the same as the number of set-bits in 0, 1, 2, 3, and 4 (ie. F(4)), plus one more for each number!

#    binary
0    0 000
1    0 001
2    0 010
3    0 011
4    0 100
5    0 101
6    0 110
7    0 111

8    1 000  <--Notice that rightmost-bits repeat themselves
9    1 001     except now we have an extra '1' in every number!
10   1 010
11   1 011
12   1 100

因此​​， 8示= N＆LT; = 15 ， F（N）= F（7）+ F（N-8 ）+（N-7）。同样地，我们可以注意到，对于 4℃= N＆LT; = 7 ， F（N）= F（3）+ F（N- 4）+（N-3）;和 2'; = N＆LT; = 3 ， F（N）= F（1）+ F（N-2）+（N -1）。一般情况下，如果我们设置 A = 2 ^（楼（的log（n））），然后 F（N）= F（A-1 ）+ F（NA）+（N-A + 1）

Thus, for 8 <= n <= 15, F(n) = F(7) + F(n-8) + (n-7). Similarly, we could note that for 4 <= n <= 7, F(n) = F(3) + F(n-4) + (n-3); and for 2 <= n <= 3, F(n) = F(1) + F(n-2) + (n-1). In general, if we set a = 2^(floor(log(n))), then F(n) = F(a-1) + F(n-a) + (n-a+1)

这并不完全给我们一个 O（log n）的算法;然而，这样做很容易。如果 A = 2 ^ X ，然后记在上面的表 A-1 ，第一位被设置正是 A / 2 倍，第二位设置正是 A / 2 倍，第三位......所有一直到第X个位。因此， F（A-1）= X * A / 2 = X * 2 ^（X-1）。在以上等式中，这为我们提供了

This doesn't quite give us an O(log n) algorithm; however, doing so is easy. If a = 2^x, then note in the table above that for a-1, the first bit is set exactly a/2 times, the second bit is set exactly a/2 times, the third bit... all the way to the x'th bit. Thus, F(a-1) = x*a/2 = x*2^(x-1). In the above equation, this gives us

F(n) = x*2x-1 + F(n-2x) + (n-2x+1)

其中， X =地板（的log（n））。计算每次迭代 F 将从根本上去除最高位;因此，这是一个 O（日志（N））算法。

Where x = floor(log(n)). Each iteration of calculating F will essentially remove the MSB; thus, this is an O(log(n)) algorithm.