Inspired by your idea.

We don't need to check INT_MAX. The only thing we need to check is 3, which means n starts with two consecutive ones.

There are three cases:

If n is even, then divide n by 2.
If n has the tail like 11 or 111 or 1111..., then do n++.
If n has the tail like 01, then do n--.

Why n = 3 is a special case?

Because the shortest path is

3 (000...00011) -> 2 (000...00010) -> 1 (000...00001)

not

3 (000...00011) -> 4 (000...00100) -> 2 (000...00010) -> 1 (000...00001)

And for other numbers start with two consecutive 1 (such as 0x11001 or 0x11000), the leading 11 is of this special case.

class Solution {
public:
int integerReplacement(int n) {
int ans = 0;
while(n != 1){
if(n == 3) // special case: n start with two consecutive 1
return ans+2;
else if((n & 0x1) == 0) // n is odd
n = (n >> 1) & 0x7FFFFFFF;
else if((n+1) % 4 == 0) // n has tail like 0x11, 0x111, ...
n++;
else // n has tail like 0x01
n--;
ans++;
}
return ans;
}
};