Как найти старший бит числа

Задача нахождения номера старшего единичного бита числа довольно часто встречается в олимпиадном программировании, например в задаче RMQ.
Рассмотрим четыре способа решения этой задачи. Условимся, что задачу будем решать для целого числа N ($latex 1leqslant{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”).

> Вообще-то гарантирует. Пункт 7.18.1.1

…

То есть если такие типы существуют, то typedef должен быть.

Там не сказано, что «если такие типы существуют» (где?), а «если реализация обеспечивает». Причём по c99 не гарантируется наличие ни одного из этих типов, а posix не гарантирует наличие только 64-битных чисел и предлагает вызывать

getconf -a | grep POSIX_V7

Но можно ли себе представить такую реализацию, которая обеспечивала бы 8-, 16-, 32-битные числа, а также int_least64_t (который теоретически может быть, например, 128-битным), но не обеспечивала бы 64-битного числа? По-моему, это невероятно.

А вообще, gcc сейчас обеспечивает и 128-битные числа (__int128_t), в том числе на 32-разрядных системах.

Sorcerer ★★★★★

(21.07.11 09:35:28 MSK)

Обычно для поиска старшего единичного бита используют функцию, которая возвращает количество лидирующих нулей, поскольку очень часто в системе команд процессора существует такая инструкция (например, в X86 это LZCNT), а компилятор обеспечивает встроенную функцию (например, в GCC это int __builtin_clz (unsigned int x)).
(см. также Find first set)

Если доступ к таким средствам недоступен (?), то можно воспользоваться одной из достаточно эффективных программных реализаций:

#include <stdlib.h>


static inline int _clz4 (uint x) {
  static int n[16] = {4, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0};
  return n[x];
}

static inline int _clz8 (uint x) {
  return x > 0xf ? _clz4(x >> 4) : _clz4(x) + 4;
}
static inline int _clz16 (uint x) {
  return x > 0xff ? _clz8(x >> 8) : _clz8(x) + 8;
}

static inline int clz32 (uint x) {
  return x > 0xffff ? _clz16(x >> 16) : _clz16(x) + 16;
}


// http://embeddedgurus.com/state-space/tag/clz/
#include <stdint.h>

static inline uint32_t CLZ1(uint32_t x) {
    static uint8_t const clz_lkup[] = {
        32U, 31U, 30U, 30U, 29U, 29U, 29U, 29U,
        28U, 28U, 28U, 28U, 28U, 28U, 28U, 28U,
        27U, 27U, 27U, 27U, 27U, 27U, 27U, 27U,
        27U, 27U, 27U, 27U, 27U, 27U, 27U, 27U,
        26U, 26U, 26U, 26U, 26U, 26U, 26U, 26U,
        26U, 26U, 26U, 26U, 26U, 26U, 26U, 26U,
        26U, 26U, 26U, 26U, 26U, 26U, 26U, 26U,
        26U, 26U, 26U, 26U, 26U, 26U, 26U, 26U,
        25U, 25U, 25U, 25U, 25U, 25U, 25U, 25U,
        25U, 25U, 25U, 25U, 25U, 25U, 25U, 25U,
        25U, 25U, 25U, 25U, 25U, 25U, 25U, 25U,
        25U, 25U, 25U, 25U, 25U, 25U, 25U, 25U,
        25U, 25U, 25U, 25U, 25U, 25U, 25U, 25U,
        25U, 25U, 25U, 25U, 25U, 25U, 25U, 25U,
        25U, 25U, 25U, 25U, 25U, 25U, 25U, 25U,
        25U, 25U, 25U, 25U, 25U, 25U, 25U, 25U,
        24U, 24U, 24U, 24U, 24U, 24U, 24U, 24U,
        24U, 24U, 24U, 24U, 24U, 24U, 24U, 24U,
        24U, 24U, 24U, 24U, 24U, 24U, 24U, 24U,
        24U, 24U, 24U, 24U, 24U, 24U, 24U, 24U,
        24U, 24U, 24U, 24U, 24U, 24U, 24U, 24U,
        24U, 24U, 24U, 24U, 24U, 24U, 24U, 24U,
        24U, 24U, 24U, 24U, 24U, 24U, 24U, 24U,
        24U, 24U, 24U, 24U, 24U, 24U, 24U, 24U,
        24U, 24U, 24U, 24U, 24U, 24U, 24U, 24U,
        24U, 24U, 24U, 24U, 24U, 24U, 24U, 24U,
        24U, 24U, 24U, 24U, 24U, 24U, 24U, 24U,
        24U, 24U, 24U, 24U, 24U, 24U, 24U, 24U,
        24U, 24U, 24U, 24U, 24U, 24U, 24U, 24U,
        24U, 24U, 24U, 24U, 24U, 24U, 24U, 24U,
        24U, 24U, 24U, 24U, 24U, 24U, 24U, 24U,
        24U, 24U, 24U, 24U, 24U, 24U, 24U, 24U
    };
    uint32_t n;
    if (x >= (1U << 16)) {
        if (x >= (1U << 24)) {
            n = 24U;
        }
        else {
            n = 16U;
        }
    }
    else {
        if (x >= (1U << 8)) {
            n = 8U;
        }
        else {
            n = 0U;
        }
    }
    return (uint32_t)clz_lkup[x >> n] - n;
}

(функция CLZ1() немного быстрее, но занимает больше памяти, чем clz32())