提高字符串到二进制数转换的性能

Question

这是我在竞争性编程中遇到的问题之一。

问题）您有一个二进制格式的输入字符串11100，您需要计算数字为零的步骤数。如果数字是odd -> subtract it by 1，如果even -> divide it by 2。

例如

28 -> 28/2

14 -> 14/2

7 -> 7-1

6 -> 6/2

3 -> 3-1

2 -> 2/2

1-> 1-1

0 -> 停止

步数=7

我想出了以下解决方案

public int solution(String S) {

    // write your code in Java SE 8

    String parsableString = cleanString(S);

    int integer = Integer.parseInt(S, 2);

    return stepCounter(integer);

}

private static String cleanString(String S){

    int i = 0;

    while (i < S.length() && S.charAt(i) == '0')

        i++;

    StringBuffer sb = new StringBuffer(S);

    sb.replace(0,i,"");

    return sb.toString();

}

private static int stepCounter(int integer) {

    int counter = 0;

    while (integer > 0) {

        if (integer == 0)

            break;

        else {

            counter++;

            if (integer % 2 == 0)

                integer = integer / 2;

            else

                integer--;

        }

    }

    return counter;

}

这个问题的解决方案看起来非常简单明了，但是这段代码的性能评估给了我一个大零。我最初的印象是，将字符串转换为 int 是一个瓶颈，但未能找到更好的解决方案。有人可以向我指出这段代码的瓶颈以及可以显着改进的地方吗？

Answer 1

如果二进制数是奇数，则最后一位（最低有效位）必须是1，因此减 1 就是将最后一位数字从 1 更改为 0（重要的是，这使数字成为偶数）。如果二进制数是偶数，则最后一位必须为0，除以零只需完全删除最后一位 0 即可完成。（就像以 10 为基数一样，数字 10 可以除以 10，去掉最后的 0，留下 1。）所以步数是每 1 位数字两步，每 0 位数字一步 - 减 1，因为当你到达最后一个 0 时，你不再除以 2，你只是停止。这是一个简单的 JavaScript（而不是 Java）解决方案：let&nbsp;n&nbsp;=&nbsp;'11100'; n.length&nbsp;+&nbsp;n.replace(/0/g,&nbsp;'').length&nbsp;-&nbsp;1;只需多做一点工作，如果需要的话，这也可以正确处理前导零“0011100”。

Answer 2

需要减去的次数就是 1 位的个数Integer.bitCount()。您需要除法的次数是最高有效位的位置，即Integer.SIZE（32，整数中的总位数）减去Integer.numberOfLeadingZeros()减一（您不需要除法1）。我假设对于零输入，结果应该为零。所以我们有int numberOfOperations = integer == 0 ? 0 : Integer.bitCount(integer) +    Integer.SIZE - Integer.numberOfLeadingZeros(integer) - 1;

Answer 3

根据给定的条件，如果数字是偶数，我们将其除以 2，这相当于删除 LSB，同样，如果数字是奇数，我们将减去 1 并将其设为偶数，这相当于取消设置设置位（更改 1）至 0)。分析上述过程我们可以说，所需的总步骤数将是（位数，即（log2（n）+1））和设置位数 - 1（最后的0不需要删除）之和。C++代码：result = __builtin_popcount(n) + log2(n) + 1 - 1;&nbsp;result = &nbsp;__builtin_popcount(n) + log2(n);