BitArray (compacting 32 bool values into one integer)

Question

I'm trying to refamiliarize myself with Java and working with it, so I've implemented my own version of a BitArray. Basically, it's an array of integers that maps 32 boolean values to each integer. This means an array of 32 boolean values only takes 4 bytes of space.

I was attempting to implement a Sieve of Eratosthenes and I figured I should implement a BitArray at the same time.

So, the BitArray class is as follows:

public class BitArray {
 private int[] elements;
 private int length;
 public boolean get(int index) {
 return (elements[(int)Math.floor(index / 32f)] >> (index % 32) & 0x01) == 1;
 }
 public void set(int index, boolean value) {
 int actualIndex = (int)Math.floor(index / 32f);
 int elementValue = elements[actualIndex] & ~(0x01 << (index % 32));
 if (value) {
 elementValue = elementValue | (0x01 << (index % 32));
 }
 elements[actualIndex] = elementValue;
 }
 public int getLength() {
 return length;
 }
 public BitArray(int maxSize) {
 length = maxSize;
 elements = new int[(int)Math.ceil(maxSize / 32f)];
 }
}

And to test this BitArray out, I implemented the following code:

public class Main {
 public static void main(String[] args) {
 int maxValue = 10000;
 // All the values will be initialized as false. If we mark them true, it means they are a composite number.
 BitArray bitArrayValues = new BitArray(maxValue);
 for (int i = 2; i < Math.sqrt(bitArrayValues.getLength()); i++) {
 if (!bitArrayValues.get(i)) {
 for (int j = i * i; j < bitArrayValues.getLength(); j += i) {
 bitArrayValues.set(j, true);
 }
 }
 }
 // All the values will be initialized as false. If we mark them true, it means they are a composite number.
 boolean[] boolArrayValues = new boolean[maxValue];
 for (int i = 2; i < Math.sqrt(boolArrayValues.length); i++) {
 if (!boolArrayValues[i]) {
 for (int j = i * i; j < boolArrayValues.length; j += i) {
 boolArrayValues[j] = true;
 }
 }
 }
 // Print all the numbers which are still false, which indicates the number is a prime.
 for (int i = 1; i < bitArrayValues.getLength(); i++) {
 if (!bitArrayValues.get(i)) {
 System.out.println(i + " is prime");
 }
 }
 boolean pass = true;
 for (int i = 0; i < maxValue; i++) {
 if (boolArrayValues[i] != bitArrayValues.get(i)) {
 pass = false;
 }
 }
 System.out.println("Arrays are equal? " + pass);
 System.out.println("Done.");
 }
}

I had some trouble getting back into the Java mindset for this, after having done C# and VB.NET for so long. Overall I think it was a successful adventure.

Any comments on either code block are welcome.

• Rick Davin: Just being curious: by reinventing-the-wheel are you referring to translating .NET's BitArray class into Java or reinventing Java's own BitSet class?
• Der Kommissar: I have no idea, I didn't add that tag. It should be similar to the .NET BitArray except in Java. I don't know anything about the Java BitSet class.
• greybeard: (int)Math.floor(index / 32f) - int arithmetic is fine - don't use index>>5, but index / Integer.SIZE

Answer 1

public void set(int index, boolean value) {
 int actualIndex = (int)Math.floor(index / 32f);
 int elementValue = elements[actualIndex] & ~(0x01 << (index % 32));
 if (value) {
 elementValue = elementValue | (0x01 << (index % 32));
 }
 elements[actualIndex] = elementValue;
}

You can avoid a bit of recalculation here by caching the shift value. Also, switch to long to increase the range of values the user can enter

public void set(long index, boolean value) {
 final long actualIndex = (long)Math.floor(index / 32f);
 final long mask = 0x01 << (index % 32);
 long elementValue = elements[actualIndex] & ~mask;
 if (value) {
 elementValue |= mask;
 }
 elements[actualIndex] = elementValue;
}