Битовые операторы
Особенный интерес представляет битовая запись целого числа в памяти компьютера, то есть двоичная запись числа, где каждый разряд помещается в отдельную ячейку памяти – бит. Для примера запишем представление числа \(13\) в восьмибитной ячейке памяти. Переведем число в двоичную систему и запишем разряды числа с выравниванием по правому краю. Слева заполним ячейки незначащими нулями:
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
Во многих языках программирования допустимы логические операции над битами целых чисел. В отличие от обычных логических операций, результатом выполнения которых будет логический тип данных, битовые операции просто изменяют целое число согласно определенным правилам. Точнее, битовые операции изменяют отдельные биты двоичного представления числа, в результате чего изменяется его десятичное значение.
В Python определены следующие битовые операции:
● x | y – побитовое "или";
● x ^ y – побитовое исключающее "или";
● x & y – побитовое "и";
● x << y – побитовый сдвиг влево;
● x >> y – побитовый сдвиг вправо;
● ~x – инверсия битов.
Разберем подробнее каждую их этих операций. Переведем пару положительных целых чисел в двоичное представление в восьмибитовой ячейке памяти: \(57_{10} = 00111001_2, \ 146_{10} = 10010010_2\) Теперь расположим биты второго числа под соответствующими битами первого и применим обычные логические операции к цифрам, стоящим в одинаковых разрядах первого и второго числа. Единица соответствует логическому True, ноль - логическому False. Если результат логической операции True, то в ответ запишем \(1\), иначе \(0\).
Так, получим, что 57 & 146 = 16:
| \(57_{10}=\) | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| \(146_{10}=\) | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| \(16_{10}=\) | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
Битовое "или" двух разрядов будет равно \(0\), только в том случае, если оба разряда \(0\), иначе \(1\). Так, 57 | 146 = 187:
| \(57_{10}=\) | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| \(146_{10}=\) | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| \(187_{10}=\) | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
Битовый xor (исключающее "или") двух разрядов будет равен \(1\), если биты различные, и \(0\) – если одинаковые. 57 ^ 146 = 171:
| \(57_{10}=\) | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| \(146_{10}=\) | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| \(171_{10}=\) | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
Операция инвертирования ~57 меняет каждый бит числа на противоположный – \(1\) на \(0\) и наоборот.
Битовый сдвиг влево перемещает все биты числа влево на \(n\) позиций и добавляет справа нули. Сдвиг на один разряд влево означает, что все единицы числа увеличили свой разряд, т.е. их вес в числе увеличился в \(2\) раза, значит в \(2\) раза увеличится и значение всего числа. Сдвиг на \(n\) – означает, что умножение на \(2\) было выполнено \(n\) раз. Значит битовый сдвиг влево на \(n\) делает тоже самое, что умножение числа на \(2^n\): x << n == x * 2 ** n. Однако битовый сдвиг влево работает значительно быстрее, поскольку работает с внутренним представлением числа в памяти.
Еще одно полезное применение битового сдвига влево - это получение числа \(2^n\) – для этого нужно сделать битовый сдвиг \(1\) влево на \(n\). Получится число, у которого \(1\) стоит в \(n+1\)-й позиции справа, что соответствует двоичной записи числа \(2^n\):
x = 1 << 10
print(f"{x}")
1024
Битовый сдвиг вправо на \(n\) сдвигает каждый бит числа вправо на \(n\) разрядов. Часть значащих разрядов справа “выпадет” из числа. При сдвиге на \(1\) вес каждого разряда числа уменьшается в \(2\) раза, а значит уменьшится и вес всего числа. Если число четное, то битовый сдвиг вернет ровно половину исходного числа, а если нечетное – то результат деления пополам с округлением вниз. В общем случае, битовый сдвиг вправо на \(n\) соответствует целочисленному делению числа на \(2^n\): x << n == x // 2 ** n . Как и при сдвиге влево, битовая операция будет работать значительно быстрее целочисленного деления.
Зачем нужны битовые операции? В байтах не всегда хранятся числа. Байт или ячейку памяти можно представить просто как список бит, а значит, в ней можно, например, хранить набор флагов (установлен — сброшен), представляющих собой информацию о состоянии какой-то системы. С помощью битовых операций можно проверить, какие биты в байте установлены в единицу, можно обнулить биты или, наоборот, установить в единицу. Можно сменить значения битов на противоположные.
Для установки битов в единицу используется битовое "или". Если побитово сложить двоичное представление числа \(x\) с \(00000000\), то получим само число. Однако если мы в каком-нибудь бите второго слагаемого напишем единицу, то в результате в этом бите будет установлена единица. Получить число, у которого в разряде \(n\) стоит \(1\) можно используя битовый сдвиг \(1\) на \(n\) влево: 1 << n. Значит, установить \(n\)-й бит в \(x\) в единицу можно выражением x |= 1 << n.
Для смены значений битов на противоположные используется битовая операция xor. Чтобы инвертировать определенный бит числа \(x\), в такой же по разряду бит второго числа записывают единицу, остальные биты числа – нули. Если в исходном числе в этом разряде стояла \(1\), то \(1 \ xor \ 1 = 0\), а если стоял \(0\), то \(0 \ xor \ 1 = 1\). Значит, заменить \(n\)-й бит числа \(x\) на противоположный можно командой x ^= 1 << n.
Найти младший единичный бит можно выражением b = a & -a.