java - java - 如何创建和操作长度为 1000 万位的位数组

Question

我刚遇到一个问题；用伪代码很容易解决，但是当我开始用 java 编码时；我开始意识到我不知道从哪里开始......

这是我需要做的：

1. 我需要一个大小为 1000 万（位）的位数组（我们称之为 A）。
2. 我需要能够将此数组中的元素设置为 1 或 0 (A[99000]=1)。
3. 我需要遍历这 1000 万个元素。

Answer 1

Java 中的“正确”方式是使用 Hunter McMillen 指出的已经存在的 BitSet 类。如果您正在弄清楚如何管理大型位数组纯粹是为了思考一个有趣的问题，那么计算字节数组中位的位置只是基本的模运算。

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

使用BitSet（正如 Hunter McMillen 在评论中已经指出的那样）。您可以轻松获取和设置位。要迭代只需使用正常for循环。

Answer 3

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

由于我们使用 64 个字段，我们将最大大小扩展到 137438953408 位，这大致适合 16GB 的内存。此外，我们使用掩码和位移来代替除法和模运算，以减少计算时间。改进是相当可观的。

Answer 4

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

如果你真的想要位，你可以使用 boolean 并让 true = 1 和 false = 0。

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