Блог пользователя Planshetnik

Реверс битов
Автор Planshetnik, 14 лет назад, По-русски
Приветствую 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;
}
Прошу прощение.
 
Теги bit
  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

14 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
тут и ниже по тексту

UPD. А вообще тут не совсем корректно применение O(). O(n) для 32- или 64- битных чисел - это O(1). Для массива длиной n быстрее чем за O(n) имхо никак. Чисел произвольной битности я как то не встречал...
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится
    Можно ли вообще корректно говорить про ассимптотику?
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вот именно. С таким же успехом можно сказать, что на ACM'е все задачи решаются за O(1), потому что все входные данные ограничены сверху ;)
    → Ответить
  • 14 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    лишнее
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если N - число битов, а размер регистра больше, чем N, то количество операций будет O(logN), а не O(1).
    → Ответить
    • 14 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Ок, число 1000000 битов. Сделайте реверс за O(logN) (или за O(1) или что там у Вас...).

      Ко всем вышеотписавшимся - некорректность я имел в таком ключе: автор топика не говорит какая длина чисел подразумевается (да и вообще на какой машине это все выполняется). O(1) - конкретно для 32-х или 64-х битных чисел (причем что то одно из них! и машина умеет оперировать сразу со всеми битами (upd: хотя тут это даже не важно)). Если машина умеет за O(1) выполнять простейшие действия с числами длины N (N не константа), то решение за O(logN). Для обычных же машин (которые не умеют параллельно менять все N битов числа) - быстрее O(N) никак (ибо мы в худшем случае меняем все биты).
      → Ответить