Самая быстрая транспозиция растрового изображения (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);
}

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


c++ bit-manipulation bitboard
person Arthelais    schedule 21.03.2015    source источник
comment
Мне кажется, что вам нужен бессменный термин там. transpose(1), кажется, возвращает неверный результат.   -  person user2357112 supports Monica    schedule 22.03.2015
comment
Кроме того, похоже, что некоторые константы в этом transpose основаны на битовой доске 1 бит на квадрат.   -  person user2357112 supports Monica    schedule 22.03.2015
comment
В зависимости от того, что вы с ним делаете, вы можете использовать дополнительный флаг, который указывает, следует ли читать это как основную матрицу строк или основных столбцов. Это то, что вы часто встречаете в библиотеках/программах, работающих с большими матрицами: вместо выполнения фактической дорогостоящей операции преобразования они, например. использовать другой алгоритм умножения.   -  person MikeMB    schedule 22.03.2015
comment
Вероятно, для этого есть хорошая последовательность дельта-свопа.   -  person harold    schedule 22.03.2015

Ответы (1)


arrow_upward
1
arrow_downward

ИИ 2048 года, найденный здесь, имеет метод транспонирования. для сетки 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);
}
person Community    schedule 22.05.2016