Двоичные операции
В современных реалиях мегамощных компьютеров (давайте я буду называть их исполнителями, потому что имеются ввиду вообще все устройства, способные выполнять программу, а это и компьютеры и ноутбуки и телефоны и прочие содержащие электронную слаботочную начинку утюги) вряд ли кто-то задумывается об оптимизации скорости выполнения программы или экономии занимаемой памяти. Но всё меняется, когда программист впервые принимает сложное решение: запрограммировать микроконтроллер или другой «интернет вещей». Там в вашем распоряжении жалкие пара мегабайт памяти, если очень повезёт, в которые нужно не только как-то впихнуть текст программы и исполняемый бинарный код, но и какие-то промежуточные, пользовательские и другие данные, буферы обмена и обработки. Другая ситуация, в которой нужно начинать «думать о занимаемом пространстве» это разработка протоколов передачи данных, чтобы протокол был быстрый, не гонял по сети сумасшедшие килобайты данных и быстро преобразовывался (сериализовался/десериализовался). На помощь приходит натуральная (если можно так выразиться) для информатики система счисления, двоичная. И правда, если нам нужно передать по сети, например, поле для игры в морской бой, размером 10х10, каждая клетка которого может находиться как минимум в трёх состояниях (закрыта, пуста, занята) нам для такой передачи явно будет недостаточно булева типа, но и самый маленький тип в java - byte с его диапазоном -128...127 будет чрезвычайно избыточен. Если не использовать никаких оптимизаций то одна посылка будет занимать сто байт. Мы же можем придумать такой протокол, который сможет уместить поле 10х10 в 200 бит, то есть в 25 байт. В четыре раза компактнее, а значит и быстрее. Как это сделать?
Лирическое отступление:
Системы счисления
Числа не существуют сами по себе, они связаны определёнными в математической науке законами и полностью подчиняются ей. Программирование, как один из аспектов жизни тоже полностью подчинено математике (называется сложным словосочетанием «математическая доказательность»), но не такой математике, которой пугают людей, а базовой, на уровне «прочитать число», «записать число», произвести сложение, вычитание, умножение. Запись чисел осуществляется поразрядно, то есть одно число может содержать несколько цифр, стоящих друг за другом. Разряды в записи чисел увеличивают свой вес справа налево, то есть самая правая цифра - самая маленькая. В любой системе счисления более значимый разряд всегда находится левее и увеличивается на единицу, если менее значимый разряд «переполняется». Мы можем это увидеть в привычной нам десятичной системе счисления, когда разряд единиц достигает цифры девять, на единицу увеличивается разряд десятков, а разряд единиц «сбрасывается в ноль». Просто потому, что такое основание, можно сказать, что «так исторически сложилось» или «других цифр не придумали» (кстати, для шестнадцатеричной системы счисления, в итоге придумали)
Двоичная система счисления
Представляет особенный интерес для области информационных технологий, поскольку вся электроника работает по принципу «есть напряжение или нет напряжения», единица или ноль. Все числа из любых систем счисления в результате преобразуются в двоичную и представляются в виде набора единиц и нулей. Так для записи десятичного числа 116 используется двоичная запись 1110100. Преобразование из системы счисления с бОльшим основанием в систему счисления с меньшим основанием производится последовательным делением исходного числа на основание системы счисления и записи остатков такого деления в младшие разряды. Например:
116/2= 58(0) /2= 29(0) /2= 14(1) /2= 7(0) /2= 3(1) /2= 1(1) /2= 1< 2
В этом примере полученные остатки от деления записаны в скобках и можно обратить внимание на то, что они полностью повторяют запись числа 116 показанную ранее в зеркальном отражении. Обратное преобразование - это последовательное умножение разрядов числа на величину каждого разряда с их аккумулированием к общему результату:
1110100= 0*1+ 0*2+ 1*4+ 0*8+ 1*16+ 1*32+ 1*64= 4+ 16+ 32+ 64= 116
В программах двоичный числовой литерал записывается с префиксом 0b,то есть для нашего примера 0b1110100. Поскольку двоичная система счисления является основной для компьютерной техники, помнить, например, значения степеней двойки - обычно, хорошее подспорье в работе.
Вернёмся к нашему полю 10х10.
Представления чисел.
Для того, чтобы записать три состояния нам нужны двоичные числа 0(00), 1(01) и 2(10). Что, очевидно, занимает два разряда двоичной записи и даже ещё остаётся место для четвёртого (третьего) состояния 11. То есть четыре ячейки поля могут быть записаны в 2х4 разрядах, в одном стандартном восьмибитном байте. Давайте разбираться, как это сделать, и что нам это даёт. Итак мы можем равноправно считать как в десятичной, так и в двоичной системах счисления, значение числа останется прежним, как его ни записывай. Поэтому мы можем сказать, что один байт, состоящий из восьми бит может сохранить для нас четыре клетки нашего поля по четыре состояния каждая, для этого его надо разделить на пары битов 00_00_00_00. Каждая пара будет в состоянии сохранить значение 0(00), 1(01), 2(10) или 3(11). В этом случае нам становится неудобно записывать наши данные в десятичной системе счисления, ведь не сразу очевидно, какое именно число скрывается за двоичным кодом, например, 01_10_00_10. Далее, для удобства восприятия я буду разделять запись байта на такие пары.
Маски и битовые сдвиги
Чтобы записать число в переменную мы используем привычный оператор присваивания и пишем byte a = 3; Исполнитель в этом случае превратит некоторую область памяти из 00_00_00_00 в 00_00_00_11. Мы можем попросить исполнителя сместить записанные биты влево или вправо на нужное количество разрядов используя оператор << или >> соответственно. Например, byte a = 3 << 2; В этом случае переменная будет иметь вид 00_00_11_00, что равно двенадцати. Внимательный читатель мог заметить, что сдвинуть на 2 это тоже самое, что умножить на 4. Если развивать эту мысль, то можно однозначно сказать, что сдвиг числа влево на N разрядов эквивалентен умножению этого числа на 2 в степени N. Можем ли мы как-то удобно получить нужное значение из конкретных битов без необходимости двигать их туда-обратно? Конечно, для этого придумали маски.
Например, я хочу узнать, какое значение имеет самый младший бит (признак чётности) в записанном значении byte a = 3; Я применяю к этому числу так называемую маску: говорю, что остальные биты мне не важны, и я хочу увидеть состояние именно этого. На помощь спешит операция побитового И. В некоторых источниках её ещё называют арифметическим И. Записывается она в виде амперсанда (&) и возвращает для разряда единицу только если в обоих операндах в соответствующих разрядах единицы. То есть:
3(00_00_00_11) & 1(00_00_00_01) = 1(00_00_00_01); 4(00_00_01_00) & 1(00_00_00_01) = 0(00_00_00_00).
Как видно, мы получили в результате цифру, обозначающую чётность исходного числа. Накладывать такие маски можно не только на один разряд, но на любое их количество. Маска для двух разрядов это &3, для трёх &7, для четырёх &15 и так далее &31, &63. Эти числа неожиданно сильно напоминают степени двойки, не правда ли? Маски также можно сдвигать относительно проверяемого числа, например, проверить старшие два разряда нашего замученного байта можно так: byte result = a & (3 << 6); здесь мы двухбитную маску 3(11) сдвигаем на шесть разрядов (11_00_00_00) и накладываем на число a (xx_xx_xx_xx & 11_00_00_00) таким образом нам вернётся состояния именно этих двух битов, остальные биты этого числа мы игнорируем (маскируем) они станут нулями. И нам, кстати, совершенно нет дела до того, какое будет у байта десятичное представление. А чтобы получить не просто значение маскированной переменной, а именно этих двух старших битов, нужно полученное маскированное значение сдвинуть обратно вправо на количество битов, на которое изначально сдвигали влево. То есть если мы изначально xx сдвинули на шесть разрядов влево, теперь маскированное значение нужно сдвинуть на шесть разрядов вправо.
Заключение
Тема битовых операций постепенно теряет свою актуальность в связи с развитием технологий, скоростей, объёмов. Скорее всего, битовые операции в ближайшем будущем перейдут в разряд узкоспециальных знаний и будут применяться только при программировании микроконтроллеров. И правда, зачем такие сложные вещи в условном JavaScript/HTML5, где основная задача - это быстро и красиво для разработчика и пользователя, и можно не особо считать потраченные килобайты.
Постскриптум
N << K = N * 2 в степени K
N >> K = N / 2 в степени K
x & y = битовая. 1 если оба x == 1 и y == 1
X && Y = литеральная.
x | y = битовая. 1 если хотя бы один из x == 1 или y == 1
X || Y = литеральная
x ^ y = битовая. 1 если x отличается от y
~x = битовая. 1 если x == 0
!X = литеральная
Литеральные операции применяются ко всему числовому литералу целиком, а не к каждому отдельному биту. Здесь особенность в том, как язык программирования интерпретирует числа. В Java, например, в таких операциях может участвовать только тип boolean, а C++ воспринимает любой ненулевой числовой литерал как истину, а нулевой, соответственно, как ложь. Логика формирования значения при этом остаётся такой же, как и при битовых операциях.