1

我有一个整数输入,它是 2 的幂(1、2、4、8 等)。我希望函数在不使用 log() 的情况下返回位位置。例如,对于上面的输入将分别返回 {0, 1, 2, 3} 对于 C#。另外,如果这可以在 SQL 中完成。

谢谢!

4

6 回答 6

5

我的 Mac 上没有 VS 来测试这个,但是你想要这样的东西吗?

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;
}
于 2012-04-13T23:11:32.627 回答
3

我发现执行此操作的最快代码来自 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 毫秒
  • 切换方式:660ms
  • Bithack 方法 1:1,154 毫秒
  • 德布鲁因:105 毫秒

很明显,DeBruijn 序列方法比其他任何方法都快得多。另一种 Bithack 方法在这里较差,因为从 C 到 C# 的转换会导致一些低效率。例如,C 语句int r = (v & b[0]) != 0;最终需要ifC# 中的一个或一个三元运算符(即 ?:)。

这是代码。

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;
}
于 2012-04-14T04:26:14.013 回答
2

0] 如果数字为零或负数,则返回/抛出错误

1] 在您的语言中,找到将数字转换为基数 2 的结构。

2] 将 base-2 值转换为字符串

3] 返回字符串长度减1。

于 2012-04-13T23:13:23.733 回答
1

冗长的代码,但可能是最快的:

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

这不涉及除法,也不涉及双重转换。它只需要比较,这是非常快速的。有关讨论,请参见Code Complete,第 2 版,第 633 页。

如果您知道输入始终是 2 的幂,您可能会从 switch 块中获得更好的性能:

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

我在 1000 万个随机整数和 1000 万个随机选择的 2 次方上测试了性能。结果:

  • Bithacks 1:1360 毫秒
  • Bithacks 2:1103 毫秒
  • 如果:1320 毫秒
  • Bithacks 1(2 的幂):1335 毫秒
  • Bithacks 2(2 的幂):1060 毫秒
  • Bithacks 3(2 的幂):1286 毫秒
  • 如果(2 的幂):1026 毫秒
  • 开关(2 的幂):896 毫秒

我将迭代次数增加了十倍,得到了这些结果:

  • Bithacks 1:13347 毫秒
  • Bithacks 2:10370 毫秒
  • 如果:12918 毫秒
  • Bithacks 1(2 的幂):12528 毫秒
  • Bithacks 2(2 的幂):10150 毫秒
  • Bithacks 3(2 的幂):12384 毫秒
  • 如果(2 的幂):9969 毫秒
  • 开关(2 的幂):8937 毫秒

现在我没有做任何分析来查看我是否在将位黑客转换为 C# 代码时做了一些愚蠢的事情,也没有查看计算日志的函数花费了多少执行时间。所以这只是一种粗略的计算,但它确实表明 if 方法与 bit hacks 算法大致相同,并且 switch 更快一些。此外,if 和 switch 方法更容易理解和维护。

于 2012-04-13T23:23:37.373 回答
1

这是一种 CPU 友好的方式:

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

对于 SQL,使用CASE. IF....ELSE如果性能是一个问题,您可以使用嵌套进行二进制搜索。但是只有 32 个可能的值,实现它的开销可能远远超过简单的顺序搜索。

于 2012-04-14T11:00:56.770 回答
-1

在用 C 编码的 2 字节幂(仅设置一个位的 uint8 标志)中查找位位置(不了解 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

编辑:

deBruijn 样式大约快 100 倍...

于 2017-12-03T14:07:10.233 回答