
Naive recursion solution, need to pay attention to overflow:
public int integerReplacement(int n) {
return op((long)n);
}private int op(long n) {
int result = 0;
while (n > 1) {
if (n % 2 == 1) {
result++;
return result + Math.min(op(n+1), op(n1));
} else {
n >>= 1;
}
result++;
}
return result;
} 
A better solution, but a little tricky. In general reducing the number of bits as much as possible in one operation is good since shifting to the right is much faster than +1 or 1. If we analyze +1 and 1 further, we can find out that:
 for consecutive 1s like 111, plus 1 can reduce more 1s
 for patterns end with 01, minus one can reduce one bit while plus one won't affect the number of bits
 Somehow this strategy doesn't seem right for n = 3 since plus one reduce 1 bit but introduce 2 shifts.
 n = Integer.MAX_VALUE will introduce overflow, we can return 32 in this case.
Solution:
public int integerReplacement(int n) {
int result = 0;
if (n == Integer.MAX_VALUE) {
return 32;
}
while (n > 1) {
if ((n & 1) == 1) {
if (n != 3 && (n & 2) == 2) {
n++;
} else {
n;
}
} else {
n >>= 1;
}
result++;
}
return result;
}