Campi di bit in C #

Question

Quindi, campi di bit. In particolare, grandi campi di bit. Capisco come manipolare i singoli valori in un bitfield, ma come farei per farlo su un set di grandi dimensioni, come dire:

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

Il problema specifico che sto riscontrando è fare i turni sinistro e destro che attraversano l'intero array. Ad esempio, se avessi fatto un > > 4 sull'array sopra, finirei con:

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

Ora, un algoritmo (eccessivamente) semplicistico qui potrebbe assomigliare a qualcosa (sono io a scrivere codice al volo):

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'è qualcosa incorporato che potrebbe facilitare il lavoro con questo tipo di dati?

Answer 1

Cosa ti fa pensare che BitArray usi i bool internamente? Utilizza valori booleani per rappresentare i bit in termini di API, ma credo che utilizzi un int [].

Answer 2

Non sono sicuro che sia il modo migliore per farlo, ma questo potrebbe funzionare (vincolare i turni ad essere nell'intervallo 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: con questa modifica, dovresti essere in grado di gestire turni maggiori di 31 bit. Potrebbe essere rifattorizzato per renderlo un po 'meno brutto, ma nei miei test funziona e non sembra troppo male dal punto di vista delle prestazioni (a meno che, in realtà, non ci sia qualcosa incorporato per gestire grossi bitets, che potrebbe essere il 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 i metodi di estensione, puoi farlo:

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

Sfortunatamente, non sono riuscito a trovare un modo per sovraccaricare gli operatori di turno. (Principalmente perché BitArray è sigillato.)

Se si intende manipolare int so uint , è possibile creare metodi di estensione per inserire bit / estrarre bit da BitArray . ( BitArray ha un costruttore che accetta una matrice di int , ma che ti porta solo così lontano.)

Answer 4

Questo non riguarda lo spostamento specifico, ma potrebbe essere utile per lavorare con set di grandi dimensioni. È in C, ma penso che potrebbe essere facilmente adattato a C #

Esiste un limite pratico alla dimensione delle maschere di bit?