Задача нахождения номера старшего единичного бита числа довольно часто встречается в олимпиадном программировании, например в задаче RMQ.
Рассмотрим четыре способа решения этой задачи. Условимся, что задачу будем решать для целого числа N ($latex 1\leqslant{N}\leqslant{2}^{32}-1$).
Рассмотрим четыре способа решения этой задачи. Условимся, что задачу будем решать для целого числа N ($latex 1\leqslant{N}\leqslant{2}^{32}-1$).
1. naive [O(logN)] Первый способ самый простой и очевидный: будем сдвигать N вправо на один бит, пока оно не станет равным 1 (а не 0, так мы сэкономим одну итерацию).
- inline int high_bit_line(UINT n) {
- int res = 0;
- while (n != 1) {
- n >>= 1;
- res++;
- }
- return res;
- }
* This source code was highlighted with Source Code Highlighter.
Сложность первого алгоритма - количество цифр в двоичном представлении N, то есть $latex \log_2{N}$.
2. log2 [O(const)] Второй способ математический. Поскольку номер старшего бита - показатель старшей степени двойки, то его номер можно найти с помощью логарифма, округлив его вниз:
- #include <cmath>
- const double EPS = 1e-11;
- inline double log2(double n) {
- return log(n) / log(2.0);
- }
- inline int high_bit_log2(UINT n) {
- return (int)(log2((double)n) + EPS);
- }
* 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, поэтому пришлось делать промежуточную функцию. Сложность вычисления логарифма равна константе, но она достаточно велика.
К сожалению, библиотека cmath в Visual Studio не поддерживает функцию log2, поэтому пришлось делать промежуточную функцию. Сложность вычисления логарифма равна константе, но она достаточно велика.
3. Binary search [O(log(logN))] В основе этого способа лежит метод бинарного поиска. Будем брать правую часть числа (в двоичном представлении), пока она не равна нулю, а иначе берем левую часть, постепенно деля число пополам, пока не получим 1:
- inline int high_bit_bs(UINT n){
- int size = sizeof(n) * 4;
- int res = 0;
- while (n != 1) {
- int l = n >> size;
- if (l) {
- n = l;
- res += size;
- } else {
- n ^= l << size;
- }
- size >>= 1;
- }
- return res;
- }
* 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 } )$.
Сложность этого способа равна логарифму от числа битов 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};
Немного исправив код третьего способа, получаем:
- inline int high_bit_bsm(UINT n){
- int size = sizeof(n)*4;
- int res = 0;
- int m = 0;
- while (n != 1) {
- int l = n >> size;
- if (l) {
- n = l;
- res += size;
- } else {
- n &= MASK_R[m];
- }
- size >>= 1;
- m++;
- }
- return res;
- }
* This source code was highlighted with Source Code Highlighter.
Правда, в некоторых случаях эта оптимизация будет работать дольше, чем оригинал, поскольку операция сложения выполняется при каждом проходе цикла while.
Выводы: Подход с бинарным поиском дает наилучший результат.
Если нужно решать поставленную задачу на ограниченном диапазоне, который можно хранить в памяти, то лучше динамикой подсчитать позицию старшего единичного бита для каждого числа в диапазоне.
Эта идея хорошо описана в вики конспектах ИТМО(Раздел “Применение к задаче RMQ”).
Если нужно решать поставленную задачу на ограниченном диапазоне, который можно хранить в памяти, то лучше динамикой подсчитать позицию старшего единичного бита для каждого числа в диапазоне.
Эта идея хорошо описана в вики конспектах ИТМО(Раздел “Применение к задаче RMQ”).
