Как транспонировать биты числа максимально быстро?

Question

[SergeySerge11]

Допустим есть число 16 бит 4x4
1 1 1 1
0 0 0 0
0 0 0 0
1 0 0 1
его нужно повернуть в
1 0 0 1
1 0 0 0
1 0 0 0
1 0 0 1
Как сделать Без циклов и их разверток

Есть алгоритм, что бы его решить нужно транспонировать число, как это сделать, цикл или 32 операции для long числа делают алгоритм бессмысленным. можно ли как-то 4-8 битовыми операциями транспонировать число.

Еще есть ли вообще такие операции, как можно допустим число
биты которого 1111 заскелить в 0001000100010001 то есть каждый бит расматривать как разряд, допустим из 8 bit числа маски получить 64 битовое число, где каждый байт 0-1 в зависимости от 1 бита
Что-то вроде такого, можно ли сделать быстрее, ведь по факту в железе такую операцию легко реализовать одной ассемблерной инструкцией есть ли такая?

int b0=(15>>0)&1;
 int b1=(15>>1)&1;
 int b2=(15>>2)&1;
 int b2=(15>>3)&1;
 int res=b0| b1<<8 | b2<<16 | b3<<24

Comments

[historydev]

ведь по факту в железе такую операцию легко реализовать одной ассемблерной

так возьми ассемблерную инструкцию и вызови её из языка

[Sussh]

А как можно 32 бита в виде матрицы представить? Или она просто не квадратная?

Answer 1

[Wataru]

Занумеруйте все биты от 0 до 16. Потом транспонируйте эту матрицу. Потом посмотрите на разность результата и конца. Вот эти вот числа - это на сколько бит надо сдвинуть исходные биты, чтобы они встали на нужное место.

0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

0 4 8 12
1 5 9 13
2 6 10 13
3 7 11 15

0 -3 -6 -9
3 0 -3 -6
...

Все биты с одинаковым смещением можно подсчитать за 3 операции: Сдвиг, битовая маска и побитовое или в ответ.
Я тут вижу 7 разных чисел -9,-6,-3,0,3,6,9.
Например, для 0 и 3 у вас будет

answer = (source & 0x1248) | ((source << 3) | 0x2480) | ...

Это не 8 пока еще операций, а аж 20. Возможно можно как-то еще их сгруппировать.

Edit: Возможно, еще подход с таблицей будет быстрее. Для каждого из 16 возможных значений строк выдавайте битовое число - столбец, где эти 4 бита на позициях 0, 4, 8,12. Тогда ответ будет table[source&0xf0] | (table[(source>>4)&0xf] << 1) | (table[(source>>8)&0xf] << 2) | (table[(source>>12)&0xf] << 3).

Тут 13 битовых операций и 4 чтения из памяти.

Comments

[SergeySerge11]

Что за число 0x1248 = 0001_0010_0100_1000 не могу понять, почему не 1000_0100_0010_0001

[Wataru]

SergeySerge11, вы правы, я не в том порядке маски для строк выписал.

Answer 2

[U235U235]

Думаю, наиболее быстро будет с помощью предварительно сформированной таблицы подстановки - Look up table (LUT).
Просто создаете таблицу из 65536 16-битных чисел, где каждому индексу соответствует результат транспонирования. И берите готовый результат по индексу.

Comments

[SergeySerge11]

65к это больше чем локальной памяти на видеокарте

[U235U235]

SergeySerge11, достаточно даже будет 8192 байта. Если учесть, что диагональные элементы можно не кодировать..

[Odissey Nemo]

SergeySerge11, это суммарно 128 килобайт (65536*2).

Answer 3

[mayton2019]

Ищется функция вида

def transpose(matrix uint16) : uint16 = {}

Если она ДЕТЕРМИНИРОВАНА тоесть зависит от аргумента и все. То можно ее ускорить
путем МЕМОИЗАЦИИ тоесть создания просто таблицы расчитанных значений.
Это будет очень быстро.

Это удобно поскольку таблица получается не очень большая и влезает в разумные
рамки памяти. Если допустим мы говорим о 32х битах то можно изучать варианты.
В реальном мире линейного распределения аргументов не бывает. Распределение
всегда косит в какую-то сторону, и этим можно вользоваться, создавая кеши значений
типа LRU или дисковые базы данных как делают например, для
тяжелых расчетов или в вебе для медленных источников данных.

Answer 4

[arteast]

Если вопрос стоит в том, как это сделать средствами исключительно логических операций - то см. ответ Wataru. 17 бинарных логический операций, если я правильно посчитал (с учетом того, что сдвиги на 9 и -9 можно маскировать совместно).
Если можно использовать LUT - то LUT, вероятно, будет выгоднее. Учитывая, что преобразование линейное - таблицу можно делить на части, выбирая между скоростью и памятью. Например, можно поделить на 2 части - отдельные таблицы для каждой половины из 16-битного входа, и получить расход 1кб памяти, 3 логических операции и два хождения в LUT.
Если речь о x86 cpu и можно использовать специфичные инструкции - то еще можно посмотреть в сторону sse/avx. Например, разбить вход побитово на байты и pshub, или (если есть XOP/AVX512) броадкаст его и vprotw/vpsllvw, или же vpshufbitqmb, или же vpermb,... Куча возможных вариантов.