Самое быстрое преобразование битборда (5x5)
Для решателя головоломки, который я пишу, я ищу самый быстрый алгоритм (минимальное количество битовых операций) для транспонирования битборда 5x5 с 2 битами на квадрат в головоломке, поэтому:
00 01 02 03 04
05 06 07 08 09
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
становится
00 05 10 15 20
01 06 11 16 21
02 07 12 17 22
03 08 13 18 23
04 09 14 19 24
Лучшее, что я смог придумать, это
uint64_t transpose(uint64_t state) {
return ((state >> 16) & 0x10) |
((state >> 12) & 0x208) |
((state >> 8) & 0x4104) |
((state >> 4) & 0x82082) |
((state << 4) & 0x820820) |
((state << 8) & 0x410400) |
((state << 12) & 0x208000) |
((state << 16) & 0x100000);
}
Но такое ощущение, что это можно сделать с помощью значительно меньшего количества операций. Кто-нибудь знает более быстрое решение? Ссылки на хорошую литературу по этому вопросу также очень приветствуются.
1 ответ
Найденный здесь 2048 AI имеет метод транспонирования для сетки 4x4 из 4-битных тайлов. Возможно, вы сможете адаптировать его к вашей ситуации. Вот код:
// Transpose rows/columns in a board:
// 0123 048c
// 4567 --> 159d
// 89ab 26ae
// cdef 37bf
uint64_t transpose(uint64_t x)
{
uint64_t a1 = x & 0xF0F00F0FF0F00F0FULL;
uint64_t a2 = x & 0x0000F0F00000F0F0ULL;
uint64_t a3 = x & 0x0F0F00000F0F0000ULL;
uint64_t a = a1 | (a2 << 12) | (a3 >> 12);
uint64_t b1 = a & 0xFF00FF0000FF00FFULL;
uint64_t b2 = a & 0x00FF00FF00000000ULL;
uint64_t b3 = a & 0x00000000FF00FF00ULL;
return b1 | (b2 >> 24) | (b3 << 24);
}