The optimized way is to keep the number a multiple of 4 because this will let us divide the number as many times as possible and approach 1 faster.

```
int integerReplacement(int64_t n) {
int i;
for (i = 0; n > 1; i++) {
if (n < 4)
n--;
else if (n & 1)
n = (n + 1) >> 2 << 2;
else
n >>= 1;
}
return i;
}
```