```
public class Solution {
public int integerReplacement(int n) {
int step = 0;
while(n != 1){
if(n % 2 == 0)
n >>>= 1;
else if(n == 3){
n -= 1;
}else{
int num1 = n + 1;
int num2 = n - 1;
while(((num1 >>> 1)&1) == 0 && ((num2 >>> 1)&1) == 0){
num1 >>>= 1;
num2 >>>= 1;
}
n = ((num1 >>> 1)&1) == 0 ? n + 1 : n - 1;
}
step += 1;
}
return step;
}
}
```