Программирование: минимальные шаги, необходимые для преобразования двоичного числа в ноль

Question

Работал над упражнением по программированию и застрял в поиске правильного алгоритма.Вот проблема:

Учитывая десятичное число, сколько минимально возможных шагов требуется, чтобы преобразовать это в ноль при условии:

1. Измените бит i, если следующий битi + 1 равен '1', а остальные все биты i + 2 и более поздние равны 0
2. Изменить последний бит без ограничения

Например:
если введено значение (8) Base10 = (1000) Base2, то предпринимаются следующие шаги:

1000→1001→1011→1010→1110→1111→1101→1100→0100→0101→0111→0110→0010→0011→0001→0000

требуется всего 15 шагов.

Заполните следующее определение:

int minStepsRequired(long number)

Можно получить псевдокод или просто алгоритм.Это не домашнее задание или задание.

Answer 1

Сначала я пытался решить ее с помощью рекурсивной функции глубины (в NodeJS), но она работала только для небольших чисел - входное значение, такое как 10^5, вызывало бы ошибку времени выполнения из-за количества рекурсивных вызовов.в стеке.

Итак, я попытался увидеть, как я могу свести проблему к сумме меньших проблем, и обнаружил, что число шагов для N, будучи N степенью 2, составило

Правило № 1

N * 2 - 1

(например: число шагов для 2 - 3, для 32 - 63, для 256 - 511,и так далее).

Тогда я нашел, что делать с любым другим числом (которое не является степенью 2), и, поскольку любое целое число является суммой различных степеней 2 (отсюда и двоичное представление), мне нужно было только увидетьесли бы количество шагов также складывалось ... но это было не так.Тем не менее, я обнаружил, что мне нужно было не просто добавить число шагов от каждой степени два, но

Правило # 2

вычесть и добавить шаги поочередномода, начиная с цифры высшего порядка

Демонстрация

Дано число 42 (101010 в двоичном виде)

Давайте сначала применим Правило № 1

1 0 1 0 1 0
^ ^ ^ ^ ^ ^
| | | | | |_           0 steps
| | | | |___  2*2-1 =  3 steps
| | | |_____           0 steps
| | |_______  2*8-1 = 15 steps
| |_________           0 steps
|___________ 2*32-1 = 63 steps

И, во-вторых, применение Правило № 2 :

63 - 15 + 3 = 51

Общее количество шагов 51

Answer 2

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

Если длина двоичного представления равна 0, вы уже можете сказать ответ.Или, если длина 0 не разрешена, то если длина равна 1, вы сообщаете ответ в зависимости от того, равен ли этот бит 0 или 1.

Если длина больше 1:

• Если первый бит равен 0, ответ такой же, как и без этого 0 бита.Удалите его и вызовите рекурсивно, чтобы получить ответ.
• Если первый бит равен 1, разделите его на три подзадачи и найдите количество шагов для каждого:
  1. Создайте ситуацию, в которой вам разрешено изменятьот 1 до 0. Это означает, что за ним следует 1, а затем все 0.Напишите рекурсивный вспомогательный алгоритм для этого.Это будет очень похоже на основной алгоритм, и, вероятно, они могут разделить некоторую логику.
  2. Отразить 1 к 0 (1 шаг)
  3. Преобразовать оставшиеся биты в 0. Ещерекурсивный вызов.

Алгоритм может занять много времени.Это фактически подсчет шагов, поэтому требуется время, пропорциональное количеству шагов, которое, я думаю, примерно пропорционально вводимому числу.Ваш метод принимает аргумент long, но с моим алгоритмом для больших значений long он может не завершиться в течение срока службы компьютера, на котором он работает.Также количество шагов может превысить int и даже long (если входное значение является отрицательным long).

Счастливое кодирование.Если бы это был я, я бы на самом деле запрограммировал и запустил его, чтобы убедиться, что все правильно понял.

Быстрый путь

Следующее решение не требует рекурсии и выполняется в постоянном времени.Я не могу правильно объяснить, как это работает, что является серьезной проблемой, если мы хотим использовать это для чего-то.Я играл с некоторыми примерами, видел шаблон и обобщал его.ИМХО, в отличие от этого, прелесть рекурсивного решения, описанного выше, состоит в том, что его легко понять (если вы понимаете рекурсию).

Пример: ввод 8 или 1000 двоичный файл.Результат 15 или 1111 двоичный.Шаблон таков: каждый бит результата - это XOR предыдущего бита результата и бит в той же позиции на входе.Таким образом, из 1000 просто скопируйте передний бит 1. Следующий бит равен 1 XOR 0 = 1, где 1 - это передний бит результата, а 0 - из входа.Оставшиеся два бита рассчитываются одинаково.

Более длинный пример, чтобы вы могли проверить, поняли ли вы:

Input:  115 = 1110011
Result:       1011101 = 93

Или в коде:

static BigInteger calculateStepsRequired(long number) {
    // Take sign bit
    int bit = number < 0 ? 1 : 0;
    BigInteger result = BigInteger.valueOf(bit);
    for (int i = 0; i < 63; i++) {
        number = number << 1;
        int sign = number < 0 ? 1 : 0;
        bit = (bit + sign) % 2;
        result = result.shiftLeft(1).add(BigInteger.valueOf(bit));
    }
    return result;
}

IЯ проверил этот метод по сравнению с моей собственной реализацией первого вышеупомянутого алгоритма, используя различные входные данные до 100 000 000, и они всегда соглашаются, поэтому я считаю, что быстрый метод также является правильным.