编写一种算法，以查找F(n)任何给定值n的从1到n的所有数字中设置为1的位数。
F(n)
复杂度应该是 O(log 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)算法。
O(n)
解决这类问题的方法是写出前几个值，然后寻找模式
数字二进制数位设置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个数字和后8个数字的二进制表示形式完全相同，除了前8个数字0在MSB中 （最高有效位） 有一个，而最后8个1。因此，例如以计算F(12)，我们可以F(7)将8、9、10、11和12中的设置位数相加并添加到其中。但这与0、1、2、3中的设置位数相同。 ，以及4 （即F(4)），每个数字再加上一个！
0
1
F(12)
F(7)
F(4)
＃二进制 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 <-注意最右边的位重复 9 1 001，但现在每个数字都加一个“ 1”！ 10 1 010 11 1011 12 1 100
因此，对于8 <= n <= 15，F(n) = F(7) + F(n-8) + (n-7)。同样，我们可以注意到，对于4 <= n <= 7，F(n) = F(3) + F(n-4) + (n-3); 并且2 <= n <= 3，F(n) = F(1) + F(n-2) + (n-1)。通常，如果我们设置a = 2^(floor(log(n)))，则F(n) = F(a-1) + F(n-a) + (n-a+1)
8 <= n <= 15
F(n) = F(7) + F(n-8) + (n-7)
4 <= n <= 7
F(n) = F(3) + F(n-4) + (n-3)
2 <= n <= 3
F(n) = F(1) + F(n-2) + (n-1)
a = 2^(floor(log(n)))
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)。在上式中，这使我们
a = 2^x
a-1
a/2
F(a-1) = x*a/2 = x*2^(x-1)
F（n）= x * 2 x-1 + F（n-2 x）+（n-2 x +1）
在哪里x = floor(log(n))。计算的每次迭代F本质上都会删除MSB。因此，这是一种O(log(n))算法。
x = floor(log(n))
F
O(log(n))
