Как можно провести операцию транспонирования битов числа максимально эффективно?

Одним из способов достаточно эффективно провести операцию транспонирования битов числа является использование битовых масок и битовых операций AND, OR и XOR. Например, для транспонирования 16 битов можно использовать следующий алгоритм:

1. Разбить число на 4 группы по 4 бита каждая.
2. Применить битовую маску к каждой группе для получения нужных битов.
3. Сдвинуть биты в нужную позицию и объединить 4 группы обратно в итоговое число.

Чтобы перевести число 16 бит, представленное в виде матрицы 4x4, в другую ориентацию без использования циклов, можно воспользоваться битовыми операциями. Например, для перевода числа из ориентации:

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

в другую ориентацию:

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

можно использовать следующий алгоритм:

1. Применить битовые сдвиги и маски для каждой строки и каждого столбца, чтобы переместить биты в нужные позиции.
2. Использовать битовые операции XOR и OR для соединения битов в нужном порядке.

Таким образом, можно эффективно провести операцию транспонирования битов числа и изменить ориентацию числа без использования циклов.

Занумеруйте все биты от 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 чтения из памяти.

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