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

Задача нахождения номера старшего единичного бита числа довольно часто встречается в олимпиадном программировании, например в задаче 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”).