There two cases as add one or minus one when n is odd. I found a **add one rule** that is adding one can make the next (high) bit 1 change to zero. For example, in a extreme case

11111 (+1) 100000 (/2) 10000 (/2) 1000 (/2) 100 (/2) 10 (/2) 1

6 times

11111 (-1) 11110 (/2) 1111 (-1) 1110 (/2) 111 ...

8 times

**a special case is n = 3**

11 (+1) 100 (/2) 10 (/2) 1

3 times

but

11 (-1) 10 (/2) 1

2 times

```
class Solution {
public:
int integerReplacement(int n) {
if (n == INT_MAX) { // a special case
return 32;
}
int cnt = 0;
while (n != 1) {
if (n & 1) {
// a special case
if (n == 3) { // 11 -> 10 -> 1 not 11 -> 100 -> 10 -> 1
cnt += 2;
return cnt;
}
// [1] = 1 -> +
// [1] = 0 -> -
if (0x02 & n) { // add one will change 111 -> 1000
++n;
} else {
// for example as n = 10001 just change to 10000 (minus one)
--n;
}
} else {
n >>= 1;
}
++cnt;
}
return cnt;
}
};
```