在不使用Log（）的情况下查找位的位置

Question

我有一个2的幂的整数输入（1、2、4、8等）。我希望函数不使用log（）返回位位置。例如，对于上述输入，对于C＃，将分别返回{0,1,2,3}。另外，如果可以在SQL中完成。

谢谢！

Answer 1

我发现执行此操作最快的代码来自Bit Twiddling
Hacks网站。具体而言，基于DeBruijn序列的查找。参见http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn

我测试了一个朴素的方法，一个基于开关的方法以及两个Bit Twiddling
Hacks方法：DeBruijn序列，另一个表示“如果您知道自己的价值是2的幂”。

我将所有这些与3200万的2的幂进行比较。也就是说，形式为2 ^ N的整数，其中N在0..30的范围内。2 ^
31的值是负数，这会使幼稚的方法陷入无限循环。

我在发布模式下使用Visual Studio 2010编译了代码，然后在没有调试器（即Ctrl +
F5）的情况下运行了该代码。在我的系统上，数十次运行的平均值是：

• 天真的方法：950毫秒
• 切换方式：660毫秒
• Bithack方法1：1,154毫秒
• DeBruijn：105毫秒

显然，DeBruijn序列方法比任何其他方法都快得多。另一个Bithack方法在这里较差，因为从C到C＃的转换会导致效率低下。例如，C语句int 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;
}