Довольно часто битовую арифметику при обучении программированию обходят стороной, то есть даже если объясняют её правила, то не находят конкретных жизнеспособных примеров использования. В самом деле, если вы пишете драйвер для модема, она может быть нужна, но в обычной программе вряд ли... Или нет?
Давайте посмотрим.
(Рекомендуется сначала изучить материал про двоичную систему.)
Я буду говорить о семействе языков C, JavaScript, Java, PHP и подобных. Также я проверил насчет Питона, и там есть то же самое.
Операции, которые нам доступны с битами, это
& – "и"
| – "или"
~ – "инверсия"
^ – "исключающее или"
<< – "сдвиг влево"
>> – "сдвиг вправо"
Сначала рассмотрим те, что попроще. Например, операция "инверсия" заменяет единицы на нули, и нули на единицы. Проще некуда. Записывается она так:
a = ~a
То есть в данном случае – присвоить переменной a её же инвертированное значение. Если значение a равно 5, и допустим размер переменной 2 байта (тут не забываем о типах данных), то в битовом виде эти два байта выглядят так:
0000000000000101
~a даст нам:
1111111111111010
Это число 65530. Зачем нам нужна такая операция? Пока, наверно, не нужна, но её надо будет использовать вместе с другими операциями.
Дальше посмотрим на сдвиги влево и вправо. Они также очень просты, и просто сдвигают все биты в числе влево или вправо. И мы можем указать, сколько раз сдвинуть. Например:
a = a >> 2;
a = a << 1;
В первой строке мы сдвигаем все биты в числе a вправо 2 раза. Во второй строке сдвигаем эти же биты влево 1 раз. Если a = 5, и её размер 1 байт, то получаем следующий результат:
00000101 – это 5
00000001 – это сдвинуть 2 раза вправо. Получилось 1.
00000010 – это сдвинуть 1 раз влево. Получилось 2.
Когда число сдвигается вправо или влево, то с одного конца у него "выпадает" крайний бит, а с другого на освободившееся место просто пишется 0. Выпадающий бит просто теряется, и его уже не вернуть. То есть сдвинув число столько раз, сколько в нём есть бит, вы вытолкнете из него все оригинальные биты и останутся только нули.
Приносят ли сдвиги пользу? Да, по нескольким причинам.
Посмотрите на обычное число 10. Это один десяток и ноль единиц. Если его умножить на 10, то получится 100. Это одна сотня, ноль десятков и ноль единиц. Если умножить опять на 10, получится 1000. Вы заметили, что когда мы умножаем на 10, то единица в числе каждый раз сдвигается на одну позицию влево? Это потому что мы считаем в десятичной системе. То же самое мы можем сделать в двоичной системе, но так как она двоичная, то умножать надо не на 10, а на 2. Смотрим:
00000001 – это 1
00000010 – это 2 (1 * 2)
00000100 – это 4 (2 * 2)
00001000 – это 8 (4 * 2)
И т.д. Но ведь получается, что умножение на 2 – это битовый сдвиг влево. А деление на 2 – это битовый сдвиг вправо. Значит, вместо умножения на 2 и деления на 2 можно пользоваться битовыми сдвигами влево и вправо. Например, так:
a = a << 3; // сдвиг влево 3 раза, умножение на 8 (2 * 2 * 2)
a = a >> 1; // сдвиг вправо 1 раз, деление на 2
Но зачем пользоваться битовыми сдвигами, когда есть обычные умножение и деление? Потому что битовые сдвиги работают существенно быстрее (это уже не актуально, см.комменты, но может где-то ещё осталось.) Почему тогда все не пользуются битовыми сдвигами? Потому что у них есть ограничения:
- Битовые сдвиги как замена умножения и деления работают только с целыми числами и всегда дают в результате целое число. То есть 5 >> 1 будет не 2.5, а 2. Это тоже бывает полезно, когда вам нужен именно целый результат.
- Битовыми сдвигами можно умножать и делить только на 2, 4, 8, 16, 32 и т.д.
- В результате обычной операции умножения может получиться слишком большой результат, который не помещается в переменную. Некоторые языки следят за тем, чтобы такого не случилось (например, выделяют побольше байт под результат). При битовых сдвигах ничего такого не происходит. Это просто сдвиги, поэтому всем всё равно. И значит, что если при сдвиге влево самый старший бит "выпадет", произойдет усечение данных.
Кроме того, битовыми сдвигами можно получать различные эффекты, например, из любого числа сделать четное:
a = a >> 1;
a = a << 1;
Если число нечетное, самый младший бит у него равен 1. Это не договоренность, это просто математически так получается. С помощью сдвига вправо мы выталкиваем этот бит, он теряется. Затем сдвигом влево мы возвращаем всё назад, но уже без младшего бита (он замещается нулевым битом). Давайте проверим с помощью числа 5:
00000101 – это 5
00000010 – сдвинули вправо один раз, получилось 2
00000100 – сдвинули влево один раз, получилось 4
Так из нечетного числа 5 получилось четное число 4. Если же оно и так было 4, то оно и останется 4.
Чтобы сделать из четного числа нечетное, нужно сделать то же самое и к результату добавить или отнять 1.
Замечу, что такого же эффекта можно добиться и другими битовыми операциями, но мы до них пока не добрались.
Если число состоит из двух байт, то с помощью битового сдвига можно прочитать значение старшего байта. Для этого нужно просто сдвинуть число 8 раз вправо:
1111111100000000 – это 65280, нужно получить старший байт
0000000011111111 – после сдвига вправо получилось 255
Мы получили 255 – старший байт числа.
Кроме того, я применял битовый сдвиг для перемещения фигуры вправо и влево в игре "5-килобайтный Тетрис".
При желании можно найти ещё много применений. Но для полной свободы битовый сдвиг надо комбинировать с другими операциями, о которых речь пойдёт в следующей части.
