General idea is how to eliminate all bits from the right.

If `n%2 == 0`

, we can use `n/2`

, since it eliminate `1`

bit per operation, eg. `10->1`

.

If `n%2 == 1`

, first choice is using `n-1`

and `n/2`

, and we use `2`

operations to eliminate `1`

bit, eg1. `11->10->1`

, eg.2 `x011->x010->x01->x00->x0`

.

Another choice is use `n+1`

and several `n/2`

to deal with continuous bits `1`

, but this may not be always better than the above one. eg.1 `11->100->10->1`

, eg.2`x011->x100->x10->x1->(x0)`

. Note `x1`

may form another continuous `1`

sequence with potential last bits of `1`

in `x`

, and it always no worse than first choice in this situation.

The truth is for longer continuous `1`

, second choice is better, and the division is that we have `3+`

`1`

s, or we have some sequence and `011`

at the last.

Here is the codes:

```
public class Solution {
public int integerReplacement(int n) {
int step = 0, count = 0;
while(n>0){
if((n&1)==0) {
step +=1;
n = n>>1;
}
else{
while((n&1)!=0){
count += 1;
n = n>>1;
}
if(count>2||n!=0&&count==2) {
step+=count+1;
n = (n|1);
}
else step += count<<1;
count = 0;
}
}
return step-2;
}
}
```

Note, since we tried to eliminate all bits, and in fact we do not need the last `2`

steps, `1->0->`

, so we return `step-2`

.

The complexity should be `olog(n)`

.