Объяснение студента, изучающего информатику.
Как случайный программист, я часто проверяю такие сайты, как Codeforces и Kattis, чтобы отточить свою логику программирования и навыки. Однажды я наткнулся на интересную для меня проблему. Сначала эта проблема выглядела довольно сложной, поэтому я попытался ее решить (проблема будет объяснена в следующих разделах). Сначала я не мог решить ее - я не мог найти никаких закономерностей, связанных с проблемой. Я никуда не торопился, поэтому оставил задачу, потому что уже полночь.
Однажды, когда я ничего не делал в торговом центре, я вернулся к проблеме и понял, как это сделать - с помощью манипуляции с битами!
Что такое битовые маски?
Поскольку я все еще учусь, я все еще узнаю гораздо больше о компьютерных науках, поэтому пока это то, что я знаю о манипуляциях с битами.
Чтобы понять манипуляции с битами, нам нужно сначала понять битовые маски. Вы спросите, что такое битовые маски? Как вы, возможно, уже знаете, немного не хватает «двоичных цифр» - цифры, состоящей только из нулей и единиц. Целочисленная переменная обычно имеет ограничение в 32 бита, что означает, что она состоит из 32 бита с диапазоном 2 ² (2 выводятся из состояния битов - 0 или 1, что соответствует двум возможностям).
С другой стороны, битовые маски - это просто целые числа, используемые как набор логических значений. Поскольку логические значения имеют состояние только True или False, они также могут быть представлены нулями и единицами, и именно поэтому они называются битовыми масками! Итак, просто поставьте:
Битовые маски используют то, как целое число может быть представлено в его двоичной форме, что означает, что оно может использоваться как компактный набор логических значений.
Побитовые операторы.
Битовые манипуляции - это техника, которая используется для манипулирования битами, представляющими целое число. Я собираюсь показать вам некоторые часто используемые побитовые операторы в C ++.
- Сдвиг влево и вправо (‹
Сдвигает двоичную форму целого числа влево / вправо в зависимости от количества сдвигов.
Обратите внимание, что сдвиг влево эквивалентен умножению на 2, а сдвиг вправо - это деление на 2 и округление - обычно это быстрее, чем обычные операции деления.
int x=5; // 101 in binary If shifted left by 1 : x=x<<1; //10 = 2 in decimal If shifted left by 3: x=x<<3; //0 = 0 (see it as 0101) If shifted right by 1 : x=x>>1; //1010 = 10 in decimal If shifted right by 2: x=x>>2; //10100 = 20 in decimal
2. Побитовое ИЛИ (|)
Выполняет операцию ИЛИ над двоичной формой двух целых чисел.
int x=5; // 101 in binary int y=9; // 1001 in binary int z=x|y; x = 0101 y = 1001 --------- OR z = 1101 = 13 in decimal
3. Побитовое И (&)
Выполняет операцию И над двоичной формой двух целых чисел.
int x=5; // 101 in binary int y=9; // 1001 in binary int z=x&y; x = 0101 y = 1001 --------- AND z = 0001 = 1 in decimal
4. Побитовое НЕ (~)
Инвертирует биты двоичной формы целого числа.
Эта операция обычно используется вместе с другими операторами; например, для выполнения операций NAND или NOR.
5. Побитовое исключающее ИЛИ (^)
Применяет операцию XOR к двоичной форме двух целых чисел.
int x=5; // 101 in binary int y=9; // 1001 in binary int z=x^y; x = 0101 y = 1001 --------- XOR z = 1100 = 12 in decimal
Интересный факт: поменять местами 2 целых числа можно с помощью операции XOR; попробуйте сами!
int a=3; int b=5; a=a^b; // a=6, b=5 b=a^b; // a=6, b=3 a=a^b; // a=5, b=6
Помните, что это только битовые операторы, их использование будет показано в примере. Редко использовать его в чистом виде, как в примерах - мы можем сделать гораздо больше!
Проблема с использованием Bitmask!
Возвращаясь к моей истории решения этой проблемы в Kattis, вот проблема, о которой я говорил в предыдущем разделе.
Краткое изложение проблемы: бесконечное двоичное дерево, каждый узел которого состоит из дроби с числителем p и знаменателем q . Левый узел равен p / (p + q), , а правый узел равен (p + q) / q. Функция F (n) определена так, что она будет возвращать дробь из соответствующего узла. Узлы пронумерованы, как показано на иллюстрации, взятой из задачи ниже:
Первый узел начинается со значения p = 1 и q = 1. Это означает, что F (1) = 1/1, F (2) = 1/2, F (3) = 2/1 и т. Д. И т. Д. Нам необходимо ввести значение дроби и вывести N. Будет несколько тестовых примеров.
На первый взгляд, эта проблема может не иметь ничего общего с манипуляциями с битами. Но на самом деле он имеет два состояния - переход к левому или правому узлу! Прежде чем я изложу вам свою точку зрения на эту проблему, вы можете попробовать решить ее самостоятельно.
Мое понимание этой проблемы.
Проблема может предложить вам вручную использовать метод поиска в ширину (BFS) с использованием очереди. Для дроби, которая находится в малом N, это было бы жизнеспособным. Однако мы не знаем, где будет находиться введенная дробь, поскольку это бесконечное двоичное дерево.
Итак, как решить проблему? Вот моя логика:
- Лучше искать прямо из каждого теста, чем обрезать, так как это займет слишком много времени и памяти.
- Мы можем представить каждый узел в его двоичной форме!
- p всегда соответствует ‹q в левом узле, а p всегда составляет› q в правом узле.
Что вы имеете в виду, используя его двоичную форму?
Что ж, давайте возьмем первый, второй и третий узел в их двоичной форме (1, 10, 11). С помощью простого анализа мы можем сначала предположить, что в левом узле мы добавляем 0 из первого узла, а в правом узле мы добавляем 1 из первого узла.
Мы можем дополнительно проверить правильность нашего анализа, посмотрев на паттерн; и это оказывается правильным! (См. Рисунок для лучшего визуального объяснения.)
Почему это работает?
Просто - это бинарное дерево! Ну, конечно, N будет следовать образцу двоичных цифр!
Поскольку мы решаем задачу сверху вниз, нам нужно добавлять цифры (если слева 0, если справа 1) спереди. Как добиться такого результата? Мы используем оператор ИЛИ с оператором сдвига влево, чтобы включить бит в указанном месте.
Взгляните на этот псевдокод:
int result=0; int pos=2; result|=(1<<pos); //turning on the 2nd bit from the right (0-based)
Таким образом, мы можем просто поставить 1, если узел идет с правой стороны, и каждый уровень, на который мы поднимаемся, мы увеличиваем переменную pos на единицу! Мы делаем это, пока не дойдем до последнего узла (то есть p = 1 и q = 1).
Вот мое решение проблемы, написанное на C ++:
Обратите внимание: поскольку мы начинаем с индекса одного, мы добавляем еще 1 после достижения начального узла.
Это решение, поскольку мы перемещаемся по двоичному дереву, временная сложность программы составляет O (log n)!
Заключение!
Эта проблема - лишь один из примеров использования битовых манипуляций. Некоторые другие приложения также интересны для изучения, например, обратное отслеживание с использованием битовых масок, динамическое программирование с битовыми масками и другие.
Я надеюсь, что это руководство может стать хорошим началом для понимания методов работы с битами или обогатить читателей новыми знаниями.
Спасибо за чтение!
