Битовая маска — это двоичное число, которое нужно для получения определенных цифр из другого двоичного числа. С помощью специальных логических операций число сравнивают с маской и получают результат — значение конкретного бита или битов, то есть цифру.
Битовые маски требуются для работы с двоичными числами, в которых хранится массив булевых значений. Булево значение — логическое, оно может быть равно 1 или 0, где 1 — это «да», а 0 — это «нет». Поэтому хранить такие значения в виде длинных двоичных чисел разумно. А чтобы получить из последовательности конкретное значение, нужна маска — двоичное число, которое «высвечивает» из массива нужный бит.
Где применяются битовые маски
Битовые строки нужны для хранения большого количества булевых значений. Одно двоичное число или булево значение занимает один бит. Если создать для него целую переменную, потратится как минимум байт, то есть восемь бит. А если хранить все в виде одного числа, в восьми битах удастся уместить восемь значений, то есть в восемь раз больше. Каждому биту будет соответствовать свое значение. Такой способ хранения позволяет оптимизировать код.
Хранение свойств объектов. Битовые маски бывают нужны при работе с объектами, у которых много свойств, в том числе тех, которые можно представить в виде булевых значений. Свойства хранятся в виде двоичных строк, маска нужна для получения значения определенного свойства.
Динамическое программирование. Это способ решения сложных задач: они декомпозируются на маленькие и решаются поэтапно. Программа формируется так, чтобы каждая маленькая подзадача решалась только один раз, а потом исполнение переходило на другую.
Обычно динамическое программирование используют для задач, связанных с графами и траекториями. Например, с помощью ДП на битовых масках можно написать решение знаменитой задачи коммивояжера — сложного задания на поиск оптимальной траектории.
Ассемблер. Язык ассемблера — это низкоуровневый язык, который переводится в машинные коды. На нем обычно пишут системные программисты, специалисты, которые работают с «железом», создают драйверы и подобное программное обеспечение. Иногда части кода на ассемблере нужны при разработке высокоуровневых программ.
На низком уровне важно сохранение каждого бита, поэтому информация хранится в виде битовых строк — выделять целый байт на одно логическое значение нерационально. Логических значений на близком к «железу» уровне много: это сигналы на входах процессора, наличие значения в том или ином регистре и так далее. Данные надо не только хранить, и получать. Поэтому маски в подобных задачах используются часто.
Работа с сетью. Например, чтобы проверить принадлежность IP-адреса к определенной сети или узнать адрес устройства, используется маска подсети. Это тоже битовая маска, а IP-адрес — строка, которая представляется в двоичном виде.
Битовые маски бывают нужны при расчете контрольных сумм и в других ситуациях, где важна экономия памяти.
Как работает битовая маска
Хранение. Например, есть три вопроса и ответы на них. Если на первый и второй вопросы ответы даны правильный, а на третий — неверно, получится список значений формата «правда, правда, ложь». Это булевы значения. В двоичном представлении их можно отобразить как 110, это число и есть битовая строка.
Плюс такого представления в том, что место для записи экономится, а последовательность значений не теряется благодаря разрядности. Если мы посмотрим на строку, то с легкостью можем ответить, на какие именно вопросы был дан правильный ответ.
Маскирование. Компьютер воспринимает информацию иначе. Ему нельзя сказать: «Посмотри на первый бит и выдай его значение» — нужно использовать маску. Например, чтобы узнать, какой ответ был дан на второй вопрос, потребуется маска 010 — единица стоит в том бите, значение которого мы хотим получить. А затем нужно применить побитовую операцию сложения — о ней мы подробнее поговорим ниже.
Побитовые операции. Работать с масками можно благодаря побитовым операциям — они попарно сравнивают конкретные биты двух чисел и применяют к ним логические операции. Первый бит одного числа сравнится с первым битом другого, второй — со вторым, и так далее. Это похоже на сложение и вычитание в столбик, когда человек работает с цифрами попарно. Только вместо сложения и вычитания — логические операции. Они возвращают 1 или 0 в зависимости от результатов сравнения.
Они могут быть следующими:
- логическое «И» — дает результат 1, если значения обоих битов равны 1, в остальных случаях 0;
- логическое «ИЛИ» — дает результат 1, если значение хотя бы одного бита равно 1;
- логическое исключающее «ИЛИ» — дает результат 1, если значения разные.
Еще есть логическое «НЕ», которое инвертирует бит, но эта операция, в отличие от предыдущих, унарная — ей нужна не пара битов для сравнения, а один бит для инверсии.
Возможные операции с битовыми масками
Перечисленные выше логические операции — основной инструмент работы с битовыми масками. Они побитово сравнивают двоичную строку с маской, выдают результат, и этот результат устанавливает, обнуляет или получает конкретное значение.
Установка значения. Происходит с помощью логического «ИЛИ». Если у нас есть строка 1000, и мы хотим установить в первый с конца бит 1, мы пишем маску 0001 и применяем операцию «строка ИЛИ маска», «1000 ИЛИ 0001». Результат побитовой операции — число 1001. Значение добавлено.
Снятие значения. Происходит с помощью исключающего «ИЛИ». Чтобы убрать последнюю единицу из полученного числа, понадобится операция «1001 исключающее ИЛИ 0001». Последняя цифра изменится на 0, потому что значение в строке и значение в маске — одинаковые.
Проверка значения. Происходит с помощью логического «И». Чтобы узнать, какой будет первая слева цифра в нашем числе, нужна маска 1000. При побитовой операции «1001 И 1000» результатом будет 1000 — это показывает, что нужный бит равен 1. А при операции «0001 И 1000» получится 0000 — это показывает, что бит равен 0.
Чтобы получить нужный бит, вместе с логическим «И» применяют побитовый сдвиг, когда разряды числа как бы «сдвигают» в сторону, пока нужный не станет первым справа. Биты считаются справа налево, поэтому в числе 1000 бит со значением 1 — четвертый. Мы назвали его первым слева для наглядности.
В каких языках можно встретить битовые маски
В целом — в любых, где есть работа с двоичными строками. Но шанс встретить такую задачу, например, во фронтенде, в разы ниже, чем в системном программировании. Чем ниже уровень, то есть чем ближе разработка к «железной» части компьютеров, тем чаще придется работать с битовыми масками. С ними могут столкнуться разработчики на ассемблере, на C/C++ или Java, на других языках, которые используются как системные.
Битовые маски — только один из многочисленных способов использования двоичных чисел. Вы можете узнать больше о побитовых операциях и о хранении информации в компьютере — для этого есть туториалы, интернет-статьи, учебники и профессиональные курсы.
0 комментариев