将n作为位，将s作为集合，计算所有数字的总位集合数

Question

[在编程黑客马拉松期间，我想到一个问题，写一个函数对所有数字中的总位集合进行计数，考虑将n作为位，将s设置为集合，如果我将n传递为3，则计数集为7为：

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

我对3套代码的正确评估如下，但是它失败了4位，我不知道为什么，尽管按照我的观点，我认为这是正确的：

public int countSetBits(int n, int set){
    while(n>0){
        int i = (int)(Math.log10(n)/Math.log10(2));
        set = set + Math.pow(2, i-1) + i;
        set = set + n - Math.pow(2, i) + 1;
        n = n - Math.pow(2, i);
    }
    return set;
}

但是，在自动测试用例中，这对于4位检查失败。什么可能是错误的，并做了改进才能通过所有如果回答，请解释您为何如此的理性思考过程。

Answer 1

我不知道您的方法有什么问题，但是这是我的，也许可以帮助您了解您的方法：

[P(n) =用n位写入的数字中设置为1的位数。

对于1位，我们有2个可能的数字，0和1，所以P(1) = 1对于2位，我们具有来自上一步的所有数字，其前面带有0，因此为00和01，并且具有来自上一步的所有数字，其具有1之前为，因此为10和11。第0位sum（（0 0] >，0 1，1 0，1 1）是已知的，它是P（1），我们有两次。我们需要计算第一位的总和。我们可以看到我们有2个，总计P(2) = 2 * P(1) + 2 = 2 * 1 + 2 = 4。

让我们更进一步，看看模式。对于3位数字，我们有上一步中的数字，前值为0（000，001，010，011），它们的位总和为P（2），而上一步中的数字为1，前值为（100，101， 110，111）。它们的最后两位的位总和为P（2），现在我们在第二个位置将4个附加位设置为1（从右到左计算，如2的幂）。哈！因此，之前出现的1是每一步的两倍！

所以公式如下：P(1) = 1，如前所述

P(n) = 
P(n - 1) // bits sum for the numbers from previous step which have a 0 before
+ 2^(n - 1) // the 1s that appear in front of the numbers from previous step
+ P(n - 1) // bits sum for the numbers from previous step which now have a 1 before
所以最终公式是P(n) = 2 * P(n - 1) + 2^(n - 1)

可视化，它像这样：

n = 1
|  0  |
|  1  |
=======
| P1  | 

n = 2
|  0  ||  0  |
|  0  ||  1  |
== 0 === P1 ==
|  1  ||  0  |
|  1  ||  1  |
= 2^1 === P1 =

n = 3
|  0  ||  0  ||  0  |
|  0  ||  0  ||  1  |
|  0  ||  1  ||  0  |
|  0  ||  1  ||  1  |
== 0 ====== P2 ======
|  1  ||  0  ||  0  |
|  1  ||  0  ||  1  |
|  1  ||  1  ||  0  |
|  1  ||  1  ||  1  |
= 2^2 ====== P2 =====

n = 4
|  0  ||  0  ||  0  ||  0  |
|  0  ||  0  ||  0  ||  1  |
|  0  ||  0  ||  1  ||  0  |
|  0  ||  0  ||  1  ||  1  |
|  0  ||  1  ||  0  ||  0  |
|  0  ||  1  ||  0  ||  1  |
|  0  ||  1  ||  1  ||  0  |
|  0  ||  1  ||  1  ||  1  |
== 0 ======= P3 ============
|  1  ||  0  ||  0  ||  0  |
|  1  ||  0  ||  0  ||  1  |
|  1  ||  0  ||  1  ||  0  |
|  1  ||  0  ||  1  ||  1  |
|  1  ||  1  ||  0  ||  0  |
|  1  ||  1  ||  0  ||  1  |
|  1  ||  1  ||  1  ||  0  |
|  1  ||  1  ||  1  ||  1  |
= 2^3 ======= P3 ===========
public int countSetBits(int n) {
  if (n == 1) return 1;
  return 2 * countSetBits(n - 1) + (1 << n - 1);
}