Битовые трюки

Несколько выражений, которые встречаются постоянно. Каждое — одна строка, и каждое стоит понимать, а не запоминать.

x & (x - 1) — снять младшую единицу

Вычитание единицы превращает младшую единицу в ноль, а все нули правее неё — в единицы. Логическое «и» оставляет от этого только то, что было левее младшей единицы.

Отсюда проверка на степень двойки: у степени двойки ровно один единичный бит, значит x && !(x & (x - 1)).

x & (-x) — оставить только младшую единицу

В дополнительном коде $-x = \lnot x + 1$. Инверсия переворачивает всё, прибавление единицы возвращает на место хвост из нулей и саму младшую единицу. В пересечении остаётся ровно один бит.

Это выражение — основа дерева Фенвика, где по нему определяют, за какой отрезок отвечает ячейка.

Подсчёт единичных битов

Три способа, от медленного к быстрому.

int count = 0;
while (x) { count += x & 1; x >>= 1; }          // по одному биту

int count = 0;
while (x) { x &= x - 1; count++; }              // по одной единице

int count = __builtin_popcountll(x);            // одной инструкцией

Второй способ делает столько итераций, сколько единиц, а не сколько битов. Третий вызывает инструкцию процессора.

Замер на 20 миллионах случайных 64-битных чисел: цикл по битам — 627 мс, снятие младшей единицы — 354 мс, __builtin_popcountll — 30 мс. Разница с встроенной функцией двадцатикратная, и в задачах, где popcount считается миллионы раз, это существенно.

Осторожно: для int функция называется __builtin_popcount, для long long — __builtin_popcountll. Перепутать легко, а результат будет считаться только по младшим 32 битам.

Ещё несколько

задача	выражение
номер старшего бита	63 - __builtin_clzll(x)
номер младшего бита	__builtin_ctzll(x)
округлить вверх до степени двойки	1ULL << (64 - __builtin_clzll(x - 1))
поменять местами без временной переменной	a ^= b; b ^= a; a ^= b;

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

Функции __builtin_clzll и __builtin_ctzll не определены при нуле — это отдельная проверка, а не «вернёт 64».

Смежное

• Биты и маски; Выражение x & (-x) — основа дерева отрезков на массиве и дерева Фенвика: по нему определяют, за какой отрезок отвечает ячейка.