```
public class Solution {
private int min;
public int integerReplacement(int n) {
this.min = Integer.MAX_VALUE;
integerReplacement(n, 0);
return min;
}
private void integerReplacement(int n, int step) {
if (step >= min)
return;
if (n == 1) {
min = Math.min(min, step);
return;
}
if ((n & 1) == 0) {
// even
integerReplacement(n >>> 1, step + 1);
} else {
// odd
integerReplacement(n + 1, step + 1);
integerReplacement(n - 1, step + 1);
}
}
}
```