0

包括的な範囲を定義する 2 つの符号なし整数をビット フィールドに変換する必要がある C# で、タイム クリティカルなコードを作成しています。元：

uint x1 = 3;
uint x2 = 9;
  //defines the range [3-9]
  //                              98  7654 3
  //must be converted to:  0000 0011  1111 1000

ビットを逆の順序で視覚化すると役立つ場合があります

この範囲の最大値は、実行時に指定されるパラメータであり、これを と呼びますmax_val。UInt32したがって、ビット フィールド変数は、次のサイズの配列として定義する必要がありますmax_val/32。

UInt32 MAX_DIV_32 = max_val / 32;
UInt32[] bitArray = new UInt32[MAX_DIV_32];

変数x1とによって定義された範囲が与えられた場合、x2この変換を実行する最速の方法は何ですか?

4

6 に答える 6

2

これを試して。すべて 1 で埋める必要がある配列項目の範囲を計算し、この範囲を反復してこれを行います。最後に、両方の境界にアイテムを設定します。

Int32 startIndex = x1 >> 5;
Int32 endIndex = x2 >> 5;

bitArray[startIndex] = UInt32.MaxValue << (x1 & 31);

for (Int32 i = startIndex + 1; i <= endIndex; i++)
{
   bitArray[i] = UInt32.MaxValue;
}

bitArray[endIndex] &= UInt32.MaxValue >> (31 - (x2 & 31));

コードが 100% 正しいとは限りませんが、アイデアは機能するはずです。

テストしたところ、3 つのバグが見つかりました。開始インデックスでの計算には mod 32 が必要であり、終了インデックスでは 32 は 31 であり、開始インデックスと終了インデックスが同じ場合を処理する代入ではなく論理 AND である必要があります。かなり速いはずです。

アレイ全体に x1 と x2 を均等に分散してベンチマークしました。Intel Core 2 Duo E8400 3.0 GHz、Windows XP ホスト上の Server 2003 R2 を搭載した MS VirtualPC。

Array length [bits]           320         160         64
Performance [executions/s]    33 million  43 million  54 million

もう 1 つの最適化 x % 32 == x & 31 ですが、パフォーマンスの向上を測定できません。私のテストでは 10.000.000 回の反復しかないため、変動は非常に大きくなります。そして、私は VirtualPC で実行しているため、状況がさらに予測不能になっています。

于 2009-03-27T03:58:23.310 に答える
2

BitArray のビット範囲全体を true または false に設定するための私の解決策:

public static BitArray SetRange(BitArray bitArray, Int32 offset, Int32 length, Boolean value)
{

    Int32[] ints = new Int32[(bitArray.Count >> 5) + 1];

    bitArray.CopyTo(ints, 0);

    var firstInt = offset >> 5;
    var lastInt = (offset + length) >> 5;

    Int32 mask = 0;

    if (value)
    {
        // set first and last int
        mask = (-1 << (offset & 31));
        if (lastInt != firstInt)
            ints[lastInt] |= ~(-1 << ((offset + length) & 31));
        else
            mask &= ~(-1 << ((offset + length) & 31));

        ints[firstInt] |= mask;

        // set all ints in between
        for (Int32 i = firstInt + 1; i < lastInt; i++)
            ints[i] = -1;
    }

    else
    {
        // set first and last int
        mask = ~(-1 << (offset & 31));
        if (lastInt != firstInt)
            ints[lastInt] &= -1 << ((offset + length) & 31);
        else
            mask |= -1 << ((offset + length) & 31);

        ints[firstInt] &= mask;

        // set all ints in between
        for (Int32 i = firstInt + 1; i < lastInt; i++)
            ints[i] = 0;

    }

    return new BitArray(ints) { Length = bitArray.Length };

}
于 2013-01-16T09:23:38.050 に答える
0

UInt32[] の代わりに System.Collections.BitArray クラスを使用しない理由はありますか? それ以外の場合は、次のようなことを試します。

int minIndex = (int)x1/32;
int maxIndex = (int)x2/32;
// first handle the all zero regions and the all one region (if any)
for (int i = 0; i < minIndex; i++) {
    bitArray[i] = 0;
}
for (int i = minIndex + 1; i < maxIndex; i++) {
    bitArray[i] = UInt32.MaxValue; // set to all 1s
}
for (int i = maxIndex + 1; i < MAX_DIV_32; i++) {
    bitArray[i] = 0;
}

// now handle the tricky parts
uint maxBits = (2u << ((int)x2 - 32 * maxIndex)) - 1; // set to 1s up to max
uint minBits = ~((1u << ((int)x1 - 32 * minIndex)) - 1); // set to 1s after min

if (minIndex == maxIndex) {
    bitArray[minIndex] = maxBits & minBits;
}
else {
    bitArray[minIndex] = minBits;
    bitArray[maxIndex] = maxBits;
}
于 2009-03-27T03:56:55.170 に答える
0

これを試して：

uint x1 = 3;
uint x2 = 9;

int cbToShift = x2 - x1; // 6
int nResult = ((1 << cbToShift) - 1) << x1; 

/*
  (1<<6)-1 gives you 63 = 111111, then you shift it on 3 bits left
*/
于 2009-03-27T04:33:19.890 に答える
0

char私は配列でそれをやってみて、ベース2Convert.ToUInt32(string, int)からaに変換するために使用するのに十分退屈でした.uint

uint Range(int l, int h)
{
  char[] buffer = new char[h];
  for (int i = 0; i < buffer.Length; i++)
  {
    buffer[i] = i < h - l ? '1' : '0';
  }
  return Convert.ToUInt32(new string(buffer), 2);
}

簡単なベンチマークは、私の方法が Angrey Jim の方法よりも約 5% 高速であることを示しています (2 番目の Pow をビットシフトに置き換えても)。

上限が大きuintすぎて 1 つのint. 少し不可解ですが、うまくいくと思います。

uint[] Range(int l, int h)
{
  char[] buffer = new char[h];
  for (int i = 0; i < buffer.Length; i++)
  {
    buffer[i] = i < h - l ? '1' : '0';
  }

  int bitsInUInt = sizeof(uint) * 8;
  int numNeededUInts = (int)Math.Ceiling((decimal)buffer.Length /
                                         (decimal)bitsInUInt);
  uint[] uints = new uint[numNeededUInts];
  for (int j = uints.Length - 1, s = buffer.Length - bitsInUInt;
       j >= 0 && s >= 0;
       j--, s -= bitsInUInt)
  {
    uints[j] = Convert.ToUInt32(new string(buffer, s, bitsInUInt), 2);
  }

  int remainder = buffer.Length % bitsInUInt;
  if (remainder > 0)
  {
    uints[0] = Convert.ToUInt32(new string(buffer, 0, remainder), 2);
  }

  return uints;
}
于 2009-03-27T04:09:08.653 に答える
0

あなたは試すことができます：

UInt32 x1 = 3;
UInt32 x2 = 9;
UInt32 newInteger = (UInt32)(Math.Pow(2, x2 + 1) - 1) & 
                   ~(UInt32)(Math.Pow(2, x1)-1);
于 2009-03-27T02:43:47.593 に答える