Самая быстрая битовая транспозиция (5x5)

Question

Для решения головоломок Я пишу, я ищу самый быстрый алгоритм (минимальное количество бит-операций) для транспонирования битов 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); 
} 

Но я t чувствует, что это может быть сделано со значительно меньшим количеством операций. Кто-нибудь знает более быстрое решение? Ссылки на хорошую литературу по этому вопросу также очень приветствуются.

Answer 1

A 2048 AI найдено here имеет метод транспонирования для 4x4 сетки из 4-х битных плиток. Возможно, вы можете приспособить его к своей ситуации. Вот код:

// Transpose rows/columns in a board: 
//c 
// 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); 
}