Bitfields en C #

Question

Entonces, campos de bits. En concreto, grandes campos de bits. Entiendo cómo manipular valores individuales en un campo de bits, pero cómo voy a hacer esto en un conjunto grande, como decir:

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

El problema específico que estoy teniendo es hacer turnos de izquierda y derecha que se extienden a través de toda la matriz. Por ejemplo, si hice un > > 4 en la matriz anterior, terminaría con:

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

Ahora, un algoritmo (demasiado) simplista aquí podría parecer algo así (este soy yo escribiendo código al vuelo):

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

¿Hay algo integrado que pueda facilitar el trabajo con este tipo de datos?

Answer 1

¿Qué te hace pensar que BitArray usa bools internamente? Utiliza valores booleanos para representar los bits en términos de la API, pero bajo el capó creo que usa un int [].

Answer 2

No estoy seguro de si es la mejor manera de hacerlo, pero esto podría funcionar (restringiendo los cambios para que estén en el rango de 0 a 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: con este cambio, debería poder manejar los cambios superiores a 31 bits. Podría ser refactorizado para que se vea un poco menos feo, pero en mis pruebas, funciona y no parece tan malo en cuanto al rendimiento (a menos que, de hecho, haya algo incorporado para manejar grandes conjuntos de bits, lo que podría ser el caso).

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

    }

Answer 3

Usando métodos de extensión, podrías hacer esto:

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

Desafortunadamente, no pude encontrar una manera de sobrecargar a los operadores de turnos. (Principalmente porque BitArray está sellado).

Si pretende manipular int s o uint s, puede crear métodos de extensión para insertar bits en / extraer bits del BitArray . ( BitArray tiene un constructor que toma una matriz de int s, pero eso solo lo lleva tan lejos).

Answer 4

Esto no cubre cambios específicos, pero podría ser útil para trabajar con conjuntos grandes. Está en C, pero creo que podría adaptarse fácilmente a C #

¿Hay un límite práctico ¿Al tamaño de las máscaras de bits?