查找从1到n的总位数

Question

编写一个算法来查找F(n)设置为1的位数,对于任何给定的n值,从1到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)算法.

Answer 1

解决这些问题的方法是写出前几个值,然后寻找一个模式

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个和后8个数字的二进制表示是完全相同的,除了前8个0在MSB中有一个(最重要的位),而最后8个有一个1.因此,例如,为了计算F(12),我们可以F(7)将8,9,10,11和12中的设置位数加上并加上它.但这与0,1,2,3中的设置位数相同和4 (即F(4)),每个数字加一个!

#    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 <= 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).在上面的等式中,这给了我们

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

哪里x = floor(log(n)).每次迭代计算F都将基本上删除MSB; 因此,这是一种O(log(n))算法.

Answer 2

如果 n= 2^k-1, then F(n)=k*(n+1)/2

对于一般的n,让m是最大数,使得m = 2^k-1和m<=n.F(n) = F(m) + F(n-m-1) + (n-m).

转弯条件:F(0)=0和F(-1)=0.

Answer 3

考虑以下：

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

如果您想找到从 1 到 14 (1110) 个设置位的总数，请注意以下几点：

1. 0th位（LSB）1位每两位出现一次（垂直看）所以设置位的数量= n/2 +（1如果n's 0th bit is 1其他0）
2. 第 1 位：每四位出现 2 个连续的 1（沿所有数字垂直查看第 1 位）1st位位置中的设置位数= (n/4 *2) + 1（因为1st位是一个设置，否则0）
3. 2nd位：4连续1s出现每一位8（这个有点棘手）第二个位置的设置位数= (n/8*4 )+ 1（因为2nd位已设置，否则0）+ ((n%8)%(8/2)) 最后一项是包括1s在第一(n/8)组位之外的数量（14/8 =1只考虑1组即以4位为8单位设置位。我们需要1s在最后一位中包含found 14-8 = 6）
4. 3rd位：8连续的 1 出现在每一位16（类似于上面）3rd位置的设置位数= (n/16*8)+1（因为3rd设置了位，否则0）+ ((n%16)%(16/2))

所以我们O(1)对数字的每一位进行计算n。一个数字包含log2(n)位。所以当我们反复在上面的所有位置n，并在每个步骤中添加的所有设置位，我们得到的答案O(logn)步骤