7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Rick Davin Jan 11 '16 at 21:19
  • \$\begingroup\$ 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. \$\endgroup\$ – Der Kommissar Jan 11 '16 at 21:20
  • \$\begingroup\$ (int)Math.floor(index / 32f) - int arithmetic is fine - don't use index>>5, but index / Integer.SIZE \$\endgroup\$ – greybeard Jan 12 '16 at 11:54
1
\$\begingroup\$
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;
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.