从1到n中找到所有集合位的总数

Question

从1到n中找到所有集合位的总数

38

编写一个算法，找到 F(n)，即在给定值 n 的情况下，从 1 到 n 中所有数字中设置为 1 的位数。

复杂度应为 O(log n)

例如：

所以

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

我只能设计一个O(n)的算法。

- Fihop

13

如果你能设计一个O(1)的解决方案来计算从1到N中具有特定位设置的数字的数量，那么你就可以设计一个O(log N)的解决方案来计算位总数。 - Jimmy

5

@owlstead 我不知道你的想法，但当我发现一个对我来说有趣的问题时，我会花时间回答它，而不管其他人已经花了多少时间，尤其是像面试题这样的经典难题。我不明白在发帖前为什么要投入这么多时间的大事 - 你不管怎样都得欣赏这些面试题啊，也不是有人要求你替他们做工作...唉... - Assaf Lavie

例如，对于@noMAD，给定n = 3，因为1 = 01，2 = 10，3 = 11，所以从1到3的1位总数为1 + 1 + 2 = 4。希望这样清楚明了。 - Fihop

@gigantt.com 我只是在评论问题的格式，希望能让提问者创建一个不需要翻译的问题，我会自己删除“ur”的编辑，也许提问者是从YouTube学英语的...哦，太晚了。 - Maarten Bodewes

1

可能是在范围内的整数的二进制补码表示中1的数量的重复问题。 - Nemo

显示剩余3条评论

17个回答

8

考虑以下内容：

如果您想要找到从1到14（1110）的所有位集合中的总位数一些观察结果：

第0位（LSB）1位每两位出现一次（垂直查看），因此设置位数= n/2 +（如果n的第0位为1，则为1，否则为0）
第1位：每四位出现两个连续的1（沿着所有数字垂直查看第1位） 第1位位置中的设置位数= (n/4*2)+1（因为第1位是设置的，否则为0）
第2位：4个连续的1s每8位出现一次（这有点棘手） 第2位中的设置位数= (n/8*4)+1（因为第2位设置，否则为0）+ ((n%8)%(8/2)) 最后一个术语是包括在第一个(n/8)位组外的1s的数量（14/8 = 1仅考虑1组即8位中的4个设置位。我们需要包括在最后的14-8 = 6位中发现的1s）
第3位：每16位出现8个连续的1（类似于上面） 第3位位置中的设置位数= (n/16*8)+1（因为第3位是设置的，否则为0）+ ((n%16)%(16/2))

因此，我们对于数字n的每个位进行O(1)计算。一个数字包含log2(n)位。因此，当我们遍历上述所有位置并在每个步骤中添加所有设置的位时，我们可以在O(logn)步骤中得到答案。

- Viv Lingaiah

7

如果n=2^k-1，则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。

- ElKamina

4

快速搜索序列F的值会导致这个整数序列 http://oeis.org/A000788。

我在那里发现了一个公式： a(0) = 0, a(2n) = a(n)+a(n-1)+n, a(2n+1) = 2a(n)+n+1 (由于我只是从oeis复制了公式，所以a与F相同)

这个公式可以用来在log(n)时间内计算a(n)。

这是我的C++代码示例：

memset(cache, -1, sizeof(cache))
cache[0] = 0

int f(int n)
    if cache[n] != -1 return cache[n];
    cache[n] = n % 2 ? (2 * f(n / 2) + n / 2 + 1) : (f(n / 2) + f(n / 2 - 1) + n / 2)

- Pinch

3

这个问题可以使用基于位掩码的DP（动态规划）算法来解决。

自底向上的基本想法是，我们将直接访问当前数字值的set bit数，并通过与 1 的 and 操作来检查该当前数字的最后一位是否被设置。

current_number/2或current_number>>1基本上会删除此current_number的最后一位，因此为了将该位包含在我们的计数中，我们必须使用 & 运算手动检查该数字的最后一位。

以下是计算数字i中set bits数量的表达式 dp[i]=dp[i>>1]+(i&1)

如果您在解决这个问题时仍然遇到困难，那么您可以参考以下视频以获得更好的解释：-

视频链接： https://youtu.be/fCvfud4p6No

- Vaibhav Varshney

2

假设需要 n 个比特位，记为 k。

对于 0,...,2^(k-1)-1 中的每一个数，每一位恰好出现在其中一半的数字中，因此到目前为止有 (k-1)*2^(k-2) 个比特位被设置为 "1"。我们只需要检查大于 2^(k-1)-1 的数字中有哪些比特位被设置了 "1"。
对于那些大于 2^(k-1)-1 的数字，最高位有 n-2^(k-1)-1 个比特位被设置为 "1"。

因此，我们可以得出递归函数：

f(n) = (k-1)*2^(k-2) + n-(2^(k-1)-1) + f(n-(2^(k-1)))
           ^               ^            ^
         first            MSBs        recursive call for 
       2^(k-1)-1                      n-2^(k-1) highest numbers
        numbers

其中，base的值为f(0) = 0和f(2^k) = k*2^(k-1) + 1 [如前所述，我们已经知道了对于2^(k-1)-1有多少位是置位的，我们只需要再加上1 - 即为2^k的最高位]

由于每次迭代发送到f的值至少减半，因此我们总共需要进行O(logn)次迭代。

- amit

@KarolyHorvath：已修复，谢谢。我跟着逻辑追踪走了一遍，没有过多考虑细节，感谢你发现了这个问题！ - amit

1

没问题 ;) 尽管你开始想知道那些点赞者在用什么药物.. :D - Karoly Horvath

-1 这个答案仍然不正确，你仍然缺少一个术语。请查看我的或ElKamina的答案以获取缺失的术语。 - BlueRaja - Danny Pflughoeft

这个新的编辑包括缺失的术语仍然是不正确的 - 例如尝试 F(4)。你会得到 4，而不是正确的答案 5。 - BlueRaja - Danny Pflughoeft

@BlueRaja-DannyPflughoeft：谢谢您，我扩展了基础部分，试图展示我的逻辑并且不应该忽视细节。无论如何，我的回答的主要目的是提供解决这个问题应该考虑的逻辑，它完成了它的目的，考虑到后面的回答。 - amit

显示剩余4条评论

2

这是我的解决方案。时间复杂度：O（Log n）

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

- Akanksha

请提供一些注释以提供有用的澄清。 - Shashankesh Upadhyay

1

简短而精炼！

 public static int countbits(int num){
    int count=0, n;
    while(num > 0){
        n=0;
        while(num >= 1<<(n+1))
            n++;
        num -= 1<<n;
        count += (num + 1 + (1<<(n-1))*n);
    }
    return count;
}//countbis

- kasavbere

@kasavbere，你能解释一下吗？谢谢。 - Fihop

FihopZz，你为什么将 @BlueRaja - Danny Pflughoeft 标记为正确答案而不选择这个呢？ - kasavbere

首先，这是 O((log n)^2) 而不是 O(log n)。 - BlueRaja - Danny Pflughoeft

@BlueRaja - Danny Pflughoeft，你真的相信你的算法实现会比我的更快吗？如果是这样，请展示一下。 - kasavbere

我明白了。我也查过了@BlueRaja-DannyPflughoeft算法，它不是O（log n）。 - tribal

显示剩余4条评论

0

不确定是否晚了回复，但以下是我的发现。

尝试用以下方法解决问题，对于数字N，可以计算每个位号（从LSB到MSB，例如LSB从位号1开始，并且通过下一个位值递增）设置的位数为（N /（2的位号次方）*（2的位号次方-1）+ {（N％（2的位号次方）） - [(2的位号次方-1）- 1]}

已经在C/C ++中编写了递归函数，请检查。我不确定，但我认为它的复杂性是log（N）。传递函数2个参数，要计算位的数字（no）和第二个从LSB开始计数的起始值1。

int recursiveBitsCal(int no, int bitno){
int res = int(no/pow(2,bitno))*int(pow(2,bitno-1));
int rem1 = int(pow(2,bitno-1)) -1;
int rem = no % int(pow(2,bitno));
if (rem1 < rem) res += rem -rem1;
if ( res <= 0 )
    return 0;
else
    return res + recursiveBitsCal(no, bitno+1);
}

- user1138939

0

顺便说一下，这个问题也可以通过查找表的方法来解决。预先计算从0-255的设置位数并存储它。然后，我们可以通过将给定数字分成两个每个8位的部分来计算任何数字中的设置位数。对于每个部分，我们可以在第一步形成的计数数组中查找。例如，如果有一个16位数字，如，

x = 1100110001011100，在这里，设置位数=第一个字节中的设置位数+第二个字节中的设置位数。因此，为了获得第一个字节，

y = (x & 0xff) z = (x >> 8) & (0xff) 总设置位数= count[y] + count[z]

这种方法也将以O(n)运行。

- John Lui

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- BlueRaja - Danny Pflughoeft · Accepted Answer

解决这类问题的方法是写出前几个数值，寻找规律。

数字二进制置位数 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个在最高有效位（MSB）上有一个0，而最后8个则有一个1。因此，例如要计算F(12)，我们可以取F(7)并加上8、9、10、11和12的置位数。但这与计算0、1、2、3和4的置位数是相同的，再加上每个数字额外的一个置位数！

# 二进制 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 <--请注意，右侧的位重复出现

9   1 001     现在每个数字都多了一个“1”！
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*2^(x-1) + F(n-2^x) + (n-2^x+1)
其中x = floor(log(n))。每一轮计算F实际上都会删除MSB（最高有效位）；因此，这是一个O(log(n))的算法。