Биты, сдвиги и безопасные маски

Битовые операции полезны, когда условие говорит о включённых флагах, подмножествах или двоичном представлении. Сначала важно перестать думать о них как о «магических символах» и назвать, какой именно бит меняется.

Как один бит становится управляемым флагом

Для беззнакового 32-битного числа проверить, установлен ли бит с номером k (нумерация с нуля), и посчитать общее число единиц. Например, у 44 двоичная запись 101100, поэтому биты 2, 3 и 5 установлены, а ответ popcount равен 3.

Что теряет поразрядное деление

Для проверки k-го бита можно многократно делить число на 2, пока не дойдём до позиции k; для подсчёта — обойти все 32 позиции. Это уже константа для uint32_t, но не использует структуру разреженных чисел и часто превращается в менее ясный код для динамических масок.

Почему нулевые биты не должны мешать

Последовательные деления теряют прямую связь с интересующей позицией. При подсчёте приходится проверять нулевые биты так же, как единицы, хотя они не меняют ответ.

Как маска выбирает, ставит и очищает позицию

1u << k строит маску, где единица стоит только в позиции k. value & mask ненулевое ровно тогда, когда этот бит был установлен. Для положительного x выражение x & (x - 1) удаляет его младший установленный бит: вычитание 1 переворачивает хвост до этой единицы, а & обнуляет саму единицу и сохраняет более старшие биты.

У одной и той же маски есть четыре базовые операции: проверить флаг — value & mask; установить флаг — value | mask; очистить флаг — value & ~mask; при необходимости переключить — value ^ mask. Для value = 44 и маски бита 4 установка даёт 60, а очистка бита 3 даёт 36. Операция очистки не «вычитает степень двойки»: она безопасна и тогда, когда выбранный бит уже равен нулю.

Что остаётся после удаления младшей единицы

В countSetBits переменная value содержит исходное число без уже посчитанных младших единиц, а count равно числу удалённых единиц. Каждая итерация удаляет ровно одну единицу, поэтому цикл заканчивается после количества установленных битов.

Как проверить, установить и очистить флаг

1. Проверить, что k в диапазоне 0..31.
2. Для проверки построить mask = 1u << k и вернуть (value & mask) != 0.
3. Для popcount пока value != 0 увеличить счётчик и сделать value &= value - 1.
4. Не выполнять сдвиг на 32 или больше: в C++ это неопределённое поведение для данного типа.

Четыре операции с одной позицией

Сначала постройте маску 1u << k только после проверки k. Проверка возвращает ненулевость value & mask. Установка возвращает value | mask, очистка — value & ~mask. Для popcount отдельный цикл value &= value - 1 по-прежнему удаляет младшую единицу до нуля.

Как сделать безопасные операции над битом

C++ использует uint32_t и литерал 1u, чтобы знак и ширина маски были явными. Python-версия намеренно проверяет тот же контракт uint32 и диапазон k от 0 до 31: произвольная точность Python не должна скрывать отличие от 32-битной модели урока.

C++17

#include <cassert>
#include <cstdint>
#include <iostream>
#include <stdexcept>

using namespace std;

uint32_t bitMask(unsigned k) {
    if (k >= 32) throw out_of_range("bit index");
    return uint32_t{1} << k;
}

bool hasBit(uint32_t value, unsigned k) {
    return (value & bitMask(k)) != 0;
}

uint32_t setBit(uint32_t value, unsigned k) {
    return value | bitMask(k);
}

uint32_t clearBit(uint32_t value, unsigned k) {
    return value & ~bitMask(k);
}

unsigned countSetBits(uint32_t value) {
    unsigned count = 0;
    while (value != 0) {
        value &= value - 1;
        ++count;
    }
    return count;
}

int main() {
    assert(hasBit(44u, 5));
    assert(!hasBit(44u, 4));
    assert(setBit(44u, 4) == 60u);
    assert(clearBit(44u, 3) == 36u);
    assert(countSetBits(44u) == 3);
    bool rejected = false;
    try {
        bitMask(32);
    } catch (const out_of_range&) {
        rejected = true;
    }
    assert(rejected);
    cout << countSetBits(0b11110000u) << '\n';
}

Python 3

def require_uint32(value: int) -> None:
    if not 0 <= value <= 0xFFFFFFFF:
        raise ValueError("value must fit into uint32")


def bit_mask(k: int) -> int:
    if not 0 <= k < 32:
        raise ValueError("bit index must be in 0..31")
    return 1 << k


def has_bit(value: int, k: int) -> bool:
    require_uint32(value)
    return (value & bit_mask(k)) != 0


def set_bit(value: int, k: int) -> int:
    require_uint32(value)
    return value | bit_mask(k)


def clear_bit(value: int, k: int) -> int:
    require_uint32(value)
    return value & ~bit_mask(k)


def count_set_bits(value: int) -> int:
    require_uint32(value)
    count = 0
    while value != 0:
        value &= value - 1
        count += 1
    return count


assert has_bit(44, 5)
assert not has_bit(44, 4)
assert set_bit(44, 4) == 60
assert clear_bit(44, 3) == 36
assert count_set_bits(44) == 3
try:
    bit_mask(32)
    assert False, "bit index 32 must be rejected"
except ValueError:
    pass
print(count_set_bits(0b11110000))

Почему попкаунт зависит от числа единиц

hasBit работает за O(1). countSetBits работает за O(p), где p — число единиц; для фиксированного 32-битного типа это ограниченная константа. Память O(1). В C++ тип и диапазон сдвига существенны; в Python сохраняйте явный контракт о неотрицательных входах.

Где ширина типа и знак критичны

value = 0 имеет ноль единиц. Установка старшего бита k=31 безопасна только при беззнаковой маске. k=32 нельзя сдвигать в C++ даже если кажется, что результат должен быть 0. Не используйте 1 << k со знаковым int, когда важен старший бит.

Какие маски обязаны пройти проверку

• 0: ни один бит не установлен, popcount 0;
• 1: установлен только бит 0;
• 44: проверка 2, 3, 4, 5, установка бита 4 в 60, очистка бита 3 в 36 и popcount 3;
• число из всех единиц нужной ширины;
• исключение для k=32 в C++ и отрицательных входов в Python.

Когда булевы признаки лучше упаковать

Сигналы: флаги, разрешения, небольшой набор булевых признаков, «включён ли параметр k», мощность двойки, число установленных битов. Сначала назовите, какая позиция и какой тип маски нужны, а затем выбирайте операцию &, |, ^ или сдвиг.

Когда именованный набор понятнее маски

Не заменяйте битами обычную логику, когда структура данных читается яснее. Если количество признаков не ограничено и нужен перебор по именам, set может быть удобнее. Не переносите Python-код со сдвигами отрицательных чисел в C++ без определения ширины и знака.

Самопроверка чтения одного разряда

Вопрос: почему 44 & (1 << 4) равно 0?
Ответ: 44 — 101100₂, а маска для позиции 4 — 010000₂; в позиции 4 у 44 ноль.

Самопроверка удаления младшей единицы

Вопрос: что делает x & (x - 1) для x = 40 (101000₂)?
Ответ: удаляет младшую единицу в позиции 3 и даёт 100000₂ (32). Следующая итерация удалит оставшуюся единицу.

Потренируйте операции над одной маской

Напишите функцию, которая возвращает ближайшее число, являющееся степенью двойки и не меньше n. Сначала проверьте, что n уже степень двойки через n > 0 && (n & (n - 1)) == 0; затем решите, как сдвигать единицу без выхода за тип.

Самостоятельная работа с флагами

Решите без подсказок и укажите допустимый диапазон индекса до первого сдвига.

Задача 1

Для беззнакового 32-битного числа реализуйте переключение k-го бита и проверку того, является ли число степенью двойки. Определите поведение для нуля и k вне диапазона.

Что делает побитовый код объяснимым

Битовая операция полезна, когда её инвариант можно сказать вслух: маска выбирает одну позицию, а x & (x-1) удаляет одну единицу. Без такого объяснения короткий код становится источником ошибок на границах.