Подсчёт битов и младший установленный бит
Используйте popcount и приём n & -n
«Подсчёт битов и младший установленный бит» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Подсчёт единиц
Во многих задачах требуется подсчитать, сколько битов установлено в числе. Это количество называют popcount. Оно используется при определении размеров подмножеств, проверке чётности и подсчёте очков. 🔢
Встроенный метод Python для подсчёта
Самый быстрый способ подсчитать установленные биты — целочисленный метод bit_count(). Никаких циклов и лишних действий — только количество единиц.
print((13).bit_count()) # 0b1101 has 3 onesПодсчёт с помощью bin и count
Если вы забыли про bit_count, преобразуйте число в двоичный текст и посчитайте единицы. Этот способ медленнее, зато понятен и его легко запомнить.
print(bin(13).count('1')) # 3Младший установленный бит
Младший установленный бит — это крайняя правая 1 в числе. Его выделение — важный приём для деревьев Фенвика и последующих трюков с подмножествами.
Выделение с помощью n и -n
Знаменитый приём n & -n оставляет только младший установленный бит. Отрицательные числа в дополнительном коде делают это возможным почти магическим образом.
n = 12 # 0b1100
print(n & -n) # 4 = 0b100Почему работает n и -n
Инверсия меняет все биты и прибавляет 1, поэтому все позиции ниже младшей 1 инвертируются. Операция AND оставляет только этот отдельный бит.
Удаление младшего установленного бита
При вычитании 1 заём проходит через конечные нули, поэтому n & (n - 1) стирает младший установленный бит. Повторяйте эту операцию, чтобы удалять единицы по одной.
n = 12 # 0b1100
print(n & (n - 1)) # 8 = 0b1000Подсчёт по алгоритму Брайана Кернигана
Выполняйте цикл, пока число не равно нулю, каждый раз сбрасывая младший бит. Цикл выполняется по одному разу для каждого установленного бита, поэтому он эффективен для разреженного popcount.
c = 0
while n:
n &= n - 1
c += 1Проверка степени двойки
Положительная степень двойки содержит ровно один установленный бит, поэтому n & (n - 1) равно 0. Одной операцией AND это можно мгновенно проверить.
def is_pow2(n):
return n > 0 and (n & (n - 1)) == 0Чётность по количеству битов
Чётность числа — это просто его popcount по модулю 2. Так одним шагом можно определить, является ли количество единиц нечётным или чётным.
parity = (13).bit_count() & 1 # 1Выбор самого быстрого инструмента
Для максимальной скорости используйте bit_count, а для перебора установленных битов — цикл с n & (n-1). Правильный выбор инструмента помогает уложиться в жёсткие ограничения по времени. ⚡
Быстрая проверка
Проверьте приём с младшим установленным битом.
Повторение: подсчёт битов
Вы можете подсчитать единицы с помощью bit_count, выделить младший бит через n & -n и удалить его с помощью n & (n-1). Мощные однострочные приёмы. 🎉
Часто задаваемые вопросы
Урок «Подсчёт битов и младший установленный бит» бесплатный?
Да — полный текст урока «Подсчёт битов и младший установленный бит» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Подсчёт битов и младший установленный бит»?
Используйте popcount и приём n & -n Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Подсчёт битов и младший установленный бит»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- AND, OR, XOR и сдвиги
- Установить, сбросить и переключить бит
- Подсчёт битов и младший установленный бит
- Битовые маски как маленькие множества