原题链接在这里：

题目：

Given a positive integer n and you can do operations as follow:

1. If n is even, replace n with n/2.
2. If n is odd, you can replace n with either n + 1 or n - 1.

What is the minimum number of replacements needed for n to become 1?

Example 1:

Input:8Output:3Explanation:8 -> 4 -> 2 -> 1

Example 2:

Input:7Output:4Explanation:7 -> 8 -> 4 -> 2 -> 1or7 -> 6 -> 3 -> 2 -> 1

题解：

n是偶数时除以2是确定的，问题是n是奇数时+1 还是 -1. 尽可能的消除1 bit, +1 或 -1后哪个1 bit少就选哪个.

若+1或-1后1 bit相同，那么除了3特殊情况下其他都选+1.

Time Complexity: O(1), int最多32位，最多64次操作.

Space: O(1).

AC Java:

1 public class Solution { 2     public int integerReplacement(int n) { 3         int count = 0; 4         while(n != 1){ 5             if((n & 1) == 0){ 6                 n >>>= 1; 7             }else if(n == 3 || Integer.bitCount(n+1) > Integer.bitCount(n-1)){ 8                 n--; 9             }else{10                 n++;11             }12             count++;13         }14         return count;15     }16 }

除了3特例之外，看n的倒数第二位，若是1, n++, 若是0, n--.

Time Complexity: O(1). Space: O(1).

AC Java:

1 public class Solution { 2     public int integerReplacement(int n) { 3         int count = 0; 4         while(n != 1){ 5             if((n & 1) == 0){ 6                 n >>>= 1; 7             }else if(n == 3 || ((n >>> 1) & 1) == 0){ 8                 n--; 9             }else{10                 n++;11             }12             count++;13         }14         return count;15     }16 }

Reference: s