Биты и маски

Всё, что делают с отдельным битом, сводится к четырём выражениям. Их стоит выучить наизусть — они встречаются в каждой второй задаче.

действие	выражение
проверить $i$-й бит	(a >> i) & 1
установить $i$-й бит	a | (1ULL << i)
снять $i$-й бит	a & ~(1ULL << i)
инвертировать $i$-й бит	a ^ (1ULL << i)

Почему они работают, стоит проговорить один раз.

Маска 1ULL << i — это число, у которого единственная единица стоит на $i$-м месте. «Или» с единицей всегда даёт единицу, а с нулём оставляет как есть — отсюда установка. «И» с нулём всегда даёт ноль, а с единицей оставляет — отсюда снятие, только маску надо перевернуть. «Исключающее или» с единицей меняет бит, с нулём оставляет — отсюда инверсия.

Во всех трёх случаях остальные биты не задеваются, и это главное свойство.

Хвосты

действие	выражение
оставить $n$ младших битов	a & ((1ULL << n) - 1)
обнулить $n$ младших битов	(a >> n) << n

Маска (1ULL << n) - 1 — это $n$ единиц подряд: $2^n$ в двоичном виде это единица и $n$ нулей, а вычитание единицы превращает её в $n$ единиц.

Осторожно с краем: 1ULL << 64 — неопределённое поведение, а не ноль. Если $n$ может равняться разрядности типа, случай нужно разобрать отдельно.

Вывод битов

Чтобы напечатать число в двоичном виде, цикл идёт вниз, от старшего бита к младшему:

for (int bit = width - 1; bit >= 0; bit--) std::cout << ((a >> bit) & 1);

Ведущие нули при этом печатаются — обычно это как раз то, что нужно. Если хочется без них, в C++ есть std::bitset<64>(a).to_string() и потом обрезка, но чаще проще написать цикл.

Смежное

• Битовые операции — что такое &, |, ^ и сдвиги;
• Битовые трюки — идиомы посложнее.