java - 获得整数的最少 2 次幂数？

Question

我在面试中被问到以下问题:

Every number can be described via the addition and subtraction of powers of 2. For example, 29 = 2^0 + 2^2 + 2^3 + 2^4. Given an int n, return minimum number of additions and subtractions of 2^i to get 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^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;
}