Как поменять порядок битов в байте C?
Вручную, наивно. Представьте, что это массив из 8 значений. У вас есть операции "прочитать i-ое значение" ((x >> i) & 1) и "записать значение a в позицию i" ((x & ~(1 << i)) | (a << i)). Дальше остается написать цикл и руками менять биты местами.

Дальше, конечно, можно извращаться с оптимизацией и всякмими битовыми хитростями.

Но если вам важна именно скорость, то быстрее предподсчета (как вам угодно) и хранения результата в таблице вы ничего не сделаете.
Как поменять порядок битов в байте C?
Посмотреть какой бит стоит на каждом месте и поставить такой же на каждом новом месте?
Можно обойтись без сдвигов. Удобно пользоваться битовыми операциями, но можно обойтись и без них. Это можно сделать одной чистой арифметикой. Для ускорения можно анализировать не отдельные биты а группы -- например по 2 или по 4 и выполнять для них замену по таблице.