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

Битовая операция
Автор witua, 13 лет назад, По-русски
Как можно, используя побитовые операции, найти самый старший установленный бит числа за O(1)?
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
http://stackoverflow.com/questions/53161/find-the-highest-order-bit-in-c

Там описаны два способа условно за О(1).
(Вообще формулировка "за О(1)" не совсем корректна, как мне кажется, потому что только передать число - это уже О(длины числа) битовых операций.)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Почитайте)
http://habrahabr.ru/blogs/algorithm/93172/
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Кажется во втором методе лучше 

    return x - (x >> 1);

    заменить на

    return x ^ (x >> 1);

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А разве операция xor выполняется не за O(log2 N)? или условно считаеться что битовые операции выполняються за O(1)?
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

есть очень простой способ найти младший бит: x & -x

есть довольно громоздкий метод как реверснуть биты числа за O(1),

можно применить его два раза :)

→ Ответить