Counting Bits

Q: Какова временная сложность Counting Bits?

Лучшее решение работает за время O(n): каждая из n+1 записей получается из предыдущей записи одним сложением. Подсчёт битов каждого числа по отдельности занимает O(n log n). Оба решения используют O(1) дополнительной памяти помимо выходного массива.

Q: Существует ли ещё одна рекуррентная формула с временной сложностью O(n) для подсчёта битов?

Да. i & (i-1) сбрасывает младший установленный бит в i , поэтому bits[i] = bits[i & (i-1)] + 1 для каждого i , равного 1 или больше. Для 12 ( 1100 ) 12 & 11 равно 8 ( 1000 ), в котором одна единица, поэтому в 12 их две.

Q: Могу ли я использовать встроенную функцию подсчёта единичных битов?

Вызов этой функции для каждого числа, например Integer.bitCount в Java или __builtin_popcount в C и C++, даёт правильный ответ. На собеседованиях обычно просят решить задачу без неё, потому что суть задачи — повторно использовать уже вычисленные ответы.

ЛегкоБитовые операции Динамическое программирование

+10

Для заданного целого числа n, которое не меньше 0, верните массив из n+1 элементов, где элемент i — это количество единиц в двоичной записи числа i для каждого i от 0 до n.

Функция

countBits(n: integer) → integer-array

ninteger: последнее число для отсчёта, 0 или больше
Возвращаетinteger-array: массив из n+1 счётчиков, где элемент i — это количество битов 1 в i

Ограничения

0 ≤ n ≤ 2 × 10⁴

Примеры

Ввод: n = 2
Вывод: [0, 1, 1]
Пояснение: В двоичной системе 0 — это 0, 1 — это 1, а 2 — это 10: ни одной единицы, затем одна, затем одна.

Ввод: n = 5
Вывод: [0, 1, 1, 2, 1, 2]
Пояснение: 3 — это 11, а 5 — 101, в каждом по две единицы; 4 — это 100, с одной единицей. Если добавить 0, 1 и 2 из первого примера, получим количества 0, 1, 1, 2, 1, 2.

Дополнительный вопрос

Можешь заполнить весь массив за время O(n), не используя встроенную функцию для подсчёта битов и не пересчитывая каждый номер с нуля?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Подсчёт каждого числа с нуля приводит к повторению работы: 13 — это 1101, биты числа 6 (110) с ещё одной цифрой в конце. Заполняйте ответы в порядке возрастания, и каждая запись будет повторно использовать меньшее число с одним добавлением.

Посчитайте биты каждого числа

Идея

Подсчитывай единичные биты каждого числа напрямую: добавляй x & 1 к счётчику, сдвигай x вправо на один разряд и останавливайся на 0. Для 13 (1101) биты дают 1, 0, 1, 1, поэтому их количество равно 3.

У числа до n примерно log2 n двоичных цифр, поэтому выполнение занимает O(n log n): примерно 20,000 × 15 = 300,000 шагов для n = 2 × 10^4.

Алгоритм

Создайте пустой список результатов.
Для каждого i от 0 до n установите count равным 0, а x — равным i.
Пока x больше 0, прибавляйте x & 1 к count и сдвигайте x вправо на один разряд.
Добавьте count в список результатов.
Верните список результатов.

def countBits(n):
    bits = []
    for i in range(n + 1):
        count = 0
        x = i
        while x > 0:
            count += x & 1  # the lowest bit
            x >>= 1         # shift it out
        bits.append(count)
    return bits

Удвой половину числа

Идея

Сдвиг i вправо на один разряд удаляет его последнюю двоичную цифру, а i & 1 — это эта цифра. Значит, в i столько единиц, сколько в i >> 1, плюс его последняя цифра: bits[i] = bits[i >> 1] + (i & 1).

Для любого i больше или равного 1 значение i >> 1 меньше i, поэтому при заполнении массива слева направо, начиная с bits[0] = 0, запись, которую вы считываете, всегда уже готова. Для n = 5: bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2.

Для каждой записи требуется один сдвиг, одна операция AND и одно сложение: время O(n) и никакой дополнительной памяти, кроме выходного массива.

Алгоритм

Создай массив bits из n+1 нулей. bits[0] остаётся равным 0.
Для i от 1 до n установи bits[i] в значение bits[i >> 1] + (i & 1).
Верни bits.

def countBits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        # i >> 1 is i without its last bit, and i & 1 is that last bit
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

Ловушки и крайние случаи

Возврат n элементов вместо n+1. Для n = 0 ответ — [0].
Приоритет операторов. В Python, C, Java и JavaScript оператор + имеет более высокий приоритет, чем &, поэтому bits[i >> 1] + i & 1 означает (bits[i >> 1] + i) & 1. Сохраняйте скобки вокруг (i & 1).
Обращение к bits[i-1] вместо bits[i >> 1]. Между соседними числами нет простого правила: у 7 двоичная запись 111 с тремя единицами, а у 8 — 1000 с одной.
В Lua и R массивы начинаются с 1, поэтому количество для i находится по индексу i+1, а обращение к i >> 1 — по индексу floor(i/2) + 1. В Lua 5.1 нет оператора сдвига, поэтому делите пополам с помощью math.floor(i / 2).

Частые вопросы3

Какова временная сложность Counting Bits?

Лучшее решение работает за время O(n): каждая из n+1 записей получается из предыдущей записи одним сложением. Подсчёт битов каждого числа по отдельности занимает O(n log n). Оба решения используют O(1) дополнительной памяти помимо выходного массива.

Существует ли ещё одна рекуррентная формула с временной сложностью O(n) для подсчёта битов?

Да. i & (i-1) сбрасывает младший установленный бит в i, поэтому bits[i] = bits[i & (i-1)] + 1 для каждого i, равного 1 или больше. Для 12 (1100) 12 & 11 равно 8 (1000), в котором одна единица, поэтому в 12 их две.

Могу ли я использовать встроенную функцию подсчёта единичных битов?

Вызов этой функции для каждого числа, например Integer.bitCount в Java или __builtin_popcount в C и C++, даёт правильный ответ. На собеседованиях обычно просят решить задачу без неё, потому что суть задачи — повторно использовать уже вычисленные ответы.

def countBits(n):
    # Напишите код здесь

Тест #1

Тест #2

Аргумент

n = 2

Ожидаемый вывод

[0, 1, 1]