Idea:

If `n`

is even, obviously do `>> 1`

.

If `n`

is odd,

If `n+1`

has more leading zeros, do `n + 1`

. Otherwise, do `n - 1`

.

Here, the one with more leading zeros actually implies it has fewer ones and can be applied by `>> 1`

more times than `n - 1`

.

`n = 3`

is a special case and we do `n - 1`

.

```
class Solution(object):
def integerReplacement(self, n):
"""
:type n: int
:rtype: int
"""
ans = 0
while n != 1:
if n & 1 == 0:
n = n >> 1
elif n == 3 or ((n + 1) & n) > ((n - 1) & (n - 2)):
n -= 1
else:
n += 1
ans += 1
return ans
```