How can we optimizing Java BigInteger operations?
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.