我有一个整数输入，它是 2 的幂（1、2、4、8 等）。我希望函数在不使用 log() 的情况下返回位位置。例如，对于上面的输入将分别返回 {0, 1, 2, 3} 对于 C#。另外，如果这可以在 SQL 中完成。
谢谢！
问问题
1770 次
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 回答