java - how to create and manipulate a bit array with length of 10 million bits

Question

I just came across a problem; it was easy to solve in pseudo code, but when I started coding it in java; I started to realize I didn't know where to start...

Here is what I need to do:

1. I need a bit array of size 10 million (bits) (let's call it A).
2. I need to be able to set the elements in this array to 1 or 0 (A[99000]=1).
3. I need to iterate through the 10 million elements.

Answer 1

The "proper" way in Java is to use the already-existing BitSet class pointed out by Hunter McMillen. If you're figuring out how a large bit-array is managed purely for the purpose of thinking through an interesting problem, then calculating the position of a bit in an array of bytes is just basic modular arithmetic.

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

}

Answer 2

Use BitSet (as Hunter McMillen already pointed out in a comment). You can easily get and set bits. To iterate just use a normal for loop.