java – hoe een bitarray met een lengte van 10 miljoen bits te maken en te manipuleren

Ik ben net een probleem tegengekomen; het was gemakkelijk op te lossen in pseudo-code, maar toen ik het in java begon te coderen; Ik begon te beseffen dat ik niet wist waar ik moest beginnen…

Dit is wat ik moet doen:

1. Ik heb een bitarray nodig met een grootte van 10 miljoen (bits) (laten we het A noemen).
2. Ik moet de elementen in deze array op 1 of 0 kunnen zetten (A[99000]=1).
3. Ik moet de 10 miljoen elementen doorlopen.

Antwoord 1, autoriteit 100%

Gebruik BitSet(als Hunter McMillen wees er al op in een opmerking). U kunt eenvoudig krijgenen stelbits in. Gebruik gewoon een normale for-lus om te herhalen.

Antwoord 2, autoriteit 93%

De “juiste” manier in Java is om de reeds bestaande BitSet-klasse te gebruiken die door Hunter McMillen is aangegeven. Als je aan het uitzoeken bent hoe een grote bit-array wordt beheerd, puur om een interessant probleem te doordenken, dan is het berekenen van de positie van een bit in een array van bytes slechts een eenvoudige modulaire rekenkunde.

public class BitArray {
    private static final int ALL_ONES = 0xFFFFFFFF;
    private static final int WORD_SIZE = 32;
    private int bits[] = null;
    public BitArray(int size) {
        bits = new int[size / WORD_SIZE + (size % WORD_SIZE == 0 ? 0 : 1)];
    }
    public boolean getBit(int pos) {
        return (bits[pos / WORD_SIZE] & (1 << (pos % WORD_SIZE))) != 0;
    }
    public void setBit(int pos, boolean b) {
        int word = bits[pos / WORD_SIZE];
        int posBit = 1 << (pos % WORD_SIZE);
        if (b) {
            word |= posBit;
        } else {
            word &= (ALL_ONES - posBit);
        }
        bits[pos / WORD_SIZE] = word;
    }
}

Antwoord 3, autoriteit 5%

Hier is een meer geoptimaliseerde implementatie van phatfingers‘BitArray’

class BitArray {
    private static final int MASK = 63;
    private final long len;
    private long bits[] = null;
    public BitArray(long size) {
        if ((((size-1)>>6) + 1) > 2147483647) {
            throw new IllegalArgumentException(
                "Field size to large, max size = 137438953408");
        }else if (size < 1) {
            throw new IllegalArgumentException(
                "Field size to small, min size = 1");
        }
        len = size;
        bits = new long[(int) (((size-1)>>6) + 1)];
    }
    public boolean getBit(long pos) {
        return (bits[(int)(pos>>6)] & (1L << (pos&MASK))) != 0;
    }
    public void setBit(long pos, boolean b) {
        if (getBit(pos) != b) { bits[(int)(pos>>6)] ^= (1L << (pos&MASK)); }
    }
    public long getLength() {
        return len;
    }
}

Omdat we velden van 64 gebruiken, breiden we de maximale grootte uit tot 137438953408-bits, wat ongeveer past in 16 GB RAM. Daarnaast gebruiken we maskers en bitverschuivingen in plaats van deel- en modulo-bewerkingen om de rekentijd te verkorten. De verbetering is behoorlijk substantieel.

Antwoord 4

byte[] A = new byte[10000000];
A[99000] = 1;
for(int i = 0; i < A.length; i++) {
    //do something
}

Als je echt bits wilt, kun je boolean gebruiken en true = 1 en false = 0.

boolean[] A = new boolean[10000000];
//etc