Самая быстрая реализация log2 (int) и log2 (float)

Вопрос

Существуют ли другие (и/или более быстрые) реализации базового 2log?

Приложения

Операции log2 (int) и log2 (float) очень полезны во многих разных контекстах. Чтобы назвать несколько: алгоритмы сжатия, 3d-двигатели и машинное обучение. Почти во всех этих контекстах они используются в низкоуровневом коде, который называется миллиардами раз... Особенно полезно использование операции log2 (int).

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

Полный исходный код для проверки всех реализаций добавляется внизу, поэтому вы можете сами убедиться.

И конечно... запустите ваши тесты как минимум 3 раза и убедитесь, что счетчики достаточно большие, чтобы нанести несколько секунд. Также я делаю операцию "добавить", чтобы весь цикл не был магически удален JIT'ter. Поэтому начнем с реальной работы.

Тривиальная реализация

Тривиальная реализация 2log в С#:

(int)(Math.Log(x) / Math.Log(2))

Эта реализация тривиальна, но также очень медленная. Для этого требуется 2 Log-операции, которые уже сами по себе довольно медленные. Конечно, мы можем оптимизировать это, сделав константу 1.0/Math.Log(2).

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

Поиск в таблице

Более быстрым решением для этого является использование справочной таблицы. Хотя вы можете использовать таблицу поиска любой мощности 2, я обычно использую таблицу размером 256 или 64 тыс. записей.

Сначала мы создаем таблицу поиска:

lookup = new int[256];
for (int i = 1; i < 256; ++i)
{
    lookup[i] = (int)(Math.Log(i) / Math.Log(2));
}

Затем мы реализуем 2log следующим образом:

private static int LogLookup(int i)
{
    if (i >= 0x1000000) { return lookup[i >> 24] + 24; }
    else if (i >= 0x10000) { return lookup[i >> 16] + 16; }
    else if (i >= 0x100) { return lookup[i >> 8] + 8; }
    else { return lookup[i]; }
}

Как вы можете видеть, поиск таблиц представляет собой намного более быструю реализацию, но в качестве con он не может быть использован для вычисления log2(float).

Удаление ветвей

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

nobranch = new int[16] { 0, 0, 8, 8, 16, 16, 16, 16, 24, 24, 24, 24, 24, 24, 24, 24 };

private static int LogDoubleLookup(int i)
{
    int n = (i | (i >> 4));
    n = (n | (n >> 2));
    n = (n | (n >> 1));
    n = ((n & 0x1000000) >> 21) | ((n & 0x10000) >> 14) | ((n & 0x100) >> 7) | (n & 1);
    int br = nobranch[n];
    return lookup[i >> br] + br;
}

Если вы запустите этот тест, вы обнаружите, что он на самом деле медленнее, чем решение if-then-else.

И тогда появился Intel 80386

Intel много лет назад поняла, что это важная операция, поэтому они внедрили Bit-Scan-Forward (BSF) в свои процессоры. Другие процессоры имеют схожие инструкции. Это, безусловно, самый быстрый способ сделать 2log, о котором я знаю, но, к сожалению, теперь я знаю, как использовать эти прекрасные функции из С#... Мне не нравится идея иметь реализацию, которая больше не запускается когда на рынок выходит новый планшет или телефон - и я не знаю какого-либо кросс-платформенного решения, которое позволяет мне напрямую использовать эту функцию.

Другие реализации

Как указывалось l4V (спасибо!), есть пара других реализаций, в частности:

Тривиальный цикл. Я пропустил это, потому что это тривиально, это не очень быстро. Реализовано в TestTrivial.
64-битный IEEE/int union, который можно использовать. Реализовано в TestFloat
Таблицы поиска DeBruijn. Реализовано в TestDeBruijn
Двоичный поиск. Реализовано в TestBinary

Кроме того, что мне нравится имя, таблицы поиска DeBruijn так же быстро, как и обычные таблицы поиска, что делает его одним из самых быстрых алгоритмов здесь... все другие алгоритмы, которые я пробовал, намного медленнее.

Полный тестовый код

public class Log2Test
{
    public static void TestNaive()
    {
        Stopwatch sw = new Stopwatch();
        sw.Start();
        int n = 0;
        for (int i = 1; i < 100000000; ++i)
        {
            n += (int)(Math.Log(i) / Math.Log(2.0));
        }
        sw.Stop();
        Console.WriteLine("Result: {0} - naive implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
    }

    public static int LogTrivialLoop(int v)
    {
        int r = 0;
        while ((v >>= 1) > 0) // unroll for more speed...
        {
            r++;
        }
        return r;
    }

    public static void TestTrivialLoop()
    {
        Stopwatch sw = new Stopwatch();
        sw.Start();
        int n = 0;
        for (int i = 1; i < 100000000; ++i)
        {
            n += LogTrivialLoop(i);
        }
        sw.Stop();
        Console.WriteLine("Result: {0} - loop implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
    }

    public static int LogFloat(int v)
    {
        Helper h = new Helper() { U1 = v, U2 = 0x43300000 };
        h.D -= 4503599627370496.0;
        return (h.U2 >> 20) - 0x3FF;
    }

    public static void TestFloat()
    {
        Stopwatch sw = new Stopwatch();
        sw.Start();
        int n = 0;
        for (int i = 1; i < 100000000; ++i)
        {
            n += LogFloat(i);
        }
        sw.Stop();
        Console.WriteLine("Result: {0} - IEEE float implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
    }

    [StructLayout(LayoutKind.Explicit)]
    private struct Helper
    {
        [FieldOffset(0)]
        public int U1;
        [FieldOffset(4)]
        public int U2;
        [FieldOffset(0)]
        public double D;
    }

    public static void TestConstant()
    {
        double c = 1.0 / Math.Log(2.0);
        Stopwatch sw = new Stopwatch();
        sw.Start();
        int n = 0;
        for (int i = 1; i < 100000000; ++i)
        {
            n += (int)(0.00000000001 + Math.Log(i) * c);
        }
        sw.Stop();
        Console.WriteLine("Result: {0} - naive 2 implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
    }

    private static int LogLookup(int i)
    {
        if (i >= 0x1000000) { return lookup[i >> 24] + 24; }
        else if (i >= 0x10000) { return lookup[i >> 16] + 16; }
        else if (i >= 0x100) { return lookup[i >> 8] + 8; }
        else { return lookup[i]; }
    }

    public static void TestLookup()
    {
        lookup = new int[256];
        for (int i = 1; i < 256; ++i)
        {
            lookup[i] = (int)(Math.Log(i) / Math.Log(2));
        }
        Stopwatch sw = new Stopwatch();
        sw.Start();
        int n = 0;
        for (int i = 1; i < 100000000; ++i)
        {
            n += LogLookup(i);
        }
        sw.Stop();
        Console.WriteLine("Result: {0} - table lookup implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
    }

    private static int LogDoubleLookup(int i)
    {
        int n = (i | (i >> 4));
        n = (n | (n >> 2));
        n = (n | (n >> 1));
        n = ((n & 0x1000000) >> 21) | ((n & 0x10000) >> 14) | ((n & 0x100) >> 7) | (n & 1);
        int br = nobranch[n];
        return lookup[i >> br] + br;
    }

    public static void TestDoubleLookup()
    {
        // Lookup table was already constructed earlier
        Stopwatch sw = new Stopwatch();
        sw.Start();
        int n = 0;
        for (int i = 1; i < 100000000; ++i)
        {
            n += LogDoubleLookup(i);
        }
        sw.Stop();
        Console.WriteLine("Result: {0} - double table lookup implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
    }

    private static int LogBinary(int v)
    {
        /* This is the worst implementation ever... - apparently C# is a slow-branching language

        int[] b = { 0x2, 0xC, 0xF0, 0xFF00, 0x7FFF0000 };
        int[] S = { 1, 2, 4, 8, 16 };

        int r = 0; // result of log2(v) will go here
        for (int i = 4; i >= 0; i--) // unroll for speed...
        {
            if ((v & b[i]) != 0)
            {
                v >>= S[i];
                r |= S[i];
            }
        }
        return r;

         */

        int r = (((v > 0xFFFF)) ? 0x10 : 0); 
        v >>= r;
        int shift = ((v > 0xFF) ? 0x8 : 0); 
        v >>= shift; 
        r |= shift;
        shift = ((v > 0xF) ? 0x4 : 0); 
        v >>= shift;
        r |= shift;
        shift = ((v > 0x3) ? 0x2 : 0); 
        v >>= shift;
        r |= shift;
        r |= (v >> 1);
        return r;
    }

    public static void TestBinary()
    {
        // Lookup table was already constructed earlier
        Stopwatch sw = new Stopwatch();
        sw.Start();
        int n = 0;
        for (int i = 1; i < 100000000; ++i)
        {
            n += LogBinary(i);
        }
        sw.Stop();
        Console.WriteLine("Result: {0} - binary search implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
    }

    private static readonly int[] MultiplyDeBruijnBitPosition = new int[32]
    {
        0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
        8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
    };

    private static int LogDeBruijn(int v)
    {
        v |= v >> 1; // first round down to one less than a power of 2 
        v |= v >> 2;
        v |= v >> 4;
        v |= v >> 8;
        v |= v >> 16;

        return MultiplyDeBruijnBitPosition[(uint)(v * 0x07C4ACDDU) >> 27];
    }

    public static void TestDeBruijn()
    {
        // Lookup table was already constructed earlier
        Stopwatch sw = new Stopwatch();
        sw.Start();
        int n = 0;
        for (int i = 1; i < 100000000; ++i)
        {
            n += LogDeBruijn(i);
        }
        sw.Stop();
        Console.WriteLine("Result: {0} - de Bruijn implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
    }

    private static int[] lookup;
    private static readonly int[] nobranch = new int[16] { 0, 0, 8, 8, 16, 16, 16, 16, 24, 24, 24, 24, 24, 24, 24, 24 };

    static void Main(string[] args)
    {
        TestConstant();
        TestNaive();
        TestDeBruijn();
        TestBinary();
        TestFloat();
        TestTrivialLoop();
        TestLookup();
        TestDoubleLookup();
        Console.ReadLine();
    }
}

Ответы

Ответ 1

Здесь есть целые алгоритмы.

В С#:

public static uint FloorLog2(uint x)
{
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);

    return (uint)(NumBitsSet(x) - 1);
}

public static uint CeilingLog2(uint x)
{
    int y = (int)(x & (x - 1));

    y |= -y;
    y >>= (WORDBITS - 1);
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);

    return (uint)(NumBitsSet(x) - 1 - y);
}

public static int NumBitsSet(uint x)
{
    x -= ((x >> 1) & 0x55555555);
    x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
    x = (((x >> 4) + x) & 0x0f0f0f0f);
    x += (x >> 8);
    x += (x >> 16);

    return (int)(x & 0x0000003f);
}

private const int WORDBITS = 32;

Вы должны посмотреть исходный код на сайте, который я связал для контекста, особенно то, что происходит с Log2 (0).

Ответ 2

Взял уже упомянутое двоичное решение и удалил ветвление. Произошло некоторое тестирование, и он оказался в 1,3 раза быстрее, чем DeBruijn.

public static int Log2(int v)
{
    int r = 0xFFFF - v >> 31 & 0x10;
    v >>= r;
    int shift = 0xFF - v >> 31 & 0x8;
    v >>= shift; 
    r |= shift;
    shift = 0xF - v >> 31 & 0x4;
    v >>= shift;
    r |= shift;
    shift = 0x3 - v >> 31 & 0x2;
    v >>= shift;
    r |= shift;
    r |= (v >> 1);
    return r;
}

Ответ 3

Для большего количества алгоритмов смотрите здесь http://www.asmcommunity.net/forums/topic/?id=15010

Также некоторые тесты на С++ и моя реализация BSR медленнее, чем таблица поиска

Я использую BDS2006, вероятно, замедляется нажатием кнопки /popping по директиве asm
ваш поиск в порядке, но я использую 11-битную таблицу вместо 8
он делит 32 бит на 3 ветки вместо 4
и он все еще достаточно мал, чтобы обрабатывать без функции init

код:

//---------------------------------------------------------------------------
DWORD log2_slow(const DWORD &x)
    {
    DWORD m,i;
    if (!x) return 0;
    if (x>=0x80000000) return 31;
    for (m=1,i=0;m<x;m<<=1,i++);
     if (m!=x) i--;
    return i;
    }
//---------------------------------------------------------------------------
DWORD log2_asm(const DWORD &x)
    {
    DWORD xx=x;
    asm {
        mov eax,xx
        bsr eax,eax;
        mov xx,eax;
        }
    return xx;
    }
//---------------------------------------------------------------------------
BYTE _log2[2048]=
    {
     0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
    10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,
    10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,
    10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,
    10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,
    10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,
    10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,
    10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,
    10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,
    };
DWORD log2(const DWORD &x)
    {
         if (x>=0x00400000) return _log2[x>>22]+22;
    else if (x>=0x00000800) return _log2[x>>11]+11;
    else                    return _log2[x];
    }
//---------------------------------------------------------------------------

тестовый код:

DWORD x,j,i,n=256;
tbeg(); for (i=0;i<32;i++) for (j=0;j<n;j++) x=log2     (j<<i); tend(); mm_log->Lines->Add(tstr(1));
tbeg(); for (i=0;i<32;i++) for (j=0;j<n;j++) x=log2_asm (j<<i); tend(); mm_log->Lines->Add(tstr(1));
tbeg(); for (i=0;i<32;i++) for (j=0;j<n;j++) x=log2_slow(j<<i); tend(); mm_log->Lines->Add(tstr(1));

мои результаты на AMD A8-5500 3.2 ГГц:

[   0.040 ms] log2     (x) - 11bit lookup table
[   0.060 ms] log2_asm (x) - BSR
[   0.415 ms] log2_slow(x) - shift loop

Примечание:

log2 (0) → 0 из-за использования DWORDS, в реале он должен быть -inf
все остальные значения верны для всех функций

Ответ 4

inline int fast_log2(register double x)
{ 
    return (reinterpret_cast<uint64_t&>(x) >> 52) - 1023;
};

Ответ 5

Вот что я использовал:

unsigned log2(register unsigned n) {
    register unsigned i;
    for (i=0; (n & 1); n>>=1, i++);
    return i;
}

Изменить: Проверьте их (варианты ffz): https://patchwork.kernel.org/patch/8845631/

Ответ 6

    static byte FloorLog2(UInt16 value)
    {
        for (byte i = 0; i < 15; ++i)
        {
            if ((value >>= 1) < 1)
            {
                return i;
            }
        }
        return 15;
    }

Ответ 7

(Я не делал никаких измерений, поэтому это может не совпадать, но я подумал, что идея user user9337139 была изящной и хотел попробовать то же самое в С# - его C++).

Здесь функция С# int Magnitude(byte), основанная на преобразовании значения байта в число с плавающей запятой и извлечении показателя степени из представления с плавающей запятой IEEE.

    using System.Runtime.InteropServices;

    [StructLayout(LayoutKind.Explicit)]
    struct UnionWorker
    {
        [FieldOffset(0)]
        public int i;
        [FieldOffset(0)]
        public float f;
    }

    static int Magnitude(byte b)
    {
        UnionWorker u;
        u.i = 0; // just to please the compiler
        u.f = b;
        return Math.Max((u.i >> 23) & 0xFF, 126) - 126;
    }

Возвращает ноль для нуля, 8 для 0xFF, другие значения, как и следовало ожидать.

Ноль - это особый случай, поэтому для этого мне понадобился зажим Math.Max. Я подозреваю, что решение user9337139 может иметь похожую проблему.

Обратите внимание, что это не было проверено на предмет порядка байтов - предостережение emptor.

Ответ 8

Вот самая быстрая реализация log2 (int) для С#:

    [StructLayout(LayoutKind.Explicit)]
    private struct ConverterStruct
    {
        [FieldOffset(0)] public int asInt;
        [FieldOffset(0)] public float asFloat;
    }

    public static int Log2(uint val)
    {
        ConverterStruct a;  a.asInt = 0; a.asFloat = val;
        return ((a.asInt >> 23 )+ 1) & 0x1F;
    }

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

Если вы хотите что-то безопасное, то можете проверить spender 3/3/2012. Он также имеет нулевую поддержку.

Вот некоторые тесты: (код здесь: https://github.com/SunsetQuest/Fast-Integer-Log2)

Function                 Time1  Time2    Errors  Full-32-Bit Zero_Support
Log2_SunsetQuest3:        18     18       0        (Y)        (N)
Log2_SunsetQuest4:        18     18       0        (Y)        (N)
Log2_SPWorley:            18     18       0        (Y)        (N)
MostSigBit_spender:       20     19       0        (Y)        (Y)
Log2_HarrySvensson:       26     29       0        (Y)        (N)
Log2_WiegleyJ:            27     23       0        (Y)        (N)
Log2_DanielSig:           28     24    3125        (N)        (N)
FloorLog2_Matthew_Watson: 29     25       0        (Y)        (Y)
Log2_SunsetQuest1:        31     28       0        (Y)        (Y)
HighestBitUnrolled_Kaz:   33     33    3125        (Y)        (Y)
Log2_Flynn1179:           58     52       0        (Y)        (N)
GetMsb_user3177100:       58     53       0        (Y)        (N)
Log2floor_greggo:         89    101       0        (Y)        (Y)
FloorLog2_SN17:          102     43       0        (Y)        (N)
Log2_SunsetQuest2:       118    140       0        (Y)        (Y)
Log2_Papayaved:          125     60       0        (Y)        (N)
Msb_Protagonist:         136    118       0        (Y)        (N)
Log2_SunsetQuest0:       206    202       0        (Y)        (Y)
BitScanReverse2:         228    240    3125        (N)        (Y)
UsingStrings_Rob:       2346   1494       0        (Y)        (N)

Zero_Support = Supports Neg Return on Zero
Full-32-Bit  = Supports full 32-bit (some just support 31 bits)
Time1 = benchmark for sizes up to 32-bit (same number tried for each size)
Time2 = benchmark for sizes up to 16-bit (for measuring perf with small numbers)

Benchmark notes: AMD Ryzen CPU, Release mode, no-debugger attached, .net core 2.1