Как подсчитать количество 1 битов, установленных в 0, 1, 2,..., n в O (n) времени?

Это был вопрос интервью. Оригинальные вопросы задают:

Учитывая положительное целое число N, подсчитайте число 1 в каждом целом от 0 до N и верните счет в массиве размером N + 1. Сделайте это в O (n) времени.

Пример:

Учитывая 7, верните [0, 1, 1, 2, 1, 2, 2, 3]

Конечно, самый простой способ - создать подсчет цикла 1 для каждого целого числа, но это будет O (kn) время, где k - размер целых чисел в битах. Таким образом, либо существует способ подсчета числа 1 целого числа в O (1), либо есть способ напрямую генерировать счетчик, идущий от 0 до N. Я уверен, что оба метода существуют, но не могут понять либо.

Ответ 1

Вот небольшое замечание, которое вы можете использовать для этого во времени O (n). Представьте, что вы хотите знать, сколько 1 бита установлено в числе k, и что вы уже знаете, сколько 1 бита установлено в числах 0, 1, 2,..., k - 1. Если вы можете найти способ чтобы очистить любой из 1 битов, которые установлены в числе k, вы получите меньшее число (позвоните ему m), а количество бит, установленное в k, будет равно единице плюс число бит, установленных в м. Таким образом, при условии, что мы можем найти способ удалить любой 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

Там знаменитый бит-трюк, где

 k & (k - 1)

дает число, сформированное путем сброса младшего 1 бита, установленного в числе k, и делает это во времени O (1), считая, что машина может выполнять побитовые операции в постоянное время (что обычно является разумным предположением). Это означает, что этот псевдокод должен сделать это:

result[0] = 0
for k = 1 to n:
    result[k] = result[k & (k - 1)] + 1

Это означает, что O (1) работает на число O (n) общего времени, поэтому общая работа выполнена O (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 имеет вид 2 ^k - 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;
    }
}

Это также выполняется во времени O (n). Чтобы увидеть это, обратите внимание, что на всех итерациях всех циклов здесь каждая запись в массиве записывается ровно один раз, а O (1) выполняется, чтобы определить, какое значение должно быть помещено в массив в этом слоте.

Ответ 2

Сначала мы начинаем вручную оценивать количество бит для некоторых небольших чисел. Отметим рекуррентное соотношение между количеством бит 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
...

Учитывая, что все бит подсчитывается до 2 = 2¹, мы можем вычислить количество бит до 4 = 2², добавив 1. Учитывая, что бит подсчитывается до 4 = 2², мы можем вычислить количество бит до 8 = 2³ на добавив 1. Мы обобщаем это на k-ю степень двух и можем придумать следующую примерную реализацию:

// 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());

Ответ 3

Более простой ответ:

Пусть x - массив длины k + 1, а x [i] имеет число битов набора в i.

x[0] = 0
for i=1:k
    x[i] = x[i>>1] + i&1