пятница, 13 июля 2012 г.

Нахождение номера старшего бита числа

Задача нахождения номера старшего единичного бита числа довольно часто встречается в олимпиадном программировании, например в задаче RMQ.
Рассмотрим четыре способа решения этой задачи. Условимся, что задачу будем решать для целого числа N ($latex 1\leqslant{N}\leqslant{2}^{32}-1$).
1. naive [O(logN)] Первый способ самый простой и очевидный: будем сдвигать N вправо на один бит, пока оно не станет равным 1 (а не 0, так мы сэкономим одну итерацию).
  1. inline int high_bit_line(UINT n) {
  2.   int res = 0;
  3.   while (n != 1) {
  4.     n >>= 1;
  5.     res++;
  6.   }
  7.   return res;
  8. }
* This source code was highlighted with Source Code Highlighter.
Сложность первого алгоритма - количество цифр в двоичном представлении N, то есть $latex \log_2{N}$.

2. log2 [O(const)] Второй способ математический. Поскольку номер старшего бита - показатель старшей степени двойки, то его номер можно найти с помощью логарифма, округлив его вниз:
  1. #include <cmath>
  2.  
  3. const double EPS = 1e-11;
  4. inline double log2(double n) {
  5.   return log(n) / log(2.0);
  6. }
  7. inline int high_bit_log2(UINT n) {
  8.   return (int)(log2((double)n) + EPS);
  9. }
* This source code was highlighted with Source Code Highlighter.
Вроде бы все классно, но могут возникнуть проблемы с округлением. Поскольку математические операции в cmath могут возвращать неточные значения (например, sqrt(4) = 1.9999...) , то приходится добавлять к их результатам константу. Константа должна быть строго меньше числа, обратного максимальному значению N, иначе это может привести к неправильному результату (например, если к $latex log_2({2}^{32}-1)$ прибавить 10-9, то результат будет больше 31). Поэтому в нашем случае я взял 10-11, так как $latex \frac 1 {{2}^{32}} \approx {2}*{10}^{-10}$.
К сожалению, библиотека cmath в Visual Studio не поддерживает функцию log2, поэтому пришлось делать промежуточную функцию.
Сложность вычисления логарифма равна константе, но она достаточно велика.

3. Binary search [O(log(logN))] В основе этого способа лежит метод бинарного поиска. Будем брать правую часть числа (в двоичном представлении), пока она не равна нулю, а иначе берем левую часть, постепенно деля число пополам, пока не получим 1:
  1. inline int high_bit_bs(UINT n){
  2.   int size = sizeof(n) * 4;
  3.   int res = 0;
  4.   while (n != 1) {
  5.     int l = n >> size;
  6.     if (l) {
  7.       n = l;
  8.       res += size;
  9.  
  10.     } else {
  11.       n ^= l << size;
  12.     }
  13.     size >>= 1;
  14.   }
  15.   return res;
  16. }
* This source code was highlighted with Source Code Highlighter.
Рассмотрим применение этого алгоритма к числу 1234567890.
$latex 0 1 0 0 1 0 0 1 1 0 0 1 0 1 1 0 | 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0$ res = 0; size = 16;
$latex 0 1 0 0 1 0 0 1|1 0 0 1 0 1 1 0$ res = 16; size = 8;
$latex 0 1 0 0|1 0 0 1$ res = 24; size = 4;
$latex 0 1|0 0$ res = 28; size = 2;
$latex 0|1$ res = 30; size = 1;
Сложность этого способа равна логарифму от числа битов N, то есть $latex \log _{ 2 } (\log _{ 2 }{ N } )$.

4. Binary search with mask [O(log(log(N)))]
Да, я не ошибся, сложность четвертого алгоритма почти равна сложности третьего, так как этот способ является всего лишь небольшой оптимизацией предыдущего. В третьем алгоритме мы находим правую часть числа через левую (строка 9). Здесь мы затрачиваем две операции: битового сдвига и исключающего ИЛИ (XOR). Эти операции можно заменить на сложение и И (AND), добавив константный массив масок:
const int MASK_R[6] = {0x0000FFFF, 0x000000FF, 0x0000000F, 0x00000003, 0x00000001};
Немного исправив код третьего способа, получаем:
  1. inline int high_bit_bsm(UINT n){
  2.   int size = sizeof(n)*4;
  3.   int res = 0;
  4.   int m = 0;
  5.   while (n != 1) {
  6.     int l = n >> size;
  7.     if (l) {
  8.       n = l;
  9.       res += size;
  10.     } else {
  11.       n &= MASK_R[m];
  12.     }
  13.     size >>= 1;
  14.     m++;
  15.   }
  16.   return res;
  17. }
* This source code was highlighted with Source Code Highlighter.
Правда, в некоторых случаях эта оптимизация будет работать дольше, чем оригинал, поскольку операция сложения выполняется при каждом проходе цикла while.

Выводы: Подход с бинарным поиском  дает наилучший результат.
Если нужно решать поставленную задачу на ограниченном диапазоне, который можно хранить в памяти, то лучше динамикой подсчитать позицию старшего единичного бита для каждого числа в диапазоне.
Эта идея хорошо описана в
вики конспектах ИТМО(Раздел “Применение к задаче RMQ”).

16 комментариев:

  1. Анонимный25 июня 2012 г., 12:00

    int size = sizeof(n) * 4; почему именно 4?

    ОтветитьУдалить
  2. 4 = 8/2 - количество бит в половине байта

    ОтветитьУдалить
  3. Анонимный1 июля 2012 г., 16:43

    Бинарный алгоритм для того что можно и так найти за log это круто!!! Спасибо!

    ОтветитьУдалить
  4. Анонимный1 июля 2012 г., 16:56

    И кстати log N, здесь N в битовых терминах, то есть количества бит. А не самого N числа, от которого мы хотим узнать старший бит.

    А так как количество бит не зивист от числа N - от выходного параметра, то ассимпотика, даже наивного случая будет O(1)(а также всех остальных).

    Если не прав, поправтье.

    ОтветитьУдалить
    Ответы
    1. Анонимный1 июля 2012 г., 17:13

      O(1) имеется в виду если входное число будет представленно 32,64 или 128 битами - то есть когда количество бит константно.

      Удалить
    2. Анонимный1 июля 2012 г., 17:36

      А если быть еще точнее, то в данном конкретном случае (например в naive) ассимптотика всегда O(log2(32)) - то есть худший случай когда все 32 бита заполнены, а O как известно показывает худший случай - оценку сверху.

      Удалить
    3. Анонимный1 июля 2012 г., 17:39

      Извиняюсь не O(log2(32)), а O(32).

      Удалить
    4. "И кстати log N, здесь N в битовых терминах, то есть количества бит. А не самого N числа, от которого мы хотим узнать старший бит."

      Нет, N и есть число, для которого решается задача. Количество бит в числе на 1 больше его логарифма по основанию 2.

      Удалить
  5. А какой смысл в этом алгоритме? Количество бит в числе константное, соответственно, самый первый алгоритм имеет константную сложность.
    Могла бы быть польза от масштабируемости, например, для длинных чисел, но здесь этого нет. В алгоритмах с бинарном поиском используется сдвиг и проверка группы битов, которые имеют линейную сложность.

    ОтветитьУдалить
    Ответы
    1. "Количество бит в числе константное"

      Имеется в виду количество значащих бит.

      Удалить
  6. В чем смысл того, что третий способ работает в 2.5 раза быстрее? Не знаю что тут еще можно добавить.

    Сдвиг и проверка битов работает с линейной сложностью? А мне кажется за O(1).

    ОтветитьУдалить
  7. С каких пор вычисление логарифма стало O(1)? Время вычисления логарифма определённо зависит от разрядности Вашего числа (попробуйте посчитать log (3^137-8)! столь же быстро, как и log 2).

    ОтветитьУдалить
    Ответы
    1. С Вами нельзя не согласиться! Автор поста сейчас в отъезде. По приезду подправим.
      Спасибо за замечание!

      Удалить
  8. По-моему интересным также является следующий подход:
    1. Предподсчитаем ответ для всех чисел от 0 до 2^16 одним из предложенных выше алгоритмов(любой способ будет работать быстро).
    2. Теперь чтобы находить номер старшего бита числа n разделим его на две части:
    a = (n & ((1 << 16) - 1)
    b = (n >> 16)
    Теперь несложно ответить на вопрос с помощью предподсчитанных результатов, т.к. для чисел a и b мы ответ знаем.

    ОтветитьУдалить
    Ответы
    1. При большом количестве запросов на поиск старшего бита - это очень хороший подход!

      Удалить