В спортивном/олимпиадном программировании могут пригодиться битовые операции, поэтому сегодня и завтра мы попробуем узнать что это:
Для начала, что такое бит: 1 бит информации — символ, который может принимать два значения: включено или выключено, 0 или 1. Для бита № i известно, что он несет в себе 2^(i-1) умноженное на 0 или 1 в зависимости от того, есть ли там значение. То есть число 0101 в двоичной системе счисления = 1*2^0 + 0*2^1 + 1*2^2 + 0*2^3 = 1 + 0 + 4 + 0 = 5. Мы знаем, что в одном байте помещается 8 бит, и посмотрим на одно число записанное 8 битами: 00110101 это число: 1 + 4 + 16 + 32 = 53
Побитовое ИЛИ: записывается как “|” и смотрит по очереди на все биты. Когда он смотрит на один и тот же бит двух чисел, если хотя бы один из них 1, то записывает 1. Например: 4|10 4 = 0100(в двоичной системе счисления) 10 = 1010(в двоичной системе счисления) смотрим на первый бит: у четырёх это 0, а у десяти это 0 и побитовое ИЛИ запишет 0. смотрим на второй бит: у четырёх это 0, а у десяти это 1 и побитовое ИЛИ запишет 1. смотрим на третий бит: у четырёх это 1, а у десяти это 0 и побитовое ИЛИ запишет 1. смотрим на четвертый бит: у четырёх это 0, а у десяти это 1 и побитовое ИЛИ запишет 1. и наше ИЛИ записало 1110 (в двоичной системе счисления) и это 14. То есть 4|10 = 14.
Побитовое И: записывается как “&” и смотрит по очереди на все биты. Когда он смотрит на один и тот же бит двух чисел, если оба они равны одному, то записывает 1. Например: 8 & 10 8 = 1000(в двоичной системе счисления) 10 = 1010(в двоичной системе счисления) смотрим на первый бит: у восьми это 0, и у десяти это 0 и побитовое И запишет 0. смотрим на второй бит: у восьми это 0, а у десяти это 1 и побитовое И запишет 0. смотрим на третий бит: у восьми это 0, и у десяти это 0 и побитовое И запишет 0. смотрим на четвертый бит: у восьми это 1, и у десяти это 1 и побитовое И запишет 1. и наше И записало 1000 (в двоичной системе счисления) и это 8. То есть 8 & 10 = 8.
Побитовое НЕ: Смотрит по очереди на все биты одного числа и меняет его на противоположный. записывается как “~” Например: рассмотрим число 7 в пяти битовой системе: 7 = 00111(в двоичной системе счисления) ~7 запишет 11000(в двоичной системе счисления) = 24
XOR: Работает как побитовое ИЛИ только если оба числа равны 1, то запишет уже не 1, а 0. Записывается как “^”.
Например: 2^10 2 = 0010(в двоичной системе счисления) 10 = 1010(в двоичной системе счисления) смотрим на первый бит: у двух это 0, а у десяти это 0 и XOR запишет 0. смотрим на второй бит: у двух это 1, а у десяти это 1 и XOR запишет 0. смотрим на третий бит: у двух это 0, а у десяти это 0 и XOR запишет 0. смотрим на четвертый бит: у двух это 0, а у десяти это 1 и XOR запишет 1. и наш XOR записало 1000 (в двоичной системе счисления) и это 8. То есть 2^10 = 8.
Битовый сдвиг: есть вправо, записывается как “>>” и влево, записывается как “<<” и сдвигает все биты вправо или влево. например для числа 5: 5 = 101(в двоичной системе счисления) 5 << 1 = 1010(в двоичной системе счисления) = 10 5 << 2 = 10100(в двоичной системе счисления) = 20 5 >> 1 = 10(в двоичной системе счисления) = 2 и мы можем заметить что: n << k = n*2(в степени k) 5 << 2 = 5*4 = 20 n >> k = n//2(в степени k) 5 >> 1 = 5//2 = 2 то есть битовый сдвиг вправо умножает число на степень двойки, а битовый сдвиг влево целочисленно делит число на степень двойки. Но при этом битовые сдвиги работают быстрее операций умножения и деления.
(обозначение операций приведены на примере языка c++) мой сайт с данной информацией
