Как стать автором
Обновить
11
Карма
0
Рейтинг
Sevastianov Andrii @mustitz

Программист

  • Подписчики 2
  • Подписки

Магические битборды и русские шашки

ПрограммированиеАлгоритмыC
Данная статья — иллюстрация, каким образом битовые трюки могут быть использованы не только в задачах на собеседованиях, но и при решении реальных задач. В статье дано описание одного метода быстрой генерации ходов в русских шашках на основе магических битбордов (magic bitboard). Битборды — представление позиции в виде нескольких беззнаковых целых чисел, каждый бит которого отвечает за состояние некоторого элемента игры, например клетки. Обычно использование битбордов даёт выигрыш по производительности и по объёму используемой памяти, но связано с более изощрённым программированием. При этом часто возникает задача получения значения определённых бит в битборде, например, для последующего обращения к таблице. Есть два основных подхода к решению этой задачи. Первый — использование и поддержка избыточного представления в виде дополнительных битбордов с перенумерацией битов. Такие битборды асто называют вращаемые. Второй способ — умножение на магическую константу, сдвиг и обращение к таблице. О таких магических битбордах и пойдёт речь в этой статье.
Читать дальше →
Всего голосов 17: ↑17 и ↓0+17
Просмотры9.8K
Комментарии 2

Битовая магия: получение следующего лексикографического сочетания

АлгоритмыC
Из песочницы

Введение


Допустим у нас есть некоторое множество, которое состоит из N элементов. Будем считать, что элементы пронумерованы от нуля до N-1. Набор k-элементных подмножеств данного множества (сочетаний) можно представить либо в виде массива индексов длины k. Либо в виде последовательности из N бит, в которой установлено ровно k из них. У Дональда Кнута в его TAoCP приводится алгоритм генерации сочетаний в лексикографическом порядке, когда сочетания заданы в виде массива индексов. Мы попробуем перенести этот алгоритм на случай битовых масок.
Читать дальше →
Всего голосов 21: ↑19 и ↓2+17
Просмотры12K
Комментарии 2

Информация

В рейтинге
Не участвует
Откуда
Växjö, Kronobergs Län, Швеция
Дата рождения
Зарегистрирован
Активность