Реверс битов

Planshetnik's blog

Реверс битов

By Planshetnik, 13 years ago, In Russian

Приветствую CodeForces' Users!

Мне как-то такой вопрос задали:

Можно ли за O(1) сделать реверс битов, без precalc'а?

Я ничего лучше O(n) не придумал, где n - кол-во бит.

При этом мне сказали что можно за O(1), но таки не сказали как.

Например: 101001 -(преобразование)- 100101.

UPD:

Блин Гуглом надо было попользоваться(

нашел ответ :

unsigned rev (unsigned x)
{
 x = (x & 0x55555555) << 1 | (x >> 1) & 0x55555555;
 x = (x & 0x33333333) << 2 | (x >> 2) & 0x33333333;
 x = (x & 0x0F0F0F0F) << 4 | (x >> 4) & 0x0F0F0F0F;
 x = (x <<24) | ((x & 0xFF00) <<8) |
     ((x >> 8) & 0xFF00) | (x >> 24);
 return x;
}