Observation:

**If the second bit from the least significant side of n is 1 && n>3, choose n=n+1 is a better choice.**

```
int integerReplacement(int n) {
if(n==1)
return 0;
if(n==INT_MAX)
return 32;
if(n%2==0)
return 1+integerReplacement(n/2);
else
if(n>3&&n>>1&1)
return 1+integerReplacement(n+1);
else
return 1+integerReplacement(n-1);
}
```