2の累乗（1、2、4、8など）の整数入力があります。log（）を使用せずに関数がビット位置を返すようにしたい。たとえば、上記の入力の場合、C＃の場合はそれぞれ{0、1、2、3}これを返します。さらに、これがSQLで実行できる場合。
ありがとう！
質問する
1770 次
6 に答える
5
これをテストするためのVSがMacにありませんが、このようなものが必要でしたか？
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
これを行うために私が見つけた最速のコードは、BitTwiddlingHacksサイトからのものです。具体的には、DeBruijnシーケンスに基づくルックアップ。http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijnを参照してください
ナイーブな方法、スイッチベースの方法、および2つのBit Twiddling Hacksメソッドをテストしました。DeBruijnシーケンスと、「値が2の累乗であることがわかっている場合」というもう1つの方法です。
私はこれらすべてを2の3200万の累乗の配列に対して実行しました。つまり、2 ^ Nの形式の整数です。ここで、Nは0..30の範囲です。2 ^ 31の値は負の数であり、これにより、単純なメソッドが無限ループに入ります。
Visual Studio 2010をリリースモードで使用してコードをコンパイルし、デバッガーなしで実行しました（つまり、Ctrl + F5）。私のシステムでは、数十回の実行の平均は次のとおりです。
- ナイーブな方法：950ミリ秒
- 切り替え方法：660ms
- Bithackメソッド1：1,154ミリ秒
- DeBruijn：105ミリ秒
DeBruijnシーケンスメソッドが他のどのメソッドよりもはるかに高速であることは明らかです。他のBithackメソッドは、CからC＃への変換によって非効率になるため、ここでは劣っています。たとえば、CステートメントはC＃でまたは三項演算子（つまり？:)をint r = (v & b[0]) != 0;必要とすることになります。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;
}
于 2012-04-14T04:26:14.013 に答える
2
0]数値がゼロまたは負の場合、エラーを返す/スローする
1]お使いの言語で、数値を基数2に変換する構成を見つけます。
2]基数2の値を文字列に変換します
3]文字列の長さから1を引いたものを返します。
于 2012-04-13T23:13:23.733 に答える
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
冗長なコードですが、おそらく最速です。
if (x < 1)
throw SomeException();
if (x < 2)
return 0;
if (x < 4)
return 1;
if (x < 8)
return 2;
//.... etc.
これには、除算も double からの変換も含まれません。必要なのは比較のみで、非常に高速です。議論については、 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();
}
1,000 万個のランダムな int と、ランダムに選択された 1,000 万個の 2 のべき乗でパフォーマンスをテストしました。結果：
- Bithacks 1: 1360 ミリ秒
- Bithacks 2: 1103 ミリ秒
- If: 1320 ミリ秒
- Bithacks 1 (2 の累乗): 1335 ミリ秒
- Bithacks 2 (2 の累乗): 1060 ミリ秒
- Bithacks 3 (2 の累乗): 1286 ミリ秒
- (2 の累乗) の場合: 1026 ミリ秒
- スイッチ (2 の累乗): 896 ミリ秒
反復回数を 10 倍に増やしたところ、次の結果が得られました。
- Bithacks 1: 13347 ミリ秒
- Bithacks 2: 10370 ミリ秒
- If: 12918 ミリ秒
- Bithacks 1 (2 の累乗): 12528 ミリ秒
- Bithacks 2 (2 の累乗): 10150 ミリ秒
- Bithacks 3 (2 の累乗): 12384 ミリ秒
- (2 の累乗) の場合: 9969 ミリ秒
- スイッチ (2 の累乗): 8937 ミリ秒
ここで、ビット ハックを C# コードに変換する際に愚かなことをしたかどうかを確認するためのプロファイリングも、ログを計算する関数でどれだけの実行時間が費やされたかを確認するためのプロファイリングも行いませんでした。したがって、これは封筒の裏のような計算ですが、if アプローチはビット ハック アルゴリズムとほぼ同じであり、switch の方が少し高速であることを示唆しています。さらに、if および switch アプローチは、理解と保守がはるかに簡単です。
于 2012-04-13T23:23:37.373 に答える