Приветствую 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;
}Прошу прощение. |
Comments (0)
