Geek Answers Handbook

Java - how to create and process a 10 million-bit bit array

I ran into a problem; it was easy to solve in pseudocode, but when I started to code it in java; I began to realize that I did not know where to start ...

Here is what I need to do:

  • I need a 10 million (bit) array bit (call it A).
  • I need to be able to set elements in this array 1 or 0 (A [99000] = 1).
  • I need to iterate through 10 million elements.
+4
source share
4 answers

Use BitSet (as Hunter Macmillen noted in a comment). You can easily get and set bits. Use an ordinary for loop to iterate.

+12
source

The “right” way in Java is to use the existing BitSet class that Hunter Macmillen points to. If you figure out how a large bitmap is controlled solely for reflection on an interesting problem, then calculating the position of a bit in a byte array 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; } }
+21
source 
 byte[] A = new byte[10000000]; A[99000] = 1; for(int i = 0; i < A.length; i++) { //do something }

If you really need bits, you can use boolean and let true = 1 and false = 0.

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

Here is a more optimized implementation of BitArray 'phatfingers'

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

Since we use 64 fields, we increase the maximum size to 137438953408 bits, which roughly corresponds to 16 GB of memory. In addition, we use masks and bit shifts instead of division and modulo operations, reducing computation time. The improvement is quite substantial.

0
source

More articles:


All Articles