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

Question

这是我在竞争性编程中遇到的问题之一。问题）您有一个二进制格式的输入字符串11100，您需要计算数字为零的步骤数。如果数字是odd -> subtract it by 1，如果even -> divide it by 2。例如28 -> 28/214 -> 14/27 -> 7-16 -> 6/23 -> 3-12 -> 2/21-> 1-10 -> 停止步数=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 n = '11100';
n.length + n.replace(/0/g, '').length - 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;

 result =  __builtin_popcount(n) + log2(n);