Битборд: подсчет элементов у соседей

Question

Чтобы представить состояние 2D настольной игры, я использую битборды с 16- битными целыми числами без знака. Состояние кодируется с 1 для присутствия части и 0 в противном случае.

Как подсчитать количество фигур, имеющих по крайней мере одну смежную часть по горизонтали, вертикали или диагонали?

Алгоритм, который я нашел (очень упрощенный):

total = 0
for each bitIndex in bitscanForward(bitboard)
    total += bitPopCount(bitboard & (ADJACENT_MASK << bitIndex))
return total

• Функция bitScanForward возвращает индекс первого бита и устанавливает его в 0
• Функция bitPopCount возвращает количество бит

Единственным ограничением является то, что доски представляют собой m строк x m столбцов с m <= 8.

Есть ли способ сделать это без зацикливания битов?

Answer 1

Получите маску с установленным битом, если на ней есть часть и некоторая смежная часть (то есть часть находится непосредственно слева или справа, или вверх, или вниз, или по диагонали):

mask = board & (left(board) | right(board) | up(board) | down(board) |
                left(up(board)) | left(down(board)) |
                right(up(board)) | right(down(board)))

Тогда просто посчитай это.

Ключевым моментом, очевидно, является реализация платы "сдвиги", но они действительно просты. Ваш выбор значения направления в терминах битов может отличаться в зависимости от порядка, в котором вы упаковываете биты на доске. Например, для упаковки досок 4х4 в некотором порядке, который, казалось, имел смысл:

left(board)  = (board & 0x7777) << 1
right(board) = (board & 0xEEEE) >> 1
up(board)    = board << 4
down(board)  = board >> 4