Улучшить производительность преобразования строки в двоичное число

Question

Это один из вопросов, с которыми я столкнулся в конкурентном программировании.

Ques) У вас есть входная строка в двоичном формате 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 -> STOP

Количество шагов = 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

Количество раз, которое вам нужно вычесть, - это количество битов, которое равно Integer.bitCount(). Количество раз, которое вам нужно разделить, - это позиция старшего значащего бита, которая равна Integer.SIZE (32, общее количество бит в целых числах) минус Integer.numberOfLeadingZeros() минус один (выне нужно делить 1). Я предполагаю, что для нулевого ввода результат должен быть нулевым. Итак, у нас есть

int numberOfOperations = integer == 0 ? 0 : Integer.bitCount(integer) + 
  Integer.SIZE - Integer.numberOfLeadingZeros(integer) - 1;

Answer 2

Если двоичное число нечетное, последняя (наименее значимая) цифра должна быть 1, поэтому вычитание 1 просто меняет последнюю цифру с 1 на 0 (что, что важно, делает число четным).

Если двоичное число четное, последняя цифра должна быть 0, а деление на ноль может быть достигнуто простым удалением последнего 0. (Как и в базовой десятке, число 10 можно разделить на десять, убрав последние 0, оставив 1.)

Таким образом, число шагов составляет два шага для каждой 1 цифры и один шаг для каждого0 цифр - минус 1, потому что когда вы добираетесь до последних 0, вы больше не делите на 2, а просто останавливаетесь.

Вот простое решение JavaScript (вместо Java):

let n = '11100';
n.length + n.replace(/0/g, '').length - 1;

Если немного потрудиться, это может правильно справиться с ведущими нулями '0011100', если это необходимо.

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