找位的位置，而无需使用日志（） [英] Find bit position without using Log()
问题描述
我有一个整数输入是2（1，2，4，8等）的功率。我想函数返回位的位置，而无需使用日志（）。例如，对于输入的上述返回{0，1，2，3}分别此对C＃。另外，如果这个可以在SQL中完成。
I have an integer input that is power of 2 (1, 2, 4, 8 etc). I want the function to return bit position without using log(). For example, for inputs above will return {0, 1, 2, 3} respectively This for C#. Plus if this can be done in SQL.
谢谢！
推荐答案
最快的code，我发现这样做是从位操作黑客网站。具体地，查找基于该DeBruijn序列。请参见 http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn
The fastest code I found to do this is from the Bit Twiddling Hacks site. Specifically, the lookup based on the DeBruijn sequence. See http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn
我测试了天真的方法，基于交换机的方法，以及两个位操作黑客方法：DeBruijn序列，并说其他的，如果你知道你的价值是二的幂。
I tested a naive method, a switch-based method, and two of the Bit Twiddling Hacks methods: the DeBruijn sequence, and the other that says, "if you know your value is a power of two."
我跑所有这些反对的两32000000权力的数组。即，形式2 ^ N，其中N的范围是0..30的整数。的2 ^ 31的值是一个负数，这会导致幼稚方法进入无限循环。
I ran all of these against an array of 32 million powers of two. That is, integers of the form 2^N, where N is in the range 0..30. A value of 2^31 is a negative number, which causes the naive method to go into an infinite loop.
我编译code在释放模式Visual Studio 2010和运行它没有调试器（即按Ctrl + F5）。在我的系统，在几十个运行的平均值是：
I compiled the code with Visual Studio 2010 in release mode and ran it without the debugger (i.e. Ctrl+F5). On my system, the averages over several dozen runs are:
- 天真方法：950毫秒
- 切换方法：660毫秒
- Bithack方法1：1154毫秒
- DeBruijn：105毫秒
很明显，该DeBruijn序列的方法是比别人快得多。另Bithack方法不如在这里，因为从C到一些效率低下的C＃成果转化。例如，C语句， INT R =（V和b [0]）= 0;！结束需要一个如果或三元经营者（即？:)在C＃。
It's clear that the DeBruijn sequence method is much faster than any of the others. The other Bithack method is inferior here because the conversion from C to C# results in some inefficiencies. For example, the C statement int r = (v & b[0]) != 0; ends up requiring an if or a ternary operator (i.e. ?:) in C#.
这里的code。
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 code，它的时间是一样的时间为switch语句方法
If I optimize the Bithack code by unrolling the loop and using constants instead of array lookups, its time is the same as the time for the switch statement method.
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;
}
这篇关于找位的位置，而无需使用日志（）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
