整数的最小2的幂？

Question

在采访中有人问我以下问题：

每个数字都可以通过2的幂的加法和减法来描述29 = 2^0 + 2^2 + 2^3 + 2^4。给定一个int n，返回2 ^ i的最小加法和减法得到n。

Example 1:

Input: 15
Output: 2
Explanation: 2^4 - 2^0 = 16 - 1 = 15

Example 2:

Input: 8
Output: 1

Example 3:

Input: 0
Output: 0

下面是我得到的，但是有什么方法可以改善此问题，或者有什么更好的方法可以解决上述问题？

  public static int minPowerTwo(int n) {
    if (n == 0) {
      return 0;
    }
    if (Integer.bitCount(n) == 1) {
      return 1;
    }
    String binary = Integer.toBinaryString(n);
    StringBuilder sb = new StringBuilder();
    sb.append(binary.charAt(0));
    for (int i = 0; i < binary.length() - 1; i++) {
      sb.append('0');
    }
    int min = Integer.parseInt(sb.toString(), 2);

    sb.append('0');
    int max = Integer.parseInt(sb.toString(), 2);

    return 1 + Math.min(minPowerTwo(n - min), minPowerTwo(max - n));
  }

Answer 1

好吧...我们可以推断出，每个2的幂只能使用一次，因为否则您会以更短的方式获得相同的结果，因为2 ^x + 2 ^x = 2 ^{x + 1}，-2 ^x -2 ^x =- 2 ^{x + 1}和2 ^x -2 ^x = 0。

考虑到按顺序使用的功率，每个位都必须将相应的位从不正确的值更改为正确的值，因为再也没有机会修复该位，因为每个功率仅使用一次。

当需要加或减时，不同之处在于高位会发生什么：

000000    000000    111100    111100
 + 100     - 100     + 100    -  100
------    ------    ------    ------
000100    111100    000000    111000

一种方式是，所有高位都被翻转。相反，它们不是。

由于每个决策都可以独立确定所有较高位的状态，因此在+或-之间进行选择的结果仅与确定2的下一个幂有关。

当您必须选择+或-时，一个选项将纠正1位，而另一种选择将纠正2位或更多，这意味着需要纠正的下一位将更高。

因此，此问题具有非常简单的解决方案，无需进行动态编程或搜索或类似的操作：

1. 找到需要校正的2的最小幂。
2. 加上或减去它。选择纠正2位的选项。
3. 重复直到所有位都正确

在Java中，看起来像这样。除了查找将值更改为零所需的操作外，我将查找将值更改为零所需的操作，这是相反的符号：

int minPowersToFix(int val) {
    int result = 0;
    while(val!=0) {
        ++result;
        int firstbit = val&-val; //smallest bit that needs fixed
        int pluscase = val+firstbit;
        if ((pluscase & (firstbit<<1)) == 0) {
            val+=firstbit;
        } else {
            val-=firstbit;
        }
    }
    return result;
}