得到一个整数所需的最少2的幂次数是多少？

Question

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

每个数字都可以通过加减2的幂来描述。例如，“29= 2^0 + 2^2 + 2^3 + 2^4”。给定一个整数n，返回得到n所需的最小2的幂次方的加减次数。

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));
  }

- john

---

哇，我想这是我第一次看到 bitCount 被使用！给定 bitCount 和最大位位置，一个替代方案是可以计算 1 和 0 的数量，从而确定是否添加或从下一个更大的 2 的幂开始并减去。例如，33 的最大位为6，bitCount 为2（即4个零），因此由于 bitCount < 零，使用加法。另一方面，30 的最大位为5，bitCount 为4（即1个零），因此由于 bitCount > 零，从32开始使用减法。（当然，我还没有看到 bitCount，因为我没有计算奇偶性） - racraman

密切相关：我们如何用最少的加减法进行乘法运算？ 在没有硬件乘法器的情况下，一个答案是对“乘数”进行重新编码。 - greybeard

我不是JAVA程序员，但Integer.parseInt(sb.toString(), 2); ??? 你在制造字符串，然后将它们解析回整数？这似乎比仅对整数进行暴力攻击要慢得多...为什么不使用x&1和x>>=1从lsb到msb检查位是否设置...记住位是否连续，然后构造+2^bit或+2^(maxbit+1) - 2^(minbit)。 - Spektre

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;
}

- Matt Timmermans

---

这可以更直接地计算为 Integer.bitCount(val ^ (3 * val))。 - Falk Hüffner

确实。这很聪明。 - Matt Timmermans

@FalkHüffner 当val太大并且溢出时，例如当val = Integer.MAX_VALUE时，这个方法就无法正常工作了。 - Eric

@FalkHüffner，不知道你是怎么做到的，但这太美妙了。 - Eugene

我在这里找到了这个公式：https://oeis.org/A007302，署名为Ramasamy Chandramouli。 - Falk Hüffner

Answer 2

这里有一个Java编写的测试用例，用于检查解决方案是否正确。

(它是为我的解决方案编写的，但在某些情况下被证明不正确，因此我删除了该答案，但测试用例仍然相关。)

Matt Timmermans的答案通过了所有测试用例，包括负数。

而Integer.bitCount(val ^ (3 * val))通过了大多数测试用例，除了输入为Integer.MAX_VALUE的情况。

---

代码

MinCountOf2PowerTest.java

import org.testng.Assert;
import org.testng.annotations.Test;

public class MinCountOf2PowerTest {
    @Test
    public void testPositive() {
        // no flip,
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("01010001", 2)), 3);

        // flip,
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("011", 2)), 2);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("0111", 2)), 2);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("01111", 2)), 2);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.MAX_VALUE), 2);

        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("01101", 2)), 3);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("011011", 2)), 3);

        // flip, there are multiple flippable location,
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("0100000111", 2)), 3);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("010010000000111", 2)), 4);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("0100100000001111111", 2)), 4);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("010011000000001111111", 2)), 5);
    }

    @Test
    public void testZero() {
        Assert.assertEquals(MinCountOf2Power.minCount(0), 0);
    }

    @Test
    public void testNegative() {
        Assert.assertEquals(MinCountOf2Power.minCount(-1), 1);
        Assert.assertEquals(MinCountOf2Power.minCount(-9), 2);
        Assert.assertEquals(MinCountOf2Power.minCount(-100), 3);
    }

    // a positive number has the same result as its negative number,
    @Test
    public void testPositiveVsNegative() {
        for (int i = 1; i <= 1000; i++) {
            Assert.assertEquals(MinCountOf2Power.minCount(i), MinCountOf2Power.minCount(-i));
        }
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.MAX_VALUE), MinCountOf2Power.minCount(-Integer.MAX_VALUE));
    }

    // corner case - ending 0,
    @Test
    public void testCornerEnding0() {
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("01110", 2)), 2);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("011110", 2)), 2);

        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("011100", 2)), 2);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("0111000", 2)), 2);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("01110000", 2)), 2);
    }

    // input from OP's question, refer: https://dev59.com/C7bna4cB1Zd3GeqPVyGX
    @Test
    public void testOpInput() {
        Assert.assertEquals(MinCountOf2Power.minCount(15), 2);
        Assert.assertEquals(MinCountOf2Power.minCount(8), 1);
        Assert.assertEquals(MinCountOf2Power.minCount(0), 0);
    }
}

提示：

• 这是用Java编写的，使用了TestNG。
  • 但是，只需替换导入语句，您也可以使用JUnit。
  • 或者通过具有特定语法的输入/输出值对将其翻译为其他语言。
• 我还发现正整数总是与其负数具有相同的结果。
  并且还包括一个测试用例来证明这一点。

- Eric

Answer 3

我猜

例如，29 = 2^0 + 2^2 + 2^3 + 2^4

在这个问题的背景下，这不是一个正确的例子。据我所知，我应该能够像这样做

29 = 2^5 - 2^2 + 2^0

好的，基本上这是一个数学问题。如果数学不是你的强项，就像我一样，那么我建议你首先考虑对数，每当你看到指数时。有时它非常有用，就像在这种情况下一样，因为它将这个问题简化为一种具有动态分母和减法允许的“硬币找零”问题。

1. 首先，我需要找到最接近目标的最大的n。 让我们在2^n = 29中找到确切的n值，这基本上是log(2^n) = log 29，即n log 2 = log 29，因此n = log 29 / log 2。这恰好是4.857980995127573，现在我知道我将从5开始。
2. 2^5是一个超出范围的值。现在我需要达到32-29 = 3，而且由于32>29，结果将减去2^2。
3. 现在我们有2^5 - 2^2，即28，小于29。现在我们需要添加下一个结果，我们的目标是1。

好的，这里是JS中的一个简单递归代码。我还没有完全测试，但似乎应用了正确的逻辑。

function pot(t, pr = 0){                        // target and previous result
  var d  = Math.abs(t - pr),                    // difference
      n  = Math.round(Math.log(d)/Math.log(2)), // the n figure
      cr = t > pr ? pr + 2**n                   // current result
                  : pr - 2**n;
  return t > cr ? `2^${n} + ` + pot(t, cr)      // compose the string result
                : t < cr ? `2^${n} - ` + pot(t, cr)
                         : `2^${n}`;
}

console.log(pot(29));
console.log(pot(1453));
console.log(pot(8565368));

- Redu

Answer 4

我编写了这个算法来解决这个问题。

给定一个正整数N：

1. 找到最高的2的幂A和最低的2的幂B，使得A ≤ N ≤ B且A≠B。换句话说，找出N属于哪个连续2的幂的区间；
2. 找出N是更接近A还是B，例如通过将N与A和B之间的中值进行比较（它们的平均值，由于B=2×A，平均值为3×A/2或1.5×A）
3. 如果N更接近下限（A）而不是N = A + δ：在解释消息中添加“减去B”；
4. 如果N更接近上限（B）而不是N = B - δ：在解释消息中添加“加上A”；
5. 用δ替换N并重复

迭代次数减1就是你要寻找的解。

为了解决步骤1，我编写了这个支持方法，它返回最接近输入的2的幂，即A（我们可以得到B，因为它只是A的两倍）。

public int getClosestLowerboundPowerof2 (int n)
{
    int i = 1;
    while (i<=n/2){
        i*=2;
    }
    return i;
}

剩下的在这里完成：

int operations;
String explanation = "";
if (input>0){
    operations = -1;
    int n = input, a;
    while (n >= 1) {
        operations++;
        a = getClosestLowerboundPowerof2(n);
        if (n > a*1.5) {
            explanation += " - "+ a * 2;
            n = a * 2 - n;
        } else {
            explanation += " + " + a;
            n -= a;
        }
    }
    System.out.println(input + " = " + explanation.substring(3,explanation.length()) + ", that " + ((operations==1)?"is":"are") + " "+ operations + " operation" + ((operations==1)?"":"s"));
}
else{
    System.out.println("Input must be positive");
}

例如，当input = 403时，它将打印：

403 = 512 - 128 + 16 + 2 + 1, that are 4 operations

希望我有所帮助!

---

NOTE: I first misinterpreted the question so I put effort in writing a detailed answer to the wrong problem... I'm keeping here the original answer because it may be interesting for somebody.

The problem is actually a mathematical argument: how to convert a number from base 10 to base 2, and they just asked you to implement an algorithm for that.

Here some theory about this concept and here a method for reference.

Programmatically I'm interpreting the problem as "Given an integer print a string of its representation in base 2". For instance given 100 print 2^6 + 2^5 + 2^2. As the linked wiki on radixes explains, that there is no need for subtractions, so there will only be additions.

The shortest way to do is to start from n, halve it at each iteration (i), and write 2^i only if this number (m) is odd. This is tested with modulo operator (% in java). So the method will be just this:

public String from10to2(int n){
  String str = "";
  for (int m = n, i=0; m>=1; m/=2, i++){
      str = ((m%2==1)?"+ 2^"+i+" ":"")+str; //"adds '+ 2^i' on top of the string when m is odd, keep str the same otherwise
  }
  return str.substring(2,str.length()); //debug to remove " + " at the start of the string
}

The content of the for may look inintuitive because I put effort to make the code as short as possible.

With little effort my method can be generalized to convert a number in base 10 to any base:

public String baseConverter(int targetBase, int decimalNumber){
  String str = "";
  for (int m = decimalNumber, i=0; m>=1; m/=targetBase, i++){
      str = ((m%targetBase==1)?"+ "+targetBase+"^"+i+" ":"")+str; //"adds '+ x^i' on top of the string when m is odd, keep str the same

otherwise } return str.substring(2,str.length()); //debug to remove " + " at the start of the string }

PS: I didn't use StringBuilder because it's not conceived to append a string on the start. The use of the String concatenation as I did is argument of debate (someone approve it, other don't).

- Sterconium

Answer 5

对于示例中提出的情况，这似乎很容易解决。

0111...1

你可以用两个幂来替换这个模式中的任何一个；例如：7 = 8 - 1 或 15 = 16 - 1 等等。

你还可以推断出，如果连续的 1 少于 3 个，那么你不会得到太多好处，例如：

0110 (4 + 2)
0110 (8 - 2)

但同时，通过执行该操作，您不会失去任何东西；相反，在某些情况下，这甚至是有益的：

0110110 - // 54, this has 4 powers

我们可以取出 "last" 的值 0110 ，并用 1000 - 0010（即 8-2）替换它：

0111000 - 000010 (56 - 2)

但现在我们可以用两个幂代替0111： 1000 - 0001。

因此，可以制作一个如此简单的“替换”算法：

static int count(int x) {
    String s = new StringBuffer(Integer.toBinaryString(x)).reverse().toString() + "0";

    Pattern p = Pattern.compile("1+10");
    Matcher m = p.matcher(s);

    int count = 0;
    while (m.find()) {
        ++count;
        s = m.replaceFirst("1");
        m = p.matcher(s);
    }

    return Integer.bitCount(Integer.parseInt(s, 2)) + count;
} 

- Eugene