!Побитовый сдвиг

Описание

Битовый сдвиг, как понятно из названия, способен сдвинуть биты вправо или влево. При этом это одна из самых дешевых битовых операций, выполняется очень быстро, в среднем за $O(1)$. На самом деле существует 2 вида сдвигов, логические и арифметические. Логические при сдвиге и вправо и влево просто заполняют освободившиеся биты нулями, а вот арифметические сдвиги могут делать неочевидные вещи. При сдвиге влево арифметические сдвиг также заполнит новые биты нулями, а вот при сдвиге вправо, арифметический сдвиг заполнит новые биты самым левым битом, что был в несдвинутом числе. Связано это с тем, как хранится знаковые числа в компьютере. Самый старший бит у нас в компьютере отвечает за знак, и при логическом сдвиге, если там было 1, там окажется 0 и мы получим не совсем тот результат, который ожидали, если считали, что сдвиг на $k$ поделит число на $2^k$. Так вот если вы хотите воспринимать сдвиг числа, как просто передвижение его битов вправо или влево, то используйте логический сдвиг, а если хотите воспринимать эти биты, как число, а сдвиги в нем как умножения на 2 в какой-то степени, то используйте арифметический сдвиг. В c++ имеет синтаксис << для арифметического сдвига вправо и >> для арифметического сдвига влево. Чтобы получить логический сдвиг мы используем уже 3 треугольных скобки, <<< и >>>. Арифметический сдвиг вправо на n равносилен делению на $2^n$, сдвиг же влево на n умножению на $2^n$. Таким образом можно легко обрезать последние $k$ элементов с помощью комбинации сдвигов вправо и влево на одинаковое количество битов. Очень полезны при написании дп по подмаскам, ведь с помощью сдвигов можно легко проверить kый бит маски.

Вот так выглядит арифметический сдвиг на 2 вправо:

Примеры

#include <bits/stdc++.h>
using namespace std;
int main() {
	long long a = 35; //100011
	a = a >> 2; // 1000
	a = a << 2; // 100000
	cout << a; // Программа выведет 32
}