This was an interview question. The original questions asks:
这是一个面试问题。最初的问题问道:
Given a positive integer N, count the number of 1's in each integer from 0 to N, and return the count in an array of size N+1. Do it in O(n) time.
给定一个正整数N，从0到N对每个整数中的1进行计数，并返回大小为N+1的数组中的计数。在O(n)时间内做。
An Example would be:
一个例子是:
Given 7, then return [0, 1, 1, 2, 1, 2, 2, 3]
给定7，然后返回[0,1,1,2,1,2,2,3]
Of course, the easiest way is to create a loop counting 1's for every integer, but that would be O(kn) time, with k as the size of the integers in bits. So either there's a way to count the number of 1's of an integer in O(1) time, or there's a way to directly generate the count going from 0 to N. I'm sure both methods exist, but can't figure out either.
当然，最简单的方法是为每个整数创建一个计数为1的循环，但是这将是O(kn)时间，k是整数的位的大小。所以，要么有一种方法可以在O(1)时间内计算一个整数的1的个数，要么有一种方法可以直接生成从0到n的数，我确定这两种方法都存在，但也不能算出来。
3 个解决方案
#1
14
Here's a nice little observation that you can use to do this in time O(n). Imagine you want to know how many 1 bits are set in the number k, and that you already know how many 1 bits are set in the numbers 0, 1, 2, ..., k - 1. If you can find a way to clear any of the 1 bits that are set in the number k, you'd get some smaller number (let's call it m), and the number of bits set in k would then be equal to one plus the number of bits set in m. So provided that we can find a way to clear any 1 bit from the number k, we can use this pattern to solve the problem:
这里有一个很好的观察，你可以在O(n)时间内做这个。假设你想知道在数字k中设置了多少位，你已经知道在数字0,1,2中设置了多少位…k - 1。如果你能找到一个方法来清除任何1比特数k中设置,你会得到一些较小的数量(我们称之为m)和设置在k的比特数就等于1 + m的比特数集。所以,我们可以找到一种方法来提供清楚的任何1比特数k,我们可以使用这个模式来解决这个问题:
result[0] = 0 // No bits set in 0
for k = 1 to n:
let m = k, with some 1 bit cleared
result[k] = result[m] + 1
There's a famous bit twiddling trick where
这里有一个著名的旋转技巧。
k & (k - 1)
yields the number formed by clearing the lowest 1 bit that's set in the number k, and does so in time O(1), assuming that the machine can do bitwise operations in constant time (which is usually a reasonable assumption). That means that this pseudocode should do it:
通过清除在k中设置的最低的1位，并在时间O(1)中，假设机器可以在常量时间内进行比特操作(通常是一个合理的假设)，从而产生这个数字。这意味着伪代码应该这样做:
result[0] = 0
for k = 1 to n:
result[k] = result[k & (k - 1)] + 1
This does O(1) work per number O(n) total times, so the total work done is O(n).
它做O(1)对O(n)的功，所以所做的总功是O(n)
Here's a different way to do this. Imagine, for example, that you know the counts of the bits in the numbers 0, 1, 2, and 3. You can use this to generate the counts of the bits of the numbers 4, 5, 6, and 7 by noticing that those numbers have bitwise representations which are formed by taking the bitwise representations of 0, 1, 2, and 3 and then prepending a 1. Similarly, if you then knew the bit counts of 0, 1, 2, 3, 4, 5, 6, and 7, you could generate the bit counts of 8, 9, 10, 11, 12, 13, 14, and 15 by noting that they too are formed by prepending a 1 bit to each of the lower numbers. That gives rise to this pseudocode, which for simplicity assumes that n is of the form 2k - 1 but could easily be adapted for a general n:
这里有一种不同的方法。例如，想象一下，你知道数字0,1,2和3中位数的计数。您可以使用它来生成数字4、5、6和7的位元数，注意到这些数字具有位元表示，这些位元表示是通过取0、1、2和3的位元表示，然后加上1的位元表示形成的。同样,如果你知道一些项0,1,2,3,4,5,6,7,你可以生成项8,9,10,11,12、13、14和15,他们也将形成的1位的数字越低。这就产生了伪代码，为了简单起见，它假设n的形式是2k - 1，但是可以很容易地适应一般的n:
result[0] = 0;
for (int powerOfTwo = 1; powerOfTwo < n; powerOfTwo *= 2) {
for (int i = 0; i < powerOfTwo; i++) {
result[powerOfTwo + i] = result[i] + 1;
}
}
This also runs in time O(n). To see this, notice that across all iterations of all the loops here, each entry in the array is written to exactly once, with O(1) work done to determine which value is supposed to be put into the array at that slot.
它也在O(n)时间内运行。要看到这一点，请注意，在这里所有循环的所有迭代中，数组中的每个条目都被写入一次，完成了O(1)的工作，以确定应该将哪个值放在这个槽位的数组中。
#2
3
We start by manually evaluating the bit count for some small numbers. We note a recurrence relation between the bit count of n and previous results:
我们从手工计算一些小数字的位计数开始。我们注意到n的比特计数与之前的结果之间的递归关系:
n: | count(n): | recurrence:
==============================
0 | 0 |
1 | 1 |
------------------------------
10 | 1 | = count(0) + 1
11 | 2 | = count(1) + 1
------------------------------
100 | 1 | = count(0) + 1
101 | 2 | = count(1) + 1
110 | 2 | = count(10) + 1
111 | 3 | = count(11) + 1
...
Given all bit counts up to 2 = 2¹, we can compute the bit counts up to 4 = 2² by adding 1. Given the bit counts up to 4 = 2², we can compute the bit counts up to 8 = 2³ by adding 1. We generalize this to the k-th power of two and can come up with following exemplary implementation:
考虑到2 = 2¹计数,我们可以计算出钻头数量4 = 2²通过增加1。考虑到数量多达4 = 2²,我们可以计算出一些数到8 = 2³通过增加1。我们将其推广到k次幂2，并可以提出以下示例实现:
// Counts and returns number of enabled bits for integers 0 - n:
function count_bits(n) {
let count = new Array(n);
count[0] = 0;
for (let i = 1, j = 0, k = 1; i <= n; ++i, ++j) {
if (i == 2**k) { // k-th bit of i has been enabled
k++;
j = 0;
}
count[i] = count[j] + 1;
}
return count;
}
// Example:
console.log(count_bits(17).join());We note that all operations involved are incrementing by one, random array access, copying array elements and checking the k-th bit of loop increment i via i == 2**k which could be rewritten as i & 1 << k or - for arbitrary precision of i - as a random array access.
我们注意到,所有操作都是递增,随机数组访问,复制数组元素和检查循环增量的k位我通过我= = 2 * * k可以写成我& 1 < < k或——任意精度的我——作为一个随机访问数组。
Assuming that all primitive operations listed above are in O(1) on our machine, the total runtime complexity is in O(n).
假设上面列出的所有基本操作都在我们的机器上的O(1)中，那么总的运行时复杂性在O(n)中。
This would equally hold for arbitrary precision integers - where incrementing has an average runtime complexity of O(1) - unless copying count[i] = count[j] + 1 takes more than constant time. As this is unfortunately the case for arbitrarily large integers, our runtime complexity is in O(n log(log(n))) as we need O(log(log(n))) space to store the bit count of n.
这同样适用于任意精度整数——其中递增具有O(1)的平均运行时复杂度——除非复制count[i] = count[j] + 1所花费的时间超过常量。不幸的是，对于任意大的整数，我们的运行时复杂度是O(n log(log(n)))，因为我们需要O(log(log(log(n))))空间来存储n的位计数。
#3
3
Much simpler answer:
更简单的回答:
Let x be an array of length k+1 and x[i] has the number of set bits in i.
设x是一个长度为k+1的数组，x[i]在i中有集合位的个数。
x[0] = 0
for i=1:k
x[i] = x[i>>1] + i&1
#1
14
Here's a nice little observation that you can use to do this in time O(n). Imagine you want to know how many 1 bits are set in the number k, and that you already know how many 1 bits are set in the numbers 0, 1, 2, ..., k - 1. If you can find a way to clear any of the 1 bits that are set in the number k, you'd get some smaller number (let's call it m), and the number of bits set in k would then be equal to one plus the number of bits set in m. So provided that we can find a way to clear any 1 bit from the number k, we can use this pattern to solve the problem:
这里有一个很好的观察，你可以在O(n)时间内做这个。假设你想知道在数字k中设置了多少位，你已经知道在数字0,1,2中设置了多少位…k - 1。如果你能找到一个方法来清除任何1比特数k中设置,你会得到一些较小的数量(我们称之为m)和设置在k的比特数就等于1 + m的比特数集。所以,我们可以找到一种方法来提供清楚的任何1比特数k,我们可以使用这个模式来解决这个问题:
result[0] = 0 // No bits set in 0
for k = 1 to n:
let m = k, with some 1 bit cleared
result[k] = result[m] + 1
There's a famous bit twiddling trick where
这里有一个著名的旋转技巧。
k & (k - 1)
yields the number formed by clearing the lowest 1 bit that's set in the number k, and does so in time O(1), assuming that the machine can do bitwise operations in constant time (which is usually a reasonable assumption). That means that this pseudocode should do it:
通过清除在k中设置的最低的1位，并在时间O(1)中，假设机器可以在常量时间内进行比特操作(通常是一个合理的假设)，从而产生这个数字。这意味着伪代码应该这样做:
result[0] = 0
for k = 1 to n:
result[k] = result[k & (k - 1)] + 1
This does O(1) work per number O(n) total times, so the total work done is O(n).
它做O(1)对O(n)的功，所以所做的总功是O(n)
Here's a different way to do this. Imagine, for example, that you know the counts of the bits in the numbers 0, 1, 2, and 3. You can use this to generate the counts of the bits of the numbers 4, 5, 6, and 7 by noticing that those numbers have bitwise representations which are formed by taking the bitwise representations of 0, 1, 2, and 3 and then prepending a 1. Similarly, if you then knew the bit counts of 0, 1, 2, 3, 4, 5, 6, and 7, you could generate the bit counts of 8, 9, 10, 11, 12, 13, 14, and 15 by noting that they too are formed by prepending a 1 bit to each of the lower numbers. That gives rise to this pseudocode, which for simplicity assumes that n is of the form 2k - 1 but could easily be adapted for a general n:
这里有一种不同的方法。例如，想象一下，你知道数字0,1,2和3中位数的计数。您可以使用它来生成数字4、5、6和7的位元数，注意到这些数字具有位元表示，这些位元表示是通过取0、1、2和3的位元表示，然后加上1的位元表示形成的。同样,如果你知道一些项0,1,2,3,4,5,6,7,你可以生成项8,9,10,11,12、13、14和15,他们也将形成的1位的数字越低。这就产生了伪代码，为了简单起见，它假设n的形式是2k - 1，但是可以很容易地适应一般的n:
result[0] = 0;
for (int powerOfTwo = 1; powerOfTwo < n; powerOfTwo *= 2) {
for (int i = 0; i < powerOfTwo; i++) {
result[powerOfTwo + i] = result[i] + 1;
}
}
This also runs in time O(n). To see this, notice that across all iterations of all the loops here, each entry in the array is written to exactly once, with O(1) work done to determine which value is supposed to be put into the array at that slot.
它也在O(n)时间内运行。要看到这一点，请注意，在这里所有循环的所有迭代中，数组中的每个条目都被写入一次，完成了O(1)的工作，以确定应该将哪个值放在这个槽位的数组中。
#2
3
We start by manually evaluating the bit count for some small numbers. We note a recurrence relation between the bit count of n and previous results:
我们从手工计算一些小数字的位计数开始。我们注意到n的比特计数与之前的结果之间的递归关系:
n: | count(n): | recurrence:
==============================
0 | 0 |
1 | 1 |
------------------------------
10 | 1 | = count(0) + 1
11 | 2 | = count(1) + 1
------------------------------
100 | 1 | = count(0) + 1
101 | 2 | = count(1) + 1
110 | 2 | = count(10) + 1
111 | 3 | = count(11) + 1
...
Given all bit counts up to 2 = 2¹, we can compute the bit counts up to 4 = 2² by adding 1. Given the bit counts up to 4 = 2², we can compute the bit counts up to 8 = 2³ by adding 1. We generalize this to the k-th power of two and can come up with following exemplary implementation:
考虑到2 = 2¹计数,我们可以计算出钻头数量4 = 2²通过增加1。考虑到数量多达4 = 2²,我们可以计算出一些数到8 = 2³通过增加1。我们将其推广到k次幂2，并可以提出以下示例实现:
// Counts and returns number of enabled bits for integers 0 - n:
function count_bits(n) {
let count = new Array(n);
count[0] = 0;
for (let i = 1, j = 0, k = 1; i <= n; ++i, ++j) {
if (i == 2**k) { // k-th bit of i has been enabled
k++;
j = 0;
}
count[i] = count[j] + 1;
}
return count;
}
// Example:
console.log(count_bits(17).join());We note that all operations involved are incrementing by one, random array access, copying array elements and checking the k-th bit of loop increment i via i == 2**k which could be rewritten as i & 1 << k or - for arbitrary precision of i - as a random array access.
我们注意到,所有操作都是递增,随机数组访问,复制数组元素和检查循环增量的k位我通过我= = 2 * * k可以写成我& 1 < < k或——任意精度的我——作为一个随机访问数组。
Assuming that all primitive operations listed above are in O(1) on our machine, the total runtime complexity is in O(n).
假设上面列出的所有基本操作都在我们的机器上的O(1)中，那么总的运行时复杂性在O(n)中。
This would equally hold for arbitrary precision integers - where incrementing has an average runtime complexity of O(1) - unless copying count[i] = count[j] + 1 takes more than constant time. As this is unfortunately the case for arbitrarily large integers, our runtime complexity is in O(n log(log(n))) as we need O(log(log(n))) space to store the bit count of n.
这同样适用于任意精度整数——其中递增具有O(1)的平均运行时复杂度——除非复制count[i] = count[j] + 1所花费的时间超过常量。不幸的是，对于任意大的整数，我们的运行时复杂度是O(n log(log(n)))，因为我们需要O(log(log(log(n))))空间来存储n的位计数。
#3
3
Much simpler answer:
更简单的回答:
Let x be an array of length k+1 and x[i] has the number of set bits in i.
设x是一个长度为k+1的数组，x[i]在i中有集合位的个数。
x[0] = 0
for i=1:k
x[i] = x[i>>1] + i&1