How can we optimizing Java BigInteger operations?

Question

Problem

Reduce the number to 1 in a minimal number of steps, following the rules:

• If the number is even, divide it by 2.
• Otherwise, increment or decrement it by 1.

Limit: s can be up to 309 digits long.

Solution

public static int solution(String s) {
    BigInteger n = new BigInteger(s);
    BigInteger one = BigInteger.ONE;
    BigInteger two = BigInteger.TWO;
    BigInteger four = new BigInteger("4");
    int count = 0;

    while (n.compareTo(one) == 1) {
        count++;

        if( n.and(one).intValue() == 0 )
            n = n.divide(two);
        else if ( n.intValue() == 3 || n.mod(four).intValue() == 1)
            n = n.subtract(one);
        else
            n = n.add(one);
    }

    return count;
}

Is there a better way to do things binary-operations-wise for this problem?

At the moment the choice I am making among these functions:

• use n.byteValue() to compare with the integer,
• or use function n.equals().

What more can we improve?

---

Follow-up question posted here

Answer 1

Division of the big integers is a very expensive operation. Even a division by 2 is linear in terms of its length: all bits must be shifted. The overall complexity is \$O(n \log{n})\$.

A natural desire is to not do arithmetics at all, but simulate it. Convert the bigint to byte array, and inspect bits, pretending that you perform arithmetics. In broad strokes, run the loop (starting with cursor = 0) until the number is exhausted:

if bit(cursor) == 0
    // simulate division
    increment counter
    advance cursor
else
    peek next_bit
    if next_bit == 0
        // simulate subtraction
        increment counter by 2
        advance cursor by 2
    else
        // simulate addition
        while next_bit == 1
            increment counter
            advance cursor
            peek next_bit
        advance cursor
        set bit at cursor to 1
        

This touches each bit just once, driving the complexity down to \$O(n)\$. Care must be taken to correctly terminate the loop.

Answer 2

Divide by 2

As implemented, the even-test and divide by two operations is very inefficient.

BigInteger provides a getLowestSetBit() function, which returns "the index of the rightmost (lowest-order) one bit"

So if n.getLowestSetBit() returns 12, you can evenly divide the value by 2 a total of twelve times, before the least significant bit is set. Instead of actually doing the division by 2 that many times, the shiftRight(int n) function should be used:

   while (n.compareTo(one) == 1) {

       int zeros = n.getLowestSetBit();
       if (zeros > 0) {
          n = n.shiftRight(zeros);
          count += zeros;
       } else {
          count++;
          if ( n.intValue() == 3 || n.mod(four).intValue() == 1)
             n = n.subtract(one);
          else
             n = n.add(one);
          }
       }

Mod-4

Using n.mod(four).intValue() == 1 to test whether the value should be incremented or decremented is also horribly inefficient. Java must actually compute the modulo-4 remainder of the entire number; expecting it to optimize n.mod(four).intValue() == 1 into the much faster n.and(three).intValue() == 1 is expecting a lot from the optimizer.

But even computing n.and(three) is too much work! We know n is larger than 1, and that bit #0 is set. If bit #1 is set, then n % 4 == 3; if bit #1 is not set, then n % 4 == 1. And BigInteger also provides the testBit(int n) function:

          if ( n.intValue() == 3 || !n.testBit(1))
             n = n.subtract(one);
          else
             n = n.add(one);
          }

Possible Bug

n.intValue() == 3

Since n can have over 300 digits, at any point in the process, the value of n can easily overflow an integer:

Consider the 33-bit value 0x100000003. The number is not 3, but the intValue() of the number is 3.

You probably want to explicitly test for value BigInteger(3). Since comparing the entire value may be slower than testing a single bit, you may want to reorder the test to check the bit first.

          if ( !n.testBit(1) || n.equals(three) )
             n = n.subtract(one);
          else
             n = n.add(one);
          }

Answer 3

You wrote:

    while (n.compareTo(one) == 1) {

As the documentation says:

This method is provided in preference to individual methods for each of the six boolean comparison operators (<, ==, >, >=, !=, <=). The suggested idiom for performing these comparisons is: (x.compareTo(y) <op> 0), where <op> is one of the six comparison operators.

So that would be:

    while (n.compareTo(one) > 0) {

I also find that much easier to understand. You just need to read the three parts n, one and > and mentally move the > between the operands, i.e., n > one.