Вопрос на собеседовании #3

Задача до "верного" решения которой я вряд ли бы додумался :)

Задача
Есть функция

byte f(byte b);

Надо ее реализовать так, чтобы она возвращала тот же байт, только порядок битов в них должен быть реверснут, то есть:
01100011 ==> 11000110

Функция должна работать максимально быстро, по памяти мы не ограничены.

Решение

byte a[256];

byte f(byte b)
{
    return a[b];
}

 И соответственно любой прекальк:

byte reverse(byte b)
{
    b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
    b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
    b = (b & 0xAA) >> 1 | (b & 0x55) << 1;
    return b;
}

void precalc()
{
    for(byte i = 0; i < 256; i++)
        a[i] = reverse(i);
}

Решение логичное, но в голову в качестве решения задачи не идет. Я написал функцию на обычной битовой арифметики.

В данном примере прекальк взят из Уоррена(Алгоритмические трюки для программистов), идея простая. проще всего ее описать вот так:

Ясно, что вряд ли есть более быстрое решение, но допустим можно обсудить быстрые прекальки :) или может есть процессоры с встроенным реверсом!

Другие части цикла: #1 #2 #4 #5