4

だから、ビットフィールド。具体的には、大きなビットフィールド。ビットフィールドで個々の値を操作する方法は理解していますが、次のような大規模なセットでこれを行うにはどうすればよいでしょうか。

uint[] bitfield = new uint[4] { 0x0080000, 0x00FA3020, 0x00C8000, 0x0FF00D0 };

私が抱えている特定の問題は、配列全体を通過する左右のシフトを行うことです。たとえば、>> 4上記の配列で a を実行すると、次のようになります。

uint[4] { 0x0008000, 0x000FA302, 0x000C800, 0x00FF00D };

さて、ここでの(過度に)単純化されたアルゴリズムは次のようになります(これは私がオンザフライでコードを書いているところです):

int shift = 4;
for (int i = 0; i <= shift; i++) {
    for (int j = bitfield.GetUpperBound(0); j > 0; j--) {
        bitfield[j] = bitfield[j] >> 1;
        bitfield[j] = bitfield[j] + ((bitfield[j-1] & 1) << (sizeof(uint)*8));
    }
    bitfield[0] = bitfield[0] >> 1;
}

この種のデータの操作を容易にするものは組み込まれていますか?

4

4 に答える 4

2

BitArray が内部的にブール値を使用していると思われる理由は何ですか? API に関してはブール値を使用してビットを表しますが、内部では int[] を使用していると思います。

于 2008-10-07T12:25:03.657 に答える
1

それが最善の方法かどうかはわかりませんが、これでうまくいく可能性があります(シフトを0〜31の範囲に制限します。

    public static void ShiftLeft(uint[] bitfield, int shift) {

        if(shift < 0 || shift > 31) {
            // handle error here
            return;
        }

        int len = bitfield.Length;
        int i = len - 1;
        uint prev = 0;

        while(i >= 0) {
            uint tmp        = bitfield[i];
            bitfield[i] = bitfield[i] << shift;
            if(i < len - 1) {
                bitfield[i] |= (uint)(prev & (1 >> shift) - 1 ) >> (32 - shift);
            }
            prev = tmp;

            i--;
        }

    }

    public static void ShiftRight(uint[] bitfield, int shift) {

        if(shift < 0 || shift > 31) {
            // handle error here
            return;
        }
        int len = bitfield.Length;
        int i = 0;
        uint prev = 0;

        while(i < len) {
            uint tmp        = bitfield[i];
            bitfield[i] = bitfield[i] >> shift;
            if(i > 0) {
                bitfield[i] |= (uint)(prev & (1 << shift) - 1 ) << (32 - shift);
            }
            prev = tmp;

            i++;
        }

    }

PD:この変更により、31ビットを超えるシフトを処理できるようになります。少し醜く見えないようにリファクタリングすることもできますが、私のテストでは、動作し、パフォーマンス的にはそれほど悪くはないようです(ただし、実際には大きなビットセットを処理するための何かが組み込まれている場合を除きます)。

    public static void ShiftLeft(uint[] bitfield, int shift) {

        if(shift < 0) {
            // error
            return;
        } 

        int intsShift = shift >> 5;

        if(intsShift > 0) {
            if(intsShift > bitfield.Length) {
                // error
                return;
            }

            for(int j=0;j < bitfield.Length;j++) {
                if(j > intsShift + 1) {     
                    bitfield[j] = 0;
                } else {
                    bitfield[j] = bitfield[j+intsShift];
                }
            }

            BitSetUtils.ShiftLeft(bitfield,shift - intsShift * 32);
            return;
        }

        int len = bitfield.Length;
        int i = len - 1;
        uint prev = 0;

        while(i >= 0) {
            uint tmp    = bitfield[i];
            bitfield[i] = bitfield[i] << shift;
            if(i < len - 1) {
                bitfield[i] |= (uint)(prev & (1 >> shift) - 1 ) >> (32 - shift);
            }
            prev = tmp;

            i--;
        }

    }

    public static void ShiftRight(uint[] bitfield, int shift) {

        if(shift < 0) {
            // error
            return;
        } 

        int intsShift = shift >> 5;

        if(intsShift > 0) {
            if(intsShift > bitfield.Length) {
                // error
                return;
            }

            for(int j=bitfield.Length-1;j >= 0;j--) {
                if(j >= intsShift) {        
                    bitfield[j] = bitfield[j-intsShift];
                } else {
                    bitfield[j] = 0;
                }
            }

            BitSetUtils.ShiftRight(bitfield,shift - intsShift * 32);
            return;
        }


        int len = bitfield.Length;
        int i = 0;
        uint prev = 0;

        while(i < len) {
            uint tmp    = bitfield[i];
            bitfield[i] = bitfield[i] >> shift;
            if(i > 0) {
                bitfield[i] |= (uint)(prev & (1 << shift) - 1 ) << (32 - shift);
            }
            prev = tmp;

            i++;
        }

    }
于 2008-10-07T15:32:02.767 に答える
0

拡張メソッドを使用すると、次のことができます。

public static class BitArrayExtensions
{
    public static void DownShift(this BitArray bitArray, int places)
    {
        for (var i = 0; i < bitArray.Length; i++)
        {
            bitArray[i] = i + places < bitArray.Length && bitArray[i + places];
        }
    }

    public static void UpShift(this BitArray bitArray, int places)
    {
        for (var i = bitArray.Length - 1; i >= 0; i--)
        {
            bitArray[i] = i - places >= 0 && bitArray[i - places];
        }
    }
}

残念ながら、シフト演算子をオーバーロードする方法を思いつきませんでした。(主BitArrayに封印されているためです。)

ints またはsを操作する場合はuint、 にビットを挿入/抽出するための拡張メソッドを作成できますBitArray。( s のBitArray配列を取るコンストラクターがありますがint、それはそれだけです。)

于 2008-10-07T14:09:44.757 に答える
0

これは特にシフトをカバーしていませんが、大きなセットで作業する場合に役立ちます。これは C ですが、C# にも簡単に適応できると思います。

ビットマスクのサイズに実質的な制限はありますか?

于 2008-10-07T14:23:33.263 に答える