Этот пост является частью серии, в которой я буду разбирать проблемы кодирования, которые я решил, и делиться уроками, которые я извлек, пока нахожу ответ. Язык кодирования - JavaScript.

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

Этот вызов можно найти здесь.

Понимание проблемы

Предпосылка очень проста, поэтому я процитирую описание задачи:

«Для положительного целого числа выведите его дополнительное число. Стратегия дополнения состоит в том, чтобы перевернуть биты его двоичного представления ".

Если нам дано 5, мы должны вернуть 2. Это потому, что двоичное представление 5 равно 101. Если мы изменим каждую 1 на 0 и каждый 0 на 1, мы получим 010, которое является двоичным представлением 2.

Нам дается положительное целое число на входе и ожидается, что мы вернем положительное целое число на выходе. Давай попробуем ... сначала наивно!

Псевдокод:

Вот несколько шагов для завершения наивного решения:

  1. Преобразование заданного num в строковое представление двоичного числа
  2. Инициализируйте пустую строку: let comp = ‘’;
  3. Итерировать по длине num, которая теперь является строковой версией двоичного числа num.
  4. Во время итерации проверьте, равен ли текущий индекс num «1». Если это так, добавьте «0» к строковой переменной comp. Если это не так, добавьте «1» к строковой переменной comp.
  5. По завершении цикла верните целочисленную версию comp.

Вот наш генеральный план, давайте реализуем его с помощью кода!

Код:

Вот и все. Сложность времени приличная на O (n), где n - длина строковой двоичной версии нашего заданного input num. У нас есть постоянное пространство O (1), поскольку мы не создаем никаких массивов, хэш-карт, связанных списков и т. д. из длины нашего ввода.

Учитывая, что эта проблема по своей сути связана с двоичными числами, разве мы не можем решить ее, используя операции, специально разработанные для битов? Мы должны быть в состоянии. Давай попробуем.

Другое решение:

Поразрядные операторы позволяют нам сдвигать и манипулировать битами двоичного числа. Мы можем использовать удобные операторы, чтобы найти другое решение этой проблемы.

Позвольте мне изменить наш план игры здесь:

  1. Инициализируйте переменную, чтобы отслеживать, сколько битов у нас есть в исходном вводе (если ввод 5, то 5 === 101, тогда число бит = 3): let requiredBits;
  2. Инициализируем переменную, в которой хранится текущее значение нашего ввода (текущее значение было бы 5, если бы на входе было 5): let bits;
  3. Переберите переменную bits while bits! == 0. Увеличивайте requiredBits на 1 на каждой итерации. Используйте оператор сдвига вправо (››) , чтобы сдвинуть биты на 1 бит. Если на входе 5, то 5 === 101. Сдвиг битов вправо на 1 даст нам 010, что равно 2… 2 не равно 0, поэтому мы продолжаем сдвиг вправо на 1 бит. 010 ›› 1 === 001. Опять сдвиньте вправо. 001 ›› 1 === 000. Теперь наш цикл разорван, и наши requiredBits были увеличены на 1 три раза. Теперь requiredBits === 3.
  4. Создайте маску, которая создаст полное 32-битное двоичное представление числа, которое мы можем использовать в качестве «маски» для получения дополнения к нашему вводу.
  5. Верните XOR нашего ввода и маски.

Более детальный взгляд:

Шаг 4 на первый взгляд может сбить с толку. Что такое маска? Зачем он нужен для получения комплемента? Шаг 5 также может быть немного расплывчатым, если вы не знаете, как работает побитовый оператор XOR. Я постараюсь объяснить эти шаги в этом разделе, посвященном глубокому погружению.

Что такое маска?

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

Посмотрим на цифры. Если мы вызовем метод String.prototype.toString () на нашем входе (допустим, 5), то на выходе мы получим 101. Это нормально, но оно представляет только 3 бита из полных 32 бита, которые JavaScript использует для представления двоичных чисел (мы работаем с двоичными числами подписанными и беззнаковыми ... подробнее информацию о подписанных и беззнаковых двоичных числах в JavaScript, читайте на странице побитовых операторов Mozilla здесь).

Так как же получить недостающие 29 бит? Маска. Если мы создадим маску, которая содержит все 32 бита плюс 3 бита, которые нам нужны, представленные как единицы, то мы можем получить дополнение, используя оператор XOR на исходном входе и маске. Подробнее о побитовом операторе XOR мы поговорим позже.

Но какое число мы должны использовать для представления полного 32-битного двоичного файла, который нам нужен, чтобы получить наше дополнение? Здесь мы должны посмотреть на максимальное значение, которое мы можем представить 32-битным двоичным числом без знака.

Внимательно посмотрите на этот снимок экрана ниже:

Если вы посчитаете 1 в первом аргументе для parseInt (), вы увидите, что их 32. Второй аргумент в parseInt () - это 2, который сообщает функции преобразовать эту строку из двоичного (базового 2) строкового представления числа в целое число. Это целое число 4294967295. Это то, что мы получаем, когда все 32 бита заполняются единицами.

Итак, как мы можем использовать это, чтобы получить дополнение?

Вам может быть интересно, почему нам нужно, чтобы все 32 бита были равны 1. Давайте посмотрим, как выглядит полное 32-битное представление числа 5:

Надеюсь, это становится ясным. Здесь мы видим, что есть 29 нулей, за которыми следует то, что мы знаем как 5 в двоичном формате: 101. Итак, если мы посмотрим на эти два различных двоичных числа сверху вниз, мы увидим некоторые большие различия:

11111111111111111111111111111111 (4294967295)

00000000000000000000000000000101 (5)

У нас есть 29 символов в левой части этих двоичных чисел, которые противоположны (в двоичном выражении). 29 единиц и 29 нулей. Что произойдет, если мы применим побитовый оператор XOR к этим двум числам?

Почему мы получили -6?

Поразрядные операнды JavaScript представлены в форме «дополнения до двух». Согласно документации Mozilla:

Операнды всех побитовых операторов преобразуются в 32-битные целые числа со знаком в« дополнительном формате до двух , за исключением сдвига вправо с заполнением нулями, который приводит к 32-битному целому числу без знака. (Особо подчеркну мое, позже мы воспользуемся сдвигом вправо с нулевым заполнением)

Формат дополнения до двух означает, что отрицательный аналог числа (например, 5 против -5) - это все биты числа, инвертированные (побитовое НЕ числа или дополнение числа до единиц числа ) плюс один."

В основном наше целое число без знака было преобразовано в целое число со знаком из-за использования побитового оператора (^ XOR).

Что делает XOR?

ИСКЛЮЧАЮЩЕЕ ИЛИ (^) просматривает каждый бит, и если оба бита одинаковы, то он делает результат 0. Если биты разные, то результат равен 1. Например:

101 (5)

XOR

010 (2)

равно 111 (7). Первый шаг сравнивает 0 с 1, давая нам 1. То же самое для следующего шага, 0 против 1 дает нам 1. То же самое для последнего шага, 0 против 1 дает 1. Другой пример:

111 (7)

XOR

001 (1)

равно 110 (6). Первый шаг смотрит на 1 против 0, что дает нам 1. Второй шаг смотрит на 1 против 0, что дает нам 1. Последний шаг - 1 против 1, что дает нам 0, поскольку они одинаковы.

Я думаю о XOR как о НЕ-ИЛИ. Так что, если биты одинаковые, значит, он НЕ включен. Выходной сигнал 0. Если биты разные, он включен. Выход 1.

Вернемся в нужное русло

Итак, теперь, когда мы знаем, что делает XOR и почему мы не получаем ожидаемого результата при использовании XOR на 5 и 4294967295, мы можем перейти к следующему шагу.

Нам нужно найти способ обработать 4294967295 как целое число без знака, а также удалить все единицы в первых 29 битах, начиная с левого края, чтобы сохранить нули в левой части нашего двоичного числа. На помощь приходит оператор сдвига вправо с заполнением нулями (›››)!

Сдвигая наши биты вправо на 32 минус количество бит в нашем исходном вводе (вспомните нашу переменную requiredBits), мы можем заполнить самые левые 29 бит с нулями и оставим те, которые нам нужны, чтобы правильно использовать XOR для нашего исходного ввода и нашей маски. Давайте посмотрим, как это выглядит, когда мы используем этот оператор в терминале:

Оказывается, число 7 - это маска, которую мы будем использовать, чтобы найти дополнение к 5.

Как мы получили 7?

Мы взяли 32-битную двоичную версию 4294967295 и сдвинули ее биты вправо, заполнив пробелы нулями, пока не оказались там, где начинались биты исходного ввода. Вот так:

11111111111111111111111111111111 (4294967295)

  • сдвинуть биты вправо на 29 позиций, заполнив пробелы нулями

00000000000000000000000000000111 (7)

Если мы посмотрим на наш результат по сравнению с исходным вводом в виде двоичных чисел сверху вниз, мы увидим, почему это сработает:

00000000000000000000000000000101 (5, наш исходный ввод)

00000000000000000000000000000111 (7, маска, которую мы решили для)

Если мы используем XOR для этих двух, мы действительно сравниваем только 3 места. 1 против 1 = 0, 0 против 1 = 1 и 1 против 1 = 0. Следовательно, мы получаем:

00000000000000000000000000000010 (2, результат нашей функции)

Ого, это было много. Вот код:

Если вы заметили, что в разделе, где я определил переменную mask, я использовал (Math.pow (2, 32) -1).

Единственная причина для этого - сделать код более лаконичным. Я не хотел вводить: parseInt ('11111111111111111111111111111111', 2), чтобы достичь максимального целого числа без знака, когда я могу получить тот же ответ, используя гораздо более короткий (Math.pow (2 , 32) -1). Обе версии производят одинаковый результат: 4294967295.

Временная сложность здесь составляет O (1), если учесть тот факт, что максимальное количество запусков нашего цикла while составляет 32 раза (поскольку мы имеем дело с 32 битами в любом двоичном числе). Сложность пространства также составляет O (1), поскольку мы не создавали дополнительного пространства в зависимости от длины данного ввода.

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

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