の先行ゼロをカウントするにはどうすればよいInt32ですか? だから私がやりたいことは、入力が 2 の場合に 30 を返す関数を書くことです000...0000000000010。
13846 次
15 に答える
26
注dotnet コア >=3.0 を使用していますか? ここを見てください。
例として 20 という数字を考えてみましょう。次のようにバイナリで記述できます。
00000000000000000000000000010100
最初に、最上位ビットを右シフトし、それ自体をビットごとに OR することにより、最上位ビットを下位ビット位置に「塗りつけ」ます。
00000000000000000000000000010100
or 00000000000000000000000000001010 (right-shifted by 1)
is 00000000000000000000000000011110
それから
00000000000000000000000000011110
or 00000000000000000000000000000111 (right-shifted by 2)
is 00000000000000000000000000011111
ここでは、小さい数なので、既に作業は完了していますが、4、8、および 16 ビットのシフトでプロセスを続行することにより、任意の 32 ビット数について、すべてのビットを設定したことを確認できます。 0～元の数字のMSBを1に。
ここで、「塗りつぶされた」結果の 1 の数を数えると、単純に 32 から差し引くことができ、元の値の先行ゼロの数が残ります。
整数に設定されたビットの数をどのように数えますか? このページには、まさにそれを行うための魔法のアルゴリズム (「ツリー削減を実行する可変精度 SWAR アルゴリズム」... 理解できれば、あなたは私よりも賢いです!) があり、C# に次のように変換されます。
int PopulationCount(int x)
{
x -= ((x >> 1) & 0x55555555);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0f0f0f0f);
x += (x >> 8);
x += (x >> 16);
return (x & 0x0000003f);
}
このメソッドを上記の「スミアリング」メソッドでインライン化することにより、整数の先行ゼロをカウントするための非常に高速でループや条件のないメソッドを作成できます。
int LeadingZeros(int x)
{
const int numIntBits = sizeof(int) * 8; //compile time constant
//do the smearing
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
//count the ones
x -= x >> 1 & 0x55555555;
x = (x >> 2 & 0x33333333) + (x & 0x33333333);
x = (x >> 4) + x & 0x0f0f0f0f;
x += x >> 8;
x += x >> 16;
return numIntBits - (x & 0x0000003f); //subtract # of 1s from 32
}
于 2012-05-03T21:06:34.667 に答える
3
これを試して：
static int LeadingZeros(int value)
{
// Shift right unsigned to work with both positive and negative values
var uValue = (uint) value;
int leadingZeros = 0;
while(uValue != 0)
{
uValue = uValue >> 1;
leadingZeros++;
}
return (32 - leadingZeros);
}
于 2012-05-03T21:42:22.630 に答える
2
ここでいくつかの複雑な答えが進行中です。これはどう？
private int LeadingZeroes(int value)
{
return (32 - (Convert.ToString(value, 2).Length));
}
今は、負の数やこのタイプのソリューションには問題があるのではないかと推測しています。
于 2012-05-03T21:08:08.130 に答える
2
Lzcnt 命令をシミュレートするだけの場合は、次のように実行できます (値がゼロの場合は 32 になります)。
int Lzcnt(uint value)
{
//Math.Log(0, 2) is -Infinity, cast to int is 0x80000000
int i=(int)Math.Log(value, 2);
return 31-(i&int.MaxValue)-(i>>31);
}
特定の値を格納するのに必要なビット数を知る必要がある場合は、次のようにします。
1+((int)Math.Log(value, 2)&int.MaxValue)
実際にゼロを格納するには 1 ビットが必要なため、上記ではゼロ値に 1 を指定しています。
ただし、これらは uint でのみ機能し、ulong では機能しません。Double (これは Log メソッドの引数です) は、 ulong を最下位ビットまで格納するのに十分な精度を持っていないため、(double)0xFFFFFFFFFFFFFFと区別できません(double)0x100000000000000。
しかし、.Net Core 3.0 では、最新かつ最高の Lzcnt 命令を利用できるようになりました。したがって、( ulong の場合) のみの場合は、 System.Runtime.Intrinsics.X86.Lzcnt.IsSupported( System.Runtime.Intrinsics.X86.Lzcnt.X64.IsSupportedulong の場合) を使用できます。System.Runtime.Intrinsics.X86.Lzcnt.LeadingZeroCount(value)System.Runtime.Intrinsics.X86.Lzcnt.X64.LeadingZeroCount(value)
しかし、.Net Core 3.0 ではSystem.Numerics.BitOperations.LeadingZeroCount、@phuclv が既にここで述べたように、最新かつ最高のものをついに手に入れました。
于 2019-10-06T17:00:40.463 に答える
0
さあ、「なぜこれをやりたいのか、あれをやりたいのか」と尋ねるのはやめましょう。答えられるか、そのまま続けてください。先行ゼロのカウントは、多くの問題 (圧縮アルゴリズムなど) で一般的なタスクです。専用の x86 ハードウェア命令もあります (clz、bsr)。残念ながら、組み込み関数は (まだ) サポートされていないため、C# でこれらのハードウェア命令を使用することはできません。文字列への変換は冗談だったと思います。
int のバイナリ表現には、非常に明確に定義された境界があります。実際、C# では int は Int32 の単なるエイリアスです。その名前が示すように、「Int32」は、プロジェクトを x64 用にコンパイルした場合でも、常に 32 ビットの符号付き整数です。
また、先頭のゼロを計算するために特別なブードゥー教の魔法は必要ありません。これが機能する簡単な数学ソリューションです。
ここで「x」はint（Int32）です：
int LeadingZeros = (int)(32 - Math.Log((double)x + 1, 2d));
LeadingZeros += (int)((x - (0x80000000u >> LeadingZeros)) >> 31);
編集：申し訳ありませんが、式を確認して修正しました。double 演算の精度エラーのため、結果が正しくない境界ケースがいくつかある場合があります。そのため、まだ「ブードの魔法」が必要です。2 行目はこれらのケースを処理し、正しい結果を生成します。
于 2012-07-10T17:07:35.923 に答える
0
C:
unsigned int
lzc(register unsigned int x)
{
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
return(WORDBITS - ones(x));
}
(からhttp://aggregate.org/MAGIC/#Leading Zero Count)
C# への変換は、読者にとって簡単な課題として残されています。
編集
リンクを提供した理由は、次をコピーする必要がないためです（これもCで）：
#define WORDBITS 32
unsigned int
ones(unsigned int x)
{
/* 32-bit recursive reduction using SWAR...
but first step is mapping 2-bit values
into sum of 2 1-bit values in sneaky way
*/
x -= ((x >> 1) & 0x55555555);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0f0f0f0f);
x += (x >> 8);
x += (x >> 16);
return(x & 0x0000003f);
}
于 2012-05-03T21:03:03.210 に答える
0
private int GetIntegerOffsetLength(int value)
{
return (32 - (Convert.ToString(value, 2).Length);
}
于 2012-05-03T21:07:51.833 に答える
-1
先行ゼロのカウント/最初のセットの検索/ビット スキャンの反転は、OS やその他の低レベル プログラミングで必要とされる一般的なことであり、ほとんどのハードウェアはシングル サイクル命令の形式で clz をサポートしています。また、ほとんどの c/c++ コンパイラにはコンパイラ組み込み関数があります。
http://en.wikipedia.org/wiki/Find_first_set
また、ほとんどのハードウェアとコンパイラには、カウント末尾ゼロ、ポップ カウント/ビット カウント/カウント 1、パリティ、bswap/フリップ エンディエン、およびその他のいくつかの奇抜ですが非常に便利なビット操作があります。
于 2014-02-07T21:50:48.317 に答える
-2
事前に計算されたカウントを使用して最高のパフォーマンスを得ることができます
public static class BitCounter
{
private static readonly int[] _precomputed = new[]
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
public static int CountOn(int value)
{
return _precomputed[value >> 24] +
_precomputed[(value << 8) >> 24] +
_precomputed[(value << 16) >> 24] +
_precomputed[value & 0xFF];
}
public static int CountOff(int value)
{
return 32 - CountOn(value);
}
}
于 2013-09-08T18:29:05.063 に答える
-2
32 - Convert.ToString(2,2).Count()
于 2012-05-03T21:08:29.067 に答える
-4
整数には先行ゼロがなく、32 桁もサポートされていません。そうは言っても、整数を文字列に変換し、長さをチェックすることで、これを行う関数を作成できるはずです。
private int GetIntegerOffsetLength(int value)
{
//change 32 to whatever your upper bound is
return (32 - (value.ToString().Length + 1));
}
于 2012-05-03T21:03:46.113 に答える