Вопрос по sql, c# – Найти битовую позицию без использования Log ()

1

У меня есть целочисленный вход, который является степенью 2 (1, 2, 4, 8 и т. Д.). Я хочу, чтобы функция возвращала позицию бита без использования log (). Например, для входных данных выше вернется {0, 1, 2, 3} соответственно Это для C #. Плюс, если это можно сделать в SQL.

Спасибо!

Bit Twiddling Hacks L.B
Вы не хотите использоватьMath.Log из C #? Ritch Melton
@phoog - Что? Я просил разъяснений. Ritch Melton
Или, более конкретно:graphics.stanford.edu/~seander/bithacks.html#IntegerLog Jim Mischel
@RitchMelton Math.Log будет намного медленнее. Скорее всего, это не будет проблемой, но, очевидно, в некоторых случаях это будет. phoog

Ваш Ответ

6   ответов
5

чтобы проверить это, но вы хотели что-то подобное?

public static int Foo(int n)
{
    if (n <= 0)
    {
        return -1; // A weird value is better than an infinite loop.
    }
    int i = 0;
    while (n % 2 == 0)
    {
        n /= 2;
        i++;
    }

    return i;
}
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded(int)Math.Pow(2, someint)Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededn & 1Error: User Rate Limit Exceededn >>= 1?
0

ько одним битом), закодированном в C (не знаю о C #)

Это возвращает битовую позицию 1..8 - вам может понадобиться уменьшить результат для индексации 0..7.

int pos(int a){
    int p = (a & 3) | ((a >> 1) & 6) | ((a >> 2) & 5) | ((a >> 3) & 4) | ((a >> 4) & 15) | ((a >> 5) & 2) | ((a >> 6) & 1);
    return p;
}

Для получения информации о «эволюции» фрагмента кода см. мой пост здесьhttp://blog.edutoolbox.de/?p=263

EDIT:

Стиль де Брейн примерно в 100 раз быстрее ...

2

1] На вашем языке найдите конструкцию, которая преобразует число в основание 2.

2] преобразовать значение base-2 в строку

3] возвращает длину строки минус 1.

1

if (x < 1)
    throw SomeException();
if (x < 2)
    return 0;
if (x < 4)
    return 1;
if (x < 8)
    return 2;
//.... etc.

Это не включает ни деление, ни преобразование в двойное число. Требуются только сравнения, которые очень быстрые. УвидетьКод завершен, 2-е издание, стр. 633, для обсуждения.

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

switch (input)
{
    case 1:
        return 0;
    case 2:
        return 1;
    case 4:
        return 2;
    case 8:
        return 3;
    //...
    default:
        throw SomeException();
}

Я проверил производительность на 10 млн. Случайных целочисленных значений и на 10 млн. Случайно выбранных степеней двух. Результаты, достижения:

Bithacks 1: 1360 milliseconds Bithacks 2: 1103 milliseconds If: 1320 milliseconds Bithacks 1 (powers of 2): 1335 milliseconds Bithacks 2 (powers of 2): 1060 milliseconds Bithacks 3 (powers of 2): 1286 milliseconds If (powers of 2): 1026 milliseconds Switch (powers of 2): 896 milliseconds

Я увеличил количество итераций в десять раз и получил следующие результаты:

Bithacks 1: 13347 milliseconds Bithacks 2: 10370 milliseconds If: 12918 milliseconds Bithacks 1 (powers of 2): 12528 milliseconds Bithacks 2 (powers of 2): 10150 milliseconds Bithacks 3 (powers of 2): 12384 milliseconds If (powers of 2): 9969 milliseconds Switch (powers of 2): 8937 milliseconds

Теперь я не проводил профилирование, чтобы посмотреть, не сделал ли я что-то глупое в переводе битовых хаков в код C #, а также чтобы посмотреть, сколько времени выполнения тратится на функцию, которая вычисляет журнал. Так что это всего лишь расчёт за пределами конверта, но он предполагает, что подход if примерно такой же, как алгоритмы битового взлома, а switch немного быстрее. Дополнительно,the if and switch approaches are far easier to understand and maintain.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededgraphics.stanford.edu/~seander/bithacks.html#IntegerLogError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
1

int bitpos=-1;
while(num>0) {
    num = num>>1;
    bitpos++;
}
return bitpos;

Для SQL используйтеCASE, Вы можете сделать бинарный поиск, используя вложенныеIF....ELSE если производительность является проблемой. Но только с 32 возможными значениями затраты на его реализацию могут быть намного больше, чем просто последовательный поиск.

Error: User Rate Limit ExceedednumError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
3

который я нашел для этого, взят с сайта Bit Twiddling Hacks. В частности, поиск основан на последовательности DeBruijn. Увидетьhttp://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn

Я протестировал наивный метод, метод на основе коммутатора и два метода Bit Twiddling Hacks: последовательность DeBruijn и другой, который говорит: «Если вы знаете, что ваше значение является степенью двойки».

Я управлял всем этим с массивом из 32 миллионов сил двоих. То есть целые числа вида 2 ^ N, где N находится в диапазоне 0..30. Значение 2 ^ 31 является отрицательным числом, которое приводит к тому, что наивный метод входит в бесконечный цикл.

Я скомпилировал код с Visual Studio 2010 в режиме выпуска и запустил его без отладчика (т.е. Ctrl + F5). В моей системе средние значения за несколько десятков прогонов:

Naive method: 950 ms Switch method: 660 ms Bithack method 1: 1,154 ms DeBruijn: 105 ms

Понятно, что метод последовательности Дебрюйна намного быстрее, чем любой другой. Другой метод Bithack здесь уступает, потому что преобразование из C в C # приводит к некоторой неэффективности. Например, оператор Cint r = (v & b[0]) != 0; в конечном итоге требуетif или троичный оператор (т.е.? :) в C #.

Вот код.

class Program
{
    const int Million = 1000 * 1000;
    static readonly int NumValues = 32 * Million;

    static void Main(string[] args)
    {
        // Construct a table of integers.
        // These are random powers of two.
        // That is 2^N, where N is in the range 0..31.
        Console.WriteLine("Constructing table");
        int[] values = new int[NumValues];
        Random rnd = new Random();
        for (int i = 0; i < NumValues; ++i)
        {
            int pow = rnd.Next(31);
            values[i] = 1 << pow;
        }

        // Run each one once to make sure it's JITted
        GetLog2_Bithack(values[0]);
        GetLog2_DeBruijn(values[0]);
        GetLog2_Switch(values[0]);
        GetLog2_Naive(values[0]);

        Stopwatch sw = new Stopwatch();
        Console.Write("GetLog2_Naive ... ");
        sw.Restart();
        for (int i = 0; i < NumValues; ++i)
        {
            GetLog2_Naive(values[i]);
        }
        sw.Stop();
        Console.WriteLine("{0:N0} ms", sw.ElapsedMilliseconds);

        Console.Write("GetLog2_Switch ... ");
        sw.Restart();
        for (int i = 0; i < NumValues; ++i)
        {
            GetLog2_Switch(values[i]);
        }
        sw.Stop();
        Console.WriteLine("{0:N0} ms", sw.ElapsedMilliseconds);

        Console.Write("GetLog2_Bithack ... ");
        sw.Restart();
        for (int i = 0; i < NumValues; ++i)
        {
            GetLog2_Bithack(values[i]);
        }
        Console.WriteLine("{0:N0} ms", sw.ElapsedMilliseconds);

        Console.Write("GetLog2_DeBruijn ... ");
        sw.Restart();
        for (int i = 0; i < NumValues; ++i)
        {
            GetLog2_DeBruijn(values[i]);
        }
        sw.Stop();
        Console.WriteLine("{0:N0} ms", sw.ElapsedMilliseconds);


        Console.ReadLine();
    }

    static int GetLog2_Naive(int v)
    {
        int r = 0;
        while ((v = v >> 1) != 0)
        {
            ++r;
        }
        return r;
    }

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

    static int GetLog2_DeBruijn(int v)
    {
        return MultiplyDeBruijnBitPosition2[(uint)(v * 0x077CB531U) >> 27];
    }

    static readonly uint[] b = new uint[] { 0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00, 0xFFFF0000};

    static int GetLog2_Bithack(int v)
    {
        int r = (v & b[0]) == 0 ? 0 : 1;
        int x = 1 << 4;
        for (int i = 4; i > 0; i--) // unroll for speed...
        {
            if ((v & b[i]) != 0)
                r |= x;
            x >>= 1;
        }
        return r;
    }

    static int GetLog2_Switch(int v)
    {
        switch (v)
        {
            case 0x00000001: return 0;
            case 0x00000002: return 1;
            case 0x00000004: return 2;
            case 0x00000008: return 3;
            case 0x00000010: return 4;
            case 0x00000020: return 5;
            case 0x00000040: return 6;
            case 0x00000080: return 7;
            case 0x00000100: return 8;
            case 0x00000200: return 9;
            case 0x00000400: return 10;
            case 0x00000800: return 11;
            case 0x00001000: return 12;
            case 0x00002000: return 13;
            case 0x00004000: return 14;
            case 0x00008000: return 15;
            case 0x00010000: return 16;
            case 0x00020000: return 17;
            case 0x00040000: return 18;
            case 0x00080000: return 19;
            case 0x00100000: return 20;
            case 0x00200000: return 21;
            case 0x00400000: return 22;
            case 0x00800000: return 23;
            case 0x01000000: return 24;
            case 0x02000000: return 25;
            case 0x04000000: return 26;
            case 0x08000000: return 27;
            case 0x10000000: return 28;
            case 0x20000000: return 29;
            case 0x40000000: return 30;
            case int.MinValue: return 31;
            default:
                return -1;
        }
    }
}

Если я оптимизирую код Bithack, развернув цикл и используя константы вместо поиска в массиве, его время совпадает со временем для метода оператора switch.

static int GetLog2_Bithack(int v)
{
    int r = ((v & 0xAAAAAAAA) != 0) ? 1 : 0;
    if ((v & 0xFFFF0000) != 0) r |= (1 << 4);
    if ((v & 0xFF00FF00) != 0) r |= (1 << 3);
    if ((v & 0xF0F0F0F0) != 0) r |= (1 << 2);
    if ((v & 0xCCCCCCCC) != 0) r |= (1 << 1);
    return r;
}
Error: User Rate Limit Exceededr = (v > 0xFFFF) << 4Error: User Rate Limit Exceededr |= ((v & b[i]) != 0) << i;Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded Icerman

Похожие вопросы