数据结构 - C# 中的位域

本文关键字:位域 数据结构 | 更新日期: 2023-09-27 17:47:21

所以,位域。具体来说,大位域。我了解如何在位域中操作单个值,但是我将如何在大型集合上执行此操作,例如:

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

我遇到的具体问题是在整个阵列中进行左右移位。因此,例如,如果我对上面的数组进行>> 4,我最终会得到:

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;
}

是否有任何内置的东西可以简化处理此类数据?

数据结构 - C# 中的位域

是什么让你认为BitArray在内部使用布尔值?它使用布尔值来表示 API 方面的位,但在幕后我相信它使用 int[]。

我不确定这是否是最好的方法,但这可能会起作用(将班次限制在 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++;
        }
    }

使用扩展方法,您可以执行以下操作:

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是密封的。

如果您打算操作 int s 或 uint s,您可以创建扩展方法,用于将位插入/从BitArray中提取位。(BitArray有一个构造函数,它接受一个int数组,但这只能带你走那么远。

这并不涉及专门的移位,但对于处理大型集合可能很有用。它是 C 语言,但我认为它可以很容易地适应 C#

位掩码的大小是否有实际限制?