пятница, 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”).