You want to minimize the number of 1-bits every step. You only need to look at the last two bits every step.

Case 0b00 : Divide N by 2

Case 0b10 : Divide N by 2

Case 0b01 : Subtract 1, making the last two digits 0b00, reducing the number of 1s by one.

Case 0b11 : Add 1, making the last two digits 0b00, reducing the number of 1s by at least two.

N = 3 is a special case because the faster route is to subtract 1 and divide by 2. Logic above applies for all other integers.

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