Какой самый быстрый / самый эффективный способ найти старший бит (msb) в целом числе в C?

Question

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

Я знаю, что POSIX поддерживает метод ffs() в strings.h для поиска первого установленного бита, но, похоже, нет соответствующего метода fls().

Есть ли какой-то действительно очевидный способ сделать это, которого мне не хватает?

Что делать в случаях, когда вы не можете использовать функции POSIX для переносимости?

Редактировать: А как насчет решения, которое работает как на 32-, так и на 64-битных архитектурах (многие списки кода кажутся работающими только на 32-битных целых числах).

Answer 1

Я знаю, что этот вопрос очень старый, но я просто реализовал функцию msb () , Я обнаружил, что большинство решений, представленных здесь и на других веб-сайтах, не обязательно являются наиболее эффективными - по крайней мере, для моего личного определения эффективности (см. Также Обновление ниже). И вот почему:

Большинство решений (особенно те, которые используют какую-то схему двоичного поиска или наивный подход, который выполняет линейное сканирование справа налево), похоже, игнорируют тот факт, что для произвольных двоичных чисел не так много, которые начинаются с очень длинная последовательность нулей. Фактически, для любой битовой ширины половина всех целых чисел начинается с 1 , а четверть из них начинается с 01 . Видишь, куда я клоню? Мой аргумент состоит в том, что линейное сканирование , начинающееся от старшей значащей позиции бита к наименее значимой (слева направо), не настолько "линейно", как может показаться на первый взгляд.

Можно показать ¹ , что для любой битовой ширины среднее число битов, которые необходимо проверить, составляет не более 2. Это означает амортизированную сложность времени O (1) относительно количества бит (!).

Конечно, худший случай все еще O (n) , хуже, чем O (log (n)) вы получаете подходы с бинарным поиском, но так как наихудших случаев очень мало, они незначительны для большинства приложений ( Обновление : не совсем: их может быть немного, но они может произойти с большой вероятностью - см. Обновление ниже).

Вот предложенный мной «наивный» подход, который по крайней мере на моей машине превосходит большинство других подходов (схемы двоичного поиска для 32-битных целых всегда требуют log ₂ (32) = 5 шагов, тогда как этот глупый алгоритм требует в среднем менее 2) - извините за то, что это C ++, а не чистый C:

template <typename T>
auto msb(T n) -> int
{
    static_assert(std::is_integral<T>::value && !std::is_signed<T>::value,
        "msb<T>(): T must be an unsigned integral type.");

    for (T i = std::numeric_limits<T>::digits - 1, mask = 1 << i; i >= 0; --i, mask >>= 1)
    {
        if ((n & mask) != 0)
            return i;
    }

    return 0;
}

Обновление : Хотя то, что я здесь написал, совершенно верно для произвольных целых чисел, где каждая комбинация битов одинаково вероятна (мой тест скорости просто измерял, как Потребовалось много времени, чтобы определить MSB для всех 32-разрядных целых чисел), реальных целых чисел, для которых будет вызываться такая функция, обычно по другому шаблону: в моем коде, например, эта функция используется для определения, является ли размер объекта степенью 2, или для нахождения следующей степени 2, большей или равной размера объекта . Я предполагаю, что большинство приложений, использующих MSB, содержат числа, которые намного меньше максимального числа, которое может представлять целое число (размеры объектов редко используют все биты в size_t ). В этом случае мое решение на самом деле будет работать хуже, чем метод бинарного поиска, поэтому последний вариант, вероятно, предпочтительнее, хотя мое решение будет быстрее проходить по всем целым числам.
TL; DR: Реальные целые числа, вероятно, будут иметь тенденцию к худшему случаю этого простого алгоритма, который в итоге ухудшит его производительность - несмотря на то, что он амортизируется O (1) для действительно произвольных целых чисел.

¹ Аргумент выглядит следующим образом (черновик): Пусть n будет количеством бит (ширина в битах). Всего имеется 2 ⁿ целых чисел, которые могут быть представлены n бит. Есть 2 ^{n - 1} целых чисел, начинающихся с 1 (первое 1 фиксировано, остальные n - 1 биты могут быть чем угодно). Эти целые числа требуют только одного взаимодействия цикла для определения MSB. Далее, есть 2 ^{n - 2} целых чисел, начинающихся с 01 , требующих 2 итерации, 2 ^{n - 3} целые числа, начинающиеся с 001 , требующие 3 итерации и т. д.

Если мы суммируем все необходимые итерации для всех возможных целых чисел и разделим их на 2 ⁿ , общее число целых чисел, мы получим среднее число итераций, необходимое для определения MSB для n -битных целых чисел:

(1 * 2 ^{n - 1} + 2 * 2 ^{n - 2} + 3 * 2 ^{n - 3} + ... + n) / 2 ⁿ

Эта серия средних итераций фактически сходится и имеет предел 2 для n в направлении бесконечности

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

Answer 2

Обратите внимание, что вы пытаетесь вычислить целое число log2 из целого числа,

#include <stdio.h>
#include <stdlib.h>

unsigned int
Log2(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1; int k=0;
    for( step = 1; step < bits; ) {
        n |= (n >> step);
        step *= 2; ++k;
    }
    //printf("%ld %ld\n",x, (x - (n >> 1)) );
    return(x - (n >> 1));
}

Обратите внимание, что вы можете пытаться искать более 1 бита за раз.

unsigned int
Log2_a(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1;
    int step2 = 0;
    //observe that you can move 8 bits at a time, and there is a pattern...
    //if( x>1<<step2+8 ) { step2+=8;
        //if( x>1<<step2+8 ) { step2+=8;
            //if( x>1<<step2+8 ) { step2+=8;
            //}
        //}
    //}
    for( step2=0; x>1L<<step2+8; ) {
        step2+=8;
    }
    //printf("step2 %d\n",step2);
    for( step = 0; x>1L<<(step+step2); ) {
        step+=1;
        //printf("step %d\n",step+step2);
    }
    printf("log2(%ld) %d\n",x,step+step2);
    return(step+step2);
}

Этот подход использует бинарный поиск

unsigned int
Log2_b(unsigned long x)
{
    unsigned long n = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int hbit = bits-1;
    unsigned int lbit = 0;
    unsigned long guess = bits/2;
    int found = 0;

    while ( hbit-lbit>1 ) {
        //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        //when value between guess..lbit
        if( (x<=(1L<<guess)) ) {
           //printf("%ld < 1<<%d %ld\n",x,guess,1L<<guess);
            hbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
        //when value between hbit..guess
        //else
        if( (x>(1L<<guess)) ) {
            //printf("%ld > 1<<%d %ld\n",x,guess,1L<<guess);
            lbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
    }
    if( (x>(1L<<guess)) ) ++guess;
    printf("log2(x%ld)=r%d\n",x,guess);
    return(guess);
}

Другой метод двоичного поиска, возможно, более читабельный,

unsigned int
Log2_c(unsigned long x)
{
    unsigned long v = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int step = bits;
    unsigned int res = 0;
    for( step = bits/2; step>0; )
    {
        //printf("log2(%ld) v %d >> step %d = %ld\n",x,v,step,v>>step);
        while ( v>>step ) {
            v>>=step;
            res+=step;
            //printf("log2(%ld) step %d res %d v>>step %ld\n",x,step,res,v);
        }
        step /= 2;
    }
    if( (x>(1L<<res)) ) ++res;
    printf("log2(x%ld)=r%ld\n",x,res);
    return(res);
}

И поскольку вы захотите проверить это,

int main()
{
    unsigned long int x = 3;
    for( x=2; x<1000000000; x*=2 ) {
        //printf("x %ld, x+1 %ld, log2(x+1) %d\n",x,x+1,Log2(x+1));
        printf("x %ld, x+1 %ld, log2_a(x+1) %d\n",x,x+1,Log2_a(x+1));
        printf("x %ld, x+1 %ld, log2_b(x+1) %d\n",x,x+1,Log2_b(x+1));
        printf("x %ld, x+1 %ld, log2_c(x+1) %d\n",x,x+1,Log2_c(x+1));
    }
    return(0);
}

Answer 3

Включение этого, поскольку это «еще один» подход, похоже, отличается от других, которые уже были даны.

возвращает -1, если x==0, в противном случае floor( log2(x)) (максимальный результат 31)

Уменьшите проблему с 32 до 4 бит, затем используйте таблицу. Возможно, не элегантный, но прагматичный.

Это то, что я использую, когда не хочу использовать __builtin_clz из-за проблем с переносимостью.

Чтобы сделать его более компактным, вместо этого можно использовать цикл сокращения, добавляя 4 к r каждый раз, максимум 7 итераций. Или некоторый гибрид, такой как (для 64 бит): цикл, чтобы уменьшить до 8, тест, чтобы уменьшить до 4.

int log2floor( unsigned x ){
   static const signed char wtab[16] = {-1,0,1,1, 2,2,2,2, 3,3,3,3,3,3,3,3};
   int r = 0;
   unsigned xk = x >> 16;
   if( xk != 0 ){
       r = 16;
       x = xk;
   }
   // x is 0 .. 0xFFFF
   xk = x >> 8;
   if( xk != 0){
       r += 8;
       x = xk;
   }
   // x is 0 .. 0xFF
   xk = x >> 4;
   if( xk != 0){
       r += 4;
       x = xk;
   }
   // now x is 0..15; x=0 only if originally zero.
   return r + wtab[x];
}

Answer 4

Я предполагаю, что ваш вопрос касается целого числа (называемого v ниже), а не целого числа без знака.

int v = 612635685; // whatever value you wish

unsigned int get_msb(int v)
{
    int r = 31;                         // maximum number of iteration until integer has been totally left shifted out, considering that first bit is index 0. Also we could use (sizeof(int)) << 3 - 1 instead of 31 to make it work on any platform.

    while (!(v & 0x8000000) && r--) {   // mask of the highest bit
        v <<= 1;                        // multiply integer by 2.
    }
    return r;                           // will even return -1 if no bit was set, allowing error catch
}

Если вы хотите, чтобы это работало без учета знака, вы можете добавить дополнительную 'v << = 1;' перед циклом (и измените значение r на 30 соответственно). Пожалуйста, дайте мне знать, если я что-то забыл. Я не проверял его, но он должен работать просто отлично. </p>

Answer 5

Другой плакат предоставил справочную таблицу , использующую широкий байт справочник. Если вы хотите повысить производительность (за счет 32 КБ памяти вместо 256 записей поиска), вот решение, использующее 15-битную таблицу поиска , в C # 7 для .NET .

Интересная часть - инициализация таблицы. Поскольку это относительно небольшой блок, который мы хотим использовать на протяжении всего жизненного цикла, я выделяю для этого неуправляемую память с помощью Marshal.AllocHGlobal. Как видите, для максимальной производительности весь пример записан как нативный:

readonly static byte[] msb_tab_15;

// Initialize a table of 32768 bytes with the bit position (counting from LSB=0)
// of the highest 'set' (non-zero) bit of its corresponding 16-bit index value.
// The table is compressed by half, so use (value >> 1) for indexing.
static MyStaticInit()
{
    var p = new byte[0x8000];

    for (byte n = 0; n < 16; n++)
        for (int c = (1 << n) >> 1, i = 0; i < c; i++)
            p[c + i] = n;

    msb_tab_15 = p;
}

Таблица требует одноразовой инициализации с помощью кода выше. Он доступен только для чтения, поэтому для одновременного доступа может использоваться одна глобальная копия. С помощью этой таблицы вы можете быстро найти целое число log ₂ , которое мы здесь ищем, для всех различных целочисленных значений ширины (8, 16, 32 и 64). биты).

Обратите внимание, что записи таблицы для 0, единственного целого числа, для которого понятие «старший бит установки» не определено, присваивается значение -1. Это различие необходимо для правильной обработки 0-значных верхних слов в приведенном ниже коде. Без дальнейших церемоний, вот код для каждого из различных целочисленных примитивов:

ulong (64-битная) версия

/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(this ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 0x40) - 1;      // handles cases v==0 and MSB==63

    int j = /**/ (int)((0xFFFFFFFFU - v /****/) >> 58) & 0x20;
    j |= /*****/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 0x10;
    return j + msb_tab_15[v >> (j + 1)];
}

uint (32-разрядная) версия

/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(uint v)
{
    if ((int)v <= 0)
        return (int)((v >> 26) & 0x20) - 1;     // handles cases v==0 and MSB==31

    int j = (int)((0x0000FFFFU - v) >> 27) & 0x10;
    return j + msb_tab_15[v >> (j + 1)];
}

Различные перегрузки для вышеуказанного

public static int HighestOne(long v) => HighestOne((ulong)v);
public static int HighestOne(int v) => HighestOne((uint)v);
public static int HighestOne(ushort v) => msb_tab_15[v >> 1];
public static int HighestOne(short v) => msb_tab_15[(ushort)v >> 1];
public static int HighestOne(char ch) => msb_tab_15[ch >> 1];
public static int HighestOne(sbyte v) => msb_tab_15[(byte)v >> 1];
public static int HighestOne(byte v) => msb_tab_15[v >> 1];

Это законченное, работающее решение, которое представляет лучшую производительность в .NET 4.7.2 для множества альтернатив, которые я сравнил со специализированным тестом производительности. Некоторые из них упомянуты ниже. Параметры теста представляли собой одинаковую плотность всех 65-битовых позиций, то есть 0 ... 31/63 плюс значение 0 (которое дает результат -1). Биты ниже целевой позиции индекса были заполнены случайным образом. Тесты были только x64 , режим выпуска с включенной JIT-оптимизацией.

Это конец моего официального ответа здесь; ниже приведены некоторые случайные заметки и ссылки на исходный код для альтернативных кандидатов, связанных с тестированием, которое я провел, чтобы проверить производительность и правильность приведенного выше кода.

---

Версия, представленная выше, закодированная как Tab16A, была последовательным победителем на многих трассах Эти различные кандидаты, в активной рабочей / скретч-форме, можно найти здесь , здесь и здесь .

 1  candidates.HighestOne_Tab16A               622,496
 2  candidates.HighestOne_Tab16C               628,234
 3  candidates.HighestOne_Tab8A                649,146
 4  candidates.HighestOne_Tab8B                656,847
 5  candidates.HighestOne_Tab16B               657,147
 6  candidates.HighestOne_Tab16D               659,650
 7  _highest_one_bit_UNMANAGED.HighestOne_U    702,900
 8  de_Bruijn.IndexOfMSB                       709,672
 9  _old_2.HighestOne_Old2                     715,810
10  _test_A.HighestOne8                        757,188
11  _old_1.HighestOne_Old1                     757,925
12  _test_A.HighestOne5  (unsafe)              760,387
13  _test_B.HighestOne8  (unsafe)              763,904
14  _test_A.HighestOne3  (unsafe)              766,433
15  _test_A.HighestOne1  (unsafe)              767,321
16  _test_A.HighestOne4  (unsafe)              771,702
17  _test_B.HighestOne2  (unsafe)              772,136
18  _test_B.HighestOne1  (unsafe)              772,527
19  _test_B.HighestOne3  (unsafe)              774,140
20  _test_A.HighestOne7  (unsafe)              774,581
21  _test_B.HighestOne7  (unsafe)              775,463
22  _test_A.HighestOne2  (unsafe)              776,865
23  candidates.HighestOne_NoTab                777,698
24  _test_B.HighestOne6  (unsafe)              779,481
25  _test_A.HighestOne6  (unsafe)              781,553
26  _test_B.HighestOne4  (unsafe)              785,504
27  _test_B.HighestOne5  (unsafe)              789,797
28  _test_A.HighestOne0  (unsafe)              809,566
29  _test_B.HighestOne0  (unsafe)              814,990
30  _highest_one_bit.HighestOne                824,345
30  _bitarray_ext.RtlFindMostSignificantBit    894,069
31  candidates.HighestOne_Naive                898,865

Примечательно, что ужасная производительность ntdll.dll!RtlFindMostSignificantBit через P / Invoke:

[DllImport("ntdll.dll"), SuppressUnmanagedCodeSecurity, SecuritySafeCritical]
public static extern int RtlFindMostSignificantBit(ulong ul);

Это действительно очень плохо, потому что вот вся действительная функция:

    RtlFindMostSignificantBit:
        bsr rdx, rcx  
        mov eax,0FFFFFFFFh  
        movzx ecx, dl  
        cmovne      eax,ecx  
        ret

Я не могу себе представить низкую производительность, вызванную этими пятью линиями, поэтому виноваты штрафы за управляемый / нативный переход. Я также был удивлен, что тестирование действительно отдало предпочтение 32-килобайтным (и 64-килобайтным) short (16-битным) таблицам прямого просмотра по сравнению с 128-байтовыми (и 256-байтовыми) byte (8-битными) таблицами поиска. Я думал, что следующее будет более конкурентоспособным с 16-разрядными поисками, но последний последовательно превосходил это:

public static int HighestOne_Tab8A(ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 64) - 1;

    int j;
    j =  /**/ (int)((0xFFFFFFFFU - v) >> 58) & 32;
    j += /**/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 16;
    j += /**/ (int)((0x000000FFU - (v >> j)) >> 60) & 8;
    return j + msb_tab_8[v >> j];
}

Последнее, на что я укажу, это то, что я был шокирован тем, что мой метод Дебрюйна не стал лучше. Это метод, который я ранее использовал повсеместно:

const ulong N_bsf64 = 0x07EDD5E59A4E28C2,
            N_bsr64 = 0x03F79D71B4CB0A89;

readonly public static sbyte[]
bsf64 =
{
    63,  0, 58,  1, 59, 47, 53,  2, 60, 39, 48, 27, 54, 33, 42,  3,
    61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22,  4,
    62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21,
    56, 45, 25, 31, 35, 16,  9, 12, 44, 24, 15,  8, 23,  7,  6,  5,
},
bsr64 =
{
     0, 47,  1, 56, 48, 27,  2, 60, 57, 49, 41, 37, 28, 16,  3, 61,
    54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11,  4, 62,
    46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
    25, 39, 14, 33, 19, 30,  9, 24, 13, 18,  8, 12,  7,  6,  5, 63,
};

public static int IndexOfLSB(ulong v) =>
    v != 0 ? bsf64[((v & (ulong)-(long)v) * N_bsf64) >> 58] : -1;

public static int IndexOfMSB(ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 64) - 1;

    v |= v >> 1; v |= v >> 2;  v |= v >> 4;   // does anybody know a better
    v |= v >> 8; v |= v >> 16; v |= v >> 32;  // way than these 12 ops?
    return bsr64[(v * N_bsr64) >> 58];
}

Существует много дискуссий о том, насколько превосходны и велики методы Дебрюйна по этому такому вопросу , и я склонен был согласиться. Я предполагаю, что, хотя методы deBruijn и таблицы прямого просмотра (которые я нашел наиболее быстрыми) должны выполнять поиск в таблице, и оба имеют очень минимальное ветвление, только у deBruijn есть операция 64-битного умножения. Я протестировал здесь только функции IndexOfMSB, а не deBruijn IndexOfLSB - но я ожидаю, что последний получит гораздо больше шансов, поскольку у него намного меньше операций (см. Выше), и я, вероятно, буду продолжать его использовать для LSB.

Answer 6

код:

    // x>=1;
    unsigned func(unsigned x) {
    double d = x ;
    int p= (*reinterpret_cast<long long*>(&d) >> 52) - 1023;
    printf( "The left-most non zero bit of %d is bit %d\n", x, p);
    }

Или получить целую часть инструкции FPU FYL2X (Y * Log2 X), установив Y = 1