CODEWITHSUNDEEP
java
ntin
ntin

Reputation: 177

Java manipulating large bit numbers

I have been working on the Interview Street challenge Changing Bits in my spare time for a little over a week now and just spinning my wheels at this point so I am hoping someone might be able to give me a pointer or hint in the right direction.

The basics of the challenge is taking two bit strings A & B and running a number of queries manipulating the two bit strings.

Let A and B be two N bit numbers. You are given initial values for A and B, and you should write a program which processes three kinds of queries:

Where the bit numbers are length 1 to 100,000 and the program can have between 1 to 500,000 queries of any combination of set_a, set_b, or get_c.

To minimize looping I am using C as a running total. When a bit in A or B changes, the changed bit is also added or subtracted, from C. Further minimizing looping when adding and subtracting is done from the changed bit to left hand while there is still a carry bit. 

private static void add(final boolean[] the_array, final int the_index)
{
    for(int iter = the_array.length - the_index - 1; iter >= 0; iter--)
    {
        if(the_array[iter])
        {
            the_array[iter] = false;
        }
        else if(!the_array[iter])
        {
            the_array[iter] = true;
            return ;
        }
    }
}

private static void subtract(final boolean[] the_array, final int the_index)
{
    for(int iter = the_array.length - the_index - 1; iter >= 0; iter--)
    {
        if(the_array[iter])
        {
            the_array[iter] = false;
            return ;
        }
        else if(!the_array[iter])
        {
            the_array[iter] = true;
        }
    }
}

Overall the program runs pretty well completing the worst edge case of bit length of 100,000 and 500,000 queries runs in about 120ms but it is still not fast enough for the purposes of the challenge. Due to the size of the bit length quickly exceeds the primitive integer (long as well) values in Java so most of the API is not applicable for this. As I am not making much progress increasing the overall run time magnitude is starting to suggest there might be an algorithm or data structure that is better suited for this than just an array. Any thoughts?

Upvotes: 6

Views: 945

Answers (2)

Peter Lawrey
Peter Lawrey

Reputation: 533472

I would use an long[] instead of a boolean[]. Each long has 64 bits and you can performed combined operations like

if (the_array[iter] == -1L) // all 1s
    the_array[iter] = 0L; // all zeros.

You can perform 64-bit operations in about the same time as a boolean operation, making the loop up to 64x faster.

BTW: using a boolean[] will use 8x as much memory as a long[] as each boolean uses a byte of memory in most JVMs.

Examples of where longer types are used to store data.

Depending on what operations you are performing, using int can be easier to work e.g. x = (long) a * b will overflow with long but not int.

If you are scanning lots of bits (as BitSet can do) then using long[] can be faster.

Adding a benchmark showing the difference in time it can make.

public static final int RUNS = 100;

public static void main(String... args) throws InterruptedException {
    boolean[] bools = new boolean[1024 * 1024];
    long[] longs = new long[bools.length / 64];

    for (int i = 0; i < 5; i++) {
        testBools(bools);
        testLongs(longs);
    }
}

private static void testBools(boolean[] bools) {
    long start = System.nanoTime();
    for (int t = 0; t < RUNS; t++) {
        // set all to true
        for (int i = 0; i < bools.length; i++)
            bools[i] = true;
        // search for a false;
        for (boolean b : bools)
            if (!b) throw new AssertionError();

        // set all to false
        for (int i = 0; i < bools.length; i++)
            bools[i] = false;
        // search for a true;
        for (boolean b : bools)
            if (b) throw new AssertionError();
    }
    long time = System.nanoTime() - start;
    System.out.printf("To set and scan a boolean[] with %,d bits took %,d us%n",
            bools.length, time / 2/ RUNS / 1000);
}

private static void testLongs(long[] longs) {
    long start = System.nanoTime();
    for (int t = 0; t < RUNS; t++) {
    // set all to true
    for (int i = 0; i < longs.length; i++)
        longs[i] = ~0; // all 1s
    // search for a false;
    for (long l : longs)
        if (l != ~0) throw new AssertionError();

    // set all to false
    for (int i = 0; i < longs.length; i++)
        longs[i] = 0; // all 0s

    // search for a true;
    for (long l : longs)
        if (l != 0) throw new AssertionError();
    }
    long time = System.nanoTime() - start;
    System.out.printf("To set and scan a long[] with %,d bits took %,d us%n",
            longs.length * Long.SIZE, time / 2/ RUNS / 1000);
}

prints

To set and scan a boolean[] with 1,048,576 bits took 777 us
To set and scan a long[] with 1,048,576 bits took 104 us
To set and scan a boolean[] with 1,048,576 bits took 666 us
To set and scan a long[] with 1,048,576 bits took 20 us
To set and scan a boolean[] with 1,048,576 bits took 537 us
To set and scan a long[] with 1,048,576 bits took 18 us
To set and scan a boolean[] with 1,048,576 bits took 567 us
To set and scan a long[] with 1,048,576 bits took 28 us
To set and scan a boolean[] with 1,048,576 bits took 776 us
To set and scan a long[] with 1,048,576 bits took 27 us

In this example its about 30x slower to use a boolean[] compared with a long[]

Upvotes: 2

tzaman
tzaman

Reputation: 47770

Hmm, off the top of my head:
Don't keep C around / updated, just calculate the bit you're asked for on the fly. Remember that when you add the corresponding bit positions of A and B, you only need to look down the adjacent less-significant bits until you find a point where they're both zero - anything beyond that can't carry bits past it. e.g.

A: 001101001010111
B: 010110100010110
     ^ asked for C there
   1000111^ only need to add bits from here
     ^ until you get your answer.

Upvotes: 3

Related Questions