Сегодня поговорим о побитовых операциях. Думаю, большинство программистов так или иначе сталкивались с побитовыми операциями, или обязательно столкнутся с ними в будущем. Но далеко не все из нас разобрались с ними. И если раньше программирование начиналось чуть ли не со знакомства с побитовыми операциями, то на сегодняший день это далеко не так. Давайте попробуем разобраться, что это за зверь — побитовые операции и с чем его едят, так как в программировании без них никуда. И для начала рассмотрим, где же эти побитовые операции нам могут пригодиться.
Где применяются?
Побитовые операции широко применяются при работе с битовыми полями (флагами) и битовыми масками. Битовые поля позволяют максимально эффективно хранить некоторые состояния, имеющие только два значения: «включен» и «выключен». Access Control List (ACL) — хороший пример битового поля, использующийся для управления доступом к объекту. Например, в Linux и Mac OS каждый файл в системе имеет свой ACL, определяющий полномочия пользователя по чтению, записи или запуску файла. Битовые поля позволяют хранить несколько значений, не расходуя лишнюю память (по одному биту на каждое значение, вместо 4-х или 8-ми). А битовые маски (и побитовые операции), в свою очередь, используются для извлечения необходимых данных из битовых полей.
Довольно трудно обойтись без побитовых операций при реализации сетевой коммуникации. Побитовые операции здесь используются для проверки чек-сумм, определения битов окончания операции, для объеденения команд и данных, сериализации и т.д. и т.п.
Не получится не использовать побитовые операции и при реализации алгоритмов компресии и шифрования. Если взглянуть на любой алгоритм сжатия (например Deflate) или шифрования (например, AES), то мы увидим, что в описании довольно часто всплывают именно биты.
Однозначно существуют области программирования, в которых без побитовых операций просто невозможно обойтись. Сюда можно отнести программирование микроконтроллеров, взаимодействие с реальными устройствами, написание драйверов для них. Также сюда относится реализация программ, эмулирующих реальные устройства, такие,как эмуляторы CD-ROM, игровых приставок или виртуальных компьютеров.
Побитовые операции являются частым гостем в случаях, когда требуется использовать разного рода оптимизации и микрооптимизации кода. Банальный пример: 2 << 4 в большинстве случаев быстрее. чем Math.Pow(2, 5).
Само собой, на этом список не заканчивается, и его можно продолжить, но целью этой статьи не является описание всех возможных сфер применения побитовых операций.
Если вам кажется, что вы не столкнетесь с побитовыми операциями в повседневной работе, т.к. ваша сфера работы не входит в вышеописанные, то у нас для вас «плохие» новости. Встретиться с битовыми операциями можно где угодно, даже там, где, казалось бы, их быть вообще не должно. Но не стоит раньше времени паниковать. Не так страшен черт, как его малюют. Побитовые операции сами по себе довольно просты. И сейчас мы с ними разберемся, а заодно и закроем небольшую брешь в образовании.
Как работают побитовые операции?
Чтобы понять, как работают побитовые логические операции, нужно знать, что каждая операция работает с битами числа. И, в зависимости от типа битовой операции, действие проиходит над парой битов (в случае бинарной битовой операции) или над одним битом (в случае унарной битовой операции). И уже из результирующих битов составляется итоговое значение — результат битовой операции. Таким образом, побитовая логическая операция — это логическая операция, действие (в данном случае логическая операция, такая как конъюнкция, дизъюнкция или инверсия) которой применяется к каждому биту двоичного предстваления операнда.
Начнем, пожалуй, с самой простой побитовой операции — побитовое отрицание (NOT) или побитовая инверсия. В C подобных языках программирования этой операции соответствует символ ~ . Пример:
|
1 2 3 |
c = 5 = 101b ~c = ~5 = ~101b = 010b = 2 |
Мы инвертировали каждый бит числа, т.е. если бит был включен (1), то результатом инверсии будет выключенный бит (0). Стоит отметить, что эта операция является обратимой, т.е. ~(~c) = c .
Следующая логическая побитовая операция — побитовое И (AND). Это бинарная побитовая операция, которая работает с двумя наборами битов одинаковой длины. Если один из наборов бит содержит меньше бит, чем другой, то он дополняется незначащими нулями слева. В C подобных языках программирования этой операции соответствует символ & . Как видно из названия, в качестве логической операции используется конъюнкция. Другими словами, результатом побитовой операции И с двумя битами будет 1, тогда и только тогда, когда оба оперенда (оба бита) выставлены в 1; во всех остальных случаях результатом будет 0. Легко запомнить: если первый бит равен 1 И второй бит равен 1, то результатом будет 1, иначе 0. Рассмотрим пример:
|
1 2 3 4 5 6 7 |
c = 16; d = 6; c & d = 16 & 6 = 1101b & 110b = 1101b & 0110b = 0100b = 4 |
Побитовое ИЛИ (OR) — это также бинарная логическая операция, требующая двух одинаковых по длине наборов бит. В С-подобных языках программирования для этой операции используется символ | . По своей сути, эта операция эквивалентна применению логической операции дизъюнкции к каждой паре бит бинарного представления операндов. Результатом побитовой операции ИЛИ с двумя битами будет 1, если хотя бы один из битов выставлен (равен 1), иначе будет 0. Пример:
|
1 2 3 4 5 6 7 |
a = 5; b = 11; a | b = 5 | 11 = 101b | 1011b = 0101b | 1011b = 1111b = 15 |
Последняя побитовая логическая операция — исключающее ИЛИ (XOR). Это побитовая логическая операция, также требующая два набора бит одинаковой длины, результатом которой будет 0 в случае, если оба бита равны между собой (т.е. оба выставлены или оба не выставлены), а в противном случае будет 1. В C- подобных языках для этой операции используется символ ^ . Стоит отметить, что эта операция является обратимой, т.е. (a ^ b) ^ b = a . И пример:
|
1 2 3 4 5 |
a = 5; b = 3; a ^ b = 5 ^ 3 = 101b ^ 011b = 110b = 6 |
Эту операцию также называют сложение по модулю 2. Довольно часто эта операция применяется в компьютерной графике при отрисовке спрайтов поверх некоторого фона или других спрайтов. Повторное применение этой операции приводит к стиранию ранее нарисованного спрайта. Довольно широкое применение эта операция получила в криптографии. Ну и, пожалуй, самый распространненый пример ее использования: обмен значений двух переменных без использования дополнительной памяти.
Теперь самое время перейти к последней паре побитовых операций. Это операции побитового сдвига.
Побитовый сдвиг влево — это бинарная побитовая операция, результатом которой является сдвиг всех битов влево (от младшего бита к старшему) на заданное число (второй операнд). В C-подобных языках для обозначения данной операции используют символ << . По своей сути, эта операция эквивалента умножению на 2k при сдвиге на k бит. Пример:
|
1 2 3 4 5 6 7 8 9 10 11 |
// ** здесь операция возведения в степень 1 << 1 = 00001b << 1 = 00010b = 2 = 2 ** 1 1 << 2 = 00001b << 2 = 00100b = 4 = 2 ** 2 1 << 3 = 00001b << 3 = 01000b = 8 = 2 ** 3 1 << 4 = 00001b << 4 = 10000b = 16 = 2 ** 4 ... 1 << n = 2**n |
Побитовый сдвиг вправо — это бинарная побитовая операция, результатом которой является сдвиг всех битов вправо (от старшего бита к младшему) на заданное число (второй операнд). В C-подобных языках для обозначения данной операции используют символ >> . Эквивалентом данной операции является целочисленное деление на 2k при сдвиге на k бит. Пример:
|
1 2 3 4 5 6 7 8 |
4 >> 1 = 00100b >> 1 = 00010b = 2 6 >> 1 = 00110b >> 1 = 00011b = 3 5 >> 1 = 00101b >> 1 = 00010b = 2 16 >> 4 = 10000b >> 4 = 00001b = 1 |
Вот мы и рассмотрели основные побитовые операции. Как видите, ничего особо сложного в них нет. Давайте рассмотрим несколько примеров, как можно использовать побитовые операции в повседневной жизни.
Примеры использования побитовых операций
Пожалуй, наиболее ярким примером использования побитовых операций является использование битовых полей и масок для использования битов в качестве значений, имеющих два состояния (включен или выключен) вместо каких-то символов, чисел или отдельных Boolean значений. Для этого попробуем реализовать систему прав доступа к файлам, подобную Unix-образным ОС. Первое, что нам потребуется, — это определить перечисляемый тип с флагами доступа на чтение, запись или запуск. Рассмотрим пример на языке C#:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
namespace FileSystemTest { using System; [Flags] public enum FileAccess { None = 0 << 0, // 0b000000000 OthersExecute = 1 << 0, // 0b000000001 OthersWrite = 1 << 1, // 0b000000010 OthersRead = 1 << 2, // 0b000000100 GroupExecute = 1 << 3, // 0b000001000 GroupWrite = 1 << 4, // 0b000010000 GroupRead = 1 << 5, // 0b000100000 UserExecute = 1 << 6, // 0b001000000 UserWrite = 1 << 7, // 0b010000000 UserRead = 1 << 8 // 0b100000000 } } |
Как видно из кода выше, каждый флаг использует ровно один бит, благодаря чему мы можем скомбинировать права на доступ к файлу используя побитовую операцию ИЛИ. Теперь давайте создадим класс,отвечающий за файл в нашей виртуальной файловой системе:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
namespace FileSystemTest { using System; public class File { private readonly string _path; private FileAccess _permissions = FileAccess.None; public File(string path) { _path = path; } public FileAccess permissions { get => _permissions; set => _permissions = value; } public override string ToString() { return $"File({_path}) permissions: {_permissions}: {Convert.ToString((int) _permissions, 2)}"; } } } |
Теперь мы можем «создать» файл и назначить ему некоторые права:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
using System; namespace FileSystemTest { class Program { static void Main(string[] args) { var myFile = new File("myFile.txt"); myFile.permissions = FileAccess.UserRead | FileAccess.UserWrite | FileAccess.UserExecute; Console.WriteLine(myFile.ToString()); // File(myFile.txt) permissions: UserExecute, UserWrite, UserRead: 111000000 } } } |
Благодаря тому, что мы пометили перечисляемый тип аттрибутом Flags, C# понимает, что работает с битовым полем и в консоль выводит распарсенное значение, что очень удобно. Как же нам теперь извлечь необходимые данные из поля permissions? Элементарно, и в этом нам, опять-таки, пригодятся побитовые операции. Давайте напишем функцию, которая проверяет, выставлен ли заданный бит.
|
1 2 3 4 5 6 7 8 9 10 11 |
public class File { // ... private bool IsPermissionBitSet(FileAccess mask) { return (_permissions & mask) == mask; } // ... } |
С помощью побитовой операции И мы проверяем, установлен ли соответствующий бит маски. И результат этой операции сравниваем с заданной маской. Если необходимый бит установлен, то в результате мы получим значение, равное значению маски. Рассмотрим этот момент чуть подробнее:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
permissions = FileAccess.UserRead | FileAccess.UserWrite | FileAccess.UserExecute = 111000000b; userWrite = 1 << 7 = 010000000b; groupRead = 1 << 5 = 000100000b; 1) permissions & userWrite = 111000000b & 010000000b = 010000000b 2) 010000000b == 010000000b = true 3) permissions & groupRead = 111000000b & 000100000b = 000000000b 4) 000100000b == 000000000b = false |
Таким образом, благодаря вышеописанной фукнции мы можем легко проверять соответствующие флаги. Вот так это будет выглядеть в коде:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
public class File { // ... public bool canUserRead => IsPermissionBitSet(FileAccess.UserRead); public bool canUserWrite => IsPermissionBitSet(FileAccess.UserWrite); public bool canUserExecute => IsPermissionBitSet(FileAccess.UserExecute); public bool canGroupRead => IsPermissionBitSet(FileAccess.GroupRead); public bool canGroupWrite => IsPermissionBitSet(FileAccess.GroupWrite); public bool canGroupExecute => IsPermissionBitSet(FileAccess.GroupExecute); public bool canOthersRead => IsPermissionBitSet(FileAccess.UserRead); public bool canOthersWrite => IsPermissionBitSet(FileAccess.OthersWrite); public bool canOthersExecute => IsPermissionBitSet(FileAccess.OthersExecute); public string PermissionsToString() { return $"canUserRead: {canUserRead}, " + $"canUserWrite: {canUserWrite}, " + $"canUserExecute: {canUserExecute}, " + $"canGroupRead: {canGroupRead}, " + $"canGroupWrite: {canGroupWrite}, " + $"canGroupExecute: {canGroupExecute}, " + $"canOthersRead: {canOthersRead}, " + $"canOthersWrite: {canOthersWrite}, " + $"canOthersExecute: {canOthersExecute}"; } // ... } |
Пробуем:
|
1 2 3 4 5 |
static void Main(string[] args) { // ... Console.WriteLine(myFile.PermissionsToString()); // canUserRead: True, canUserWrite: True, canUserExecute: True, canGroupRead: False, canGroupWrite: False, canGroupExecute: False, canOthersRead: True, canOthersWrite: False, canOthersExecute: False } |
Как видите. все работает.
Стоит так же отметить, что довольно часто в других статьях (коде) можно встретить реализацию проверки выставленности бита в таком виде:
|
1 |
return (flags & mask) != 0; |
Этот код работает аналогично коду выше, в случае, если значение mask состоит только из одного бита. А вот если оно представляет из себя составное значение, то этот код вернет true , если хотя бы один из битов маски в проверяемом значении выставлен. В этом и есть основное отличии этого кода от кода выше, который вернет true , только если все биты маски выставлены в проверяемом значении. Пример:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
permissions = 111000000b mask = UserWrite | GroupWrite | OthersWrite = 010010010b 1) permissions & mask == mask = 111000000b & 010010010b == 010010010b = 010000000b == 010010010b = false 2) permissions & mask != 0 111000000b & 010010010b != 0 = 010000000b != 0 = true |
Этот момент стоит учитывать.
А как же нам теперь изменить какое-то из разрешений? Ведь пока что мы только задавали разрешения скопом. Получается, самое время рассмотреть эту возможность. Здесь нам, опять-таки, помогут побитовые операции. Давайте напишем функцию, которая будет выставлять значение необходимого бита в необходимое значение:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class File { // ... private void SetPermissionBit(FileAccess mask, bool value) { if (value) { _permissions = _permissions | mask; } else { _permissions = _permissions & (~mask); } } } |
Добавим соответствующие сеттеры:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
public class File { // ... public bool canUserRead { get => IsPermissionBitSet(FileAccess.UserRead); set => SetPermissionBit(FileAccess.UserRead, value); } public bool canUserWrite { get => IsPermissionBitSet(FileAccess.UserWrite); set => SetPermissionBit(FileAccess.UserWrite, value); } public bool canUserExecute { get => IsPermissionBitSet(FileAccess.UserExecute); set => SetPermissionBit(FileAccess.UserExecute, value); } public bool canGroupRead { get => IsPermissionBitSet(FileAccess.GroupRead); set => SetPermissionBit(FileAccess.GroupRead, value); } public bool canGroupWrite { get => IsPermissionBitSet(FileAccess.GroupWrite); set => SetPermissionBit(FileAccess.GroupWrite, value); } public bool canGroupExecute { get => IsPermissionBitSet(FileAccess.GroupExecute); set => SetPermissionBit(FileAccess.GroupExecute, value); } public bool canOthersRead { get => IsPermissionBitSet(FileAccess.UserRead); set => SetPermissionBit(FileAccess.UserRead, value); } public bool canOthersWrite { get => IsPermissionBitSet(FileAccess.OthersWrite); set => SetPermissionBit(FileAccess.OthersWrite, value); } public bool canOthersExecute { get => IsPermissionBitSet(FileAccess.OthersExecute); set => SetPermissionBit(FileAccess.OthersExecute, value); } // ... } |
И пробуем новую функцию в деле:
|
1 2 3 4 5 6 7 8 |
static void Main(string[] args) { // ... myFile.canGroupWrite = true; myFile.canUserWrite = false; Console.WriteLine(myFile.PermissionsToString()); // canUserRead: True, canUserWrite: False, canUserExecute: True, canGroupRead: False, canGroupWrite: True, canGroupExecute: False, canOthersRead: True, canOthersWrite: False, canOthersExecute: False } |
Рассмотрим реализацию функции SetPermissionBit чуть подробнее.
В случае, если мы хотим выставить некоторый бит, нам достаточно операции побитового ИЛИ и, вне зависимости от текущего состояния бита, после нее соответствующий бит будет выставлен. Несколько сложнее обстоит дело, если нам необходимо выключить соответствующий бит. Для этого мы сначала инвертируем маску, применяя операцию побитового отрицания. После чего все невыставленные биты маски будут включены, а все выставленные биты (в данном случаи один бит) — выключены. И далее применяем побитовую операцию И с инвертированной маской. Тем самым мы не модифицируем ни один из выставленных битов; а также возвращаем в качестве целевого бита 0. Что, собственно, нам и требовалось. То же самое, но по действиям:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
permissions = FileAccess.UserRead | FileAccess.UserWrite | FileAccess.UserExecute = 111000000b; userWrite = 1 << 7 = 010000000b; groupWrite = 1 << 4 = 000010000b; // myFile.canGroupWrite = true; 1) permissions | groupWrite = 111000000b | 000010000b = 111010000b // myFile.canUserWrite = false; 2) permissions & (~userWrite) = 111010000b & ~010000000b = 111010000b & 101111111b = 101010000b |
Таким образом, к текущему моменту мы рассмотрели основные моменты работы с битовыми полями.
Довольно часто побитовые операции позволяют оптимизировать код. Давайте рассмотрим такой пример. Предположим, у нас стоит задача написать функцию bool IsPowerOfTwo(int x) , определяющую, является ли переданное число степенью двойки. Простым решением, которое приходит первым в голову, является следующий алгоритм: делим число x на 2 до тех пор, пока результат деления — четное число. И если мы закончим цикл с числом, равным 1, то x является степенью двойки, иначе нет. Отдельно стоит учесть, если x равно 0:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
static void Main(string[] args) { Console.WriteLine(isPowerOfTwo(0)); // False Console.WriteLine(isPowerOfTwo(1)); // True Console.WriteLine(isPowerOfTwo(2)); // True Console.WriteLine(isPowerOfTwo(4)); // True Console.WriteLine(isPowerOfTwo(-4)); // False } public static bool isPowerOfTwo(int x) { if (x == 0) return false; while (x % 2 == 0) x /= 2; return x == 1; } |
И все, вроде бы, с этой функцией хорошо. Она, кажется, даже работает. Но есть у нее значительный минус — ее сложность. Если присмотреться к этой функции, то ее сложность: O(logN). Это, вроде бы, неплохо, но можно (и нужно!) лучше. В этом нам и помогут побитовые операции:
|
1 2 3 4 |
public static bool isPowerOfTwo(int x) { return x != 0 && (x & (x - 1)) == 0; } |
Сложность этой реализации O(1)! Рассмотрим пару примеров:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// x != 0 && (x & (x - 1)) == 0 1) x = 4 = 100b x - 1 = 4 - 3 = 011b x & (x - 1) = 100b & 011b = 000b 100b != 0 && 000b == 0 = true 2) x = 6 = 110b x - 1 = 5 = 101b x & (x - 1) = 110b & 101b = 100b x != 0 && 100b == 0 = false |
Здорово, не правда ли?) Таких, и гораздо более сложных, трюков достаточно много.
Давайте попробуем побитовую операцию исключающее ИЛИ в деле. С помощью этой побитовой операции мы попробуем обменять значение двух переменных местами без использования дополнительной переменной. И для этого воспользуемся свойством обратимости побитовой операции исключающее ИЛИ — (a ^ b) ^ b = a :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public static void Swap(ref int a, ref int b) { a = a ^ b; b = a ^ b; a = a ^ b; } public static void Main(string[] args) { var a = 2; var b = 5; Console.WriteLine($"Before swap: a = {a}, b = {b}"); // Before swap: a = 2, b = 5 Swap(ref a, ref b); Console.WriteLine($"After swap: a = {a}, b = {b}"); // After swap: a = 5, b = 2 } |
Выполним функцию Swap вручную:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
a = 5 = 101b b = 12 = 1100b 1) a = a ^ b = 101b ^ 1100b = 0101b ^ 1100b = 1001b = 9 2) b = a ^ b = 9 ^ 12 = 1001b ^ 1100b = 0101b = 5 3) a = 9 ^ 5 = 1001b ^ 101b = 1001b ^ 0101b = 1100b = 12 |
И последний пример на сегодня. Давайте рассмотрим цвета в формате RGB. Допустим, у нас есть цвет в формате RGB — 0xFF007F. И нам необходимо извлечь значение каждого из каналов. Как нам это сделать? Кажется, тут не обойтись без старых знакомых — побитовых операций.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
static void main(string[] args) { var c1 = 0xFF007F; var r = (c1 & 0xFF0000) >> 16 = (0xFF007F & 0xFF0000) >> 16 = 0xFF0000 >> 16 = 0x0000FF = 255; var g = (c1 & 0xFF00) >> 8 = (0xFF007F & 0xFF00) >> 8 = (0xFF007F & 0x00FF00) >> 8 = 0x000000 >> 8 = 0x000000 = 0; var b = c1 & 0xFF = 0xFF007F & 0xFF = 0xFF007F & 0x0000FF = 0x00007F = 127 Console.WriteLine($"c1: 0x{c1.ToString("X").ToUpper()} r: {r}, g: {g}, b: {b}"); // c: 0xFF007F r: 255, g: 0, b: 127 } |
Таким образом, нам удалось извлечь значения соответствующих каналов цвета. Теперь давайте попробуем восстановить исходный цвет по значениям отдельных каналов:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
static void Main(string[] args) { // ... var c2 = r << 16 | g << 8 | b = 255 << 16 | 0 << 8 | 127 = 0xFF << 16 | 0x00 << 8 | 0x7F = 0x0000FF << 16 | 0x000000 << 8 | 0x00007F = 0xFF0000 | 0x000000 | 0x00007F = 0xFF0000 | 0x00007F = 0xFF007F Console.WriteLine($"c2: 0x{c2.ToString("X").ToUpper()} is equal = {c1 == c2}"); // c2: 0xFF007F is equal = True } |
Мы надеемся, что теперь побитовые операции вам не будут казаться чем-то магическим и непонятным. Немного попрактиковавшись, вы сможете применять побитовые операции в повседневной жизни. Если у вас возникли какие-нибудь вопросы или вы нашли какую-то неточность, то милости просим в комментарии под статьей. А на этом, пожалуй, все. До скорых встреч.