[Из песочницы] Битовая магия: получение следующего лексикографического сочетания
Допустим у нас есть некоторое множество, которое состоит из N элементов. Будем считать, что элементы пронумерованы от нуля до N-1. Набор k-элементных подмножеств данного множества (сочетаний) можно представить либо в виде массива индексов длины k. Либо в виде последовательности из N бит, в которой установлено ровно k из них. У Дональда Кнута в его TAoCP приводится алгоритм генерации сочетаний в лексикографическом порядке, когда сочетания заданы в виде массива индексов. Мы попробуем перенести этот алгоритм на случай битовых масок.
Алгоритм генерации следующего лексикографического сочетания достаточно прост и состоит из двух шагов. На первом шаге нам надо найти такой наименьший индекс m элемента, следующий за которым элемент не входит в сочетание. Или, что тоже же самое, который мы можем увеличить на единицу. Это элемент заменяем на следующий. На втором шаге все элементы, которые меньше нашего выбранного m-го элемента заменить на наименьшие из возможных. Например, и нас есть сочетание { 8, 5, 4, 3, 2 }. Наименьший элемент, который можно увеличить на единицу, это 5. Заменяем его на шестерку: { 8, 6, 4, 3, 2 }. Теперь удаляем три элемента, которые меньше шести: { 8, 6 }. И добавляем наименьшие три элемента. Получено { 8, 6, 2, 1, 0 } — следующее сочетание в лексикографическом порядке.
Теперь переведём этот алгоритм на язык битов. Первый шаг это поиск такого самого младшего бита, непосредственно слева перед которым расположен нуль. Второй шаг — обменять полученные единицу и нуль местами. Третий шаг: все биты, которые младше найденного, сдвигаем до нулевой позиции. Рассмотрим наш пример? 100111100 → 100111100 → 101011100 →101011100 →101000111 → 101000111.
Я люблю разные битовые трюки. Но многие программисты с ними знакомы достаточно слабо, и они вгоняют их в ступор. Например, не все знают, что выражение x & -x обратит все биты числа в нуль, за исключением самой младшей установленной единицы. Как он работает?
По определению, -x = ~(x-1). Простейшая иллюстрация: -1 = ~(1–1) = ~0. Допустим теперь, что число x имеет вид nnnn1000, где n — биты, которые могут быть установлены как в нуль, так и в единицу. Наша цель состоит в том, чтобы показать, что (nnnn1000 & -nnnn1000) = 00001000. Получаем такую цепочку: nnnn1000 & -nnnn1000 = nnnn1000 & ~(nnnn1000 — 1) = nnnn1000 & ~(nnnn0111) = nnnn1000 & ññññ1000 = 00001000, где ñ — соответствующий инвертированный бит n.
Теперь проиллюстрируем, как должна работать мысль, чтобы получить битовое выражение для следующего лексикографического сочетания. Если к нашему числу добавить число, в котором оставлен только один младший бит, то в результате переноса самый младший бит перед которым стоит нуль, передвинется на место этого нуля. Все остальные младшие биты обнулятся:
int a = x & -x;
int b = x + a;
В результате, если x = 100111100, то a = 000000100, и b = 101000000. Полдела сделано. Осталось только выделить младшие биты и перенести их вправо. Для того, чтобы установить в нуль неиспользуемые биты, чаще всего используется операция AND. С учётом трюка x&-x, сразу напрашивается вариант:
int c = b & -b; // 001000000
int c = c - 1; // 000111111
int d = c & x; // 000111100
В результате которого мы получим последовательность бит, которые можно сдвинуть вправо. Правда число бит будет на один больше нужного количества, что легко исправить сдвиганием ещё на один бит вправо.
Впрочем, для обнуления совпадающих бит можно использовать также операцию XOR. Попробуем и её:
int c = x ^ b;
В общем случае у нас x можно представить как x = nn…n011…100…, при этом b = nn…n100…000…. Тогда операция x ^ b убьёт совпадающие вначале nnn, оставив только 00…0111…100…. Для нашего примера c = 001111100. В отличие от предыдущего случая, данная последовательность бит на два длиннее, чем требуется. Вариант c XOR требует меньшего количества операций. Оставим его:
int a = x & -x;
int b = x + a;
int c = x ^ b;
Теперь последовательность бит, которая хранится в с, надо сдвинуть вправо до самого младшего бита, и ещё на два «лишних» разряда. Можно это сделать «в лоб»:
c /= a;
c <<= 2;
Операция деления достаточно дорогая, а если процессор поддерживает получение индекса младшего бита, то возможно быстрее будет использовать её. Например, для случая GCC соответствующая встроенная функция называется __builtin_ctz, в результате получим:
int d = __builtin_ctz(x) + 2;
c <<= d;
Если такой инструкции нет, то можно рассмотреть вариант получения индекса через последовательность де Брёйна, тогда наш код будет выглядеть примерно так:
int d = magic_table[(magic_factor * a) >> magic_shift];
c <<= d;
В итоге деление и сдвиг заменилось умножением, двумя сдвигами и взятием значения из таблицы.
Итак, в результате мы получили следующий код:
static inline uint64_t next_combination_mask(uint64_t x)
{
uint64_t a = x & -x;
uint64_t b = x + a;
uint64_t c = b ^ x;
a <<= 2;
c /= a;
return b | c;
}
состоящий из шесть элементарных операций с целыми числами, и одного деления. Без циклов и условий. Который должен выполняться достаточно быстро. Каким образом его можно использовать в готовом проекте? Например, мы хотим перечислить все возможные комбинации рук, которые можно получить в омаху. Их будет C (52,4) = 270725. Сделать это можно следующим циклом:
uint64_t current = 0x0F; // первая битовая маска;
uint64_t last = 1 << 52; // 52-й бит появится только когда мы рассмотрим все комбинации из 52 карт, и перейдем к 53-й
do {
process_mask(current); // что-то делаем...
current = next_combination_mask(current); // переходим к следующей руке
} while (current < last);
