```
public int integerReplacement(int n) {
int count = 0;
int debt = 0;
while(n > 1) {
if((n & 1) == 1) debt++;
else {
if(debt > 1) {
debt = 1;
count++;
} else { // nothing happens here when debt == 0
count += debt;
debt = 0;
}
}
n = n >>> 1;
count++;
}
return count + Math.min(debt, 2);
}
```

Only look at the last bit.

If it is `0`

simply shift right.

If it is `1`

we still shift right. However, it is a debt and we need to pay for it later, there are 2 ways to pay it (-1 and +1).

`10000001`

debt is created after the first shift. it will be payed in the next iteration. the cost of paying this debt is 1.

`10001111`

we can pay all debts one by one (minus 1 operation), that will cost 4. Or we can transform the debt into `10010000`

(plus 1 operation), which cost 1. it clears the old debt, but creates a new debt.

More complex example:

`100111101111`

. There are 2 blocks of debts. Starting from the right one. We take 1 turn to convert the right debt, and it becomes, `100111110000`

. The two block of debts are merged into one. Then it got further converted into `101000000000`

.

When last digit is `0`

, we review our debts. When the cost of paying the debt is `1`

we pay for it and clear the debt. Otherwise we convert all debts into `one`

debt to be payed in the future.