不使用Log()查找位位置

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

谢谢!

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

我测试了一个简单的方法,一个基于开关的方法,以及两个Bit Twiddling Hacks方法:DeBruijn序列,另一个说“如果你知道你的值是2的幂”。

我把所有这些都用在了3200万两个幂的数组中。 也就是说,forms为2 ^ N的整数,其中N在0..30的范围内。 值2 ^ 31是负数,这导致朴素方法进入无限循环。

我在发布模式下使用Visual Studio 2010编译代码并在没有调试器的情况下运行它(即Ctrl + F5)。 在我的系统上,几十个运行的平均值是:

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

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

这是代码。

 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; } 

我的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; } 

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

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

2]将base-2值转换为string

3]返回字符串的长度减去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 (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毫秒

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

这是一种CPU友好的方式:

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

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

找到以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倍……