Побитовые операции работают напрямую с двоичным представлением целых чисел.
Оператор
Символ
Пример
Значение
Побитовый сдвиг влево
<<
x << k
Сдвигает все биты x влево на k позиций
Побитовый сдвиг вправо
>>
x >> k
Сдвигает все биты x вправо на k позиций
Побитовое И
&
x & y
Применяет AND к каждой паре соответствующих битов
Побитовое ИЛИ
|
x | y
Применяет OR к каждой паре соответствующих битов
Побитовое исключающее ИЛИ
^
x ^ y
Применяет XOR к каждой паре соответствующих битов
Побитовый сдвиг влево
Когда мы сдвигаем двоичное число
(an−1an−2…a1a0)2
влево на k позиций, мы приписываем k нулей справа:
(an−1an−2…a1a000…0)2
Таким образом, сдвиг влево на одну позицию эквивалентен умножению на 2, а сдвиг влево на k позиций эквивалентен умножению на 2k.
Вывод:
44
Побитовый сдвиг вправо
Когда мы сдвигаем двоичное число
(an−1an−2…a1a0)2
вправо на k позиций, последние k битов удаляются:
(an−1an−2…ak)2
Для неотрицательных целых чисел сдвиг вправо на одну позицию эквивалентен целочисленному делению на 2, а сдвиг вправо на k позиций эквивалентен целочисленному делению на 2k.
Вывод:
2
Побитовое И
Побитовое AND двух чисел (a)2 и (b)2 — это число (c)2, где
ci=ai&bi
Это означает, что мы применяем AND к каждой паре соответствующих битов.
Результат x & y равен 1 только если оба бита равны 1. В противном случае он равен 0.
Таблица AND
x
y
Результат
0
0
0
0
1
0
1
0
0
1
1
1
Вывод:
2
Побитовое ИЛИ
Побитовое OR двух чисел (a)2 и (b)2 — это число (c)2, где
ci=ai∣bi
Это означает, что мы применяем OR к каждой паре соответствующих битов.
Результат x | y равен 1, если хотя бы один из битов равен 1. В противном случае он равен 0.
Таблица OR
x
y
Результат
0
0
0
0
1
1
1
0
1
1
1
1
Вывод:
13
Побитовое исключающее ИЛИ (XOR)
Побитовое XOR двух чисел (a)2 и (b)2 — это число (c)2, где
ci=ai⊕bi
Это означает, что мы применяем XOR к каждой паре соответствующих битов.
Результат x ^ y равен 1, если ровно один из битов равен 1. Если оба бита одинаковые, результат равен 0.
Таблица XOR
x
y
Результат
0
0
0
0
1
1
1
0
1
1
1
0
Вывод:
10
Примеры задач
Попробуйте решить эти задачи самостоятельно, прежде чем смотреть решения.
Пример 1
Даны два целых числа x(0≤x≤29) и y(0≤y≤29), где x=y, выведите значение
2x+2y
Пример 2
Даны два целых числа x(0≤x≤229) и k(0≤k≤29), выведите число, полученное из x после инвертирования k-го бита.
Пример 3
Даны два целых числа x(0≤x≤229) и k(0≤k≤29), выведите число, полученное из x после установки k-го бита в 0.
Пример 4
Даны два целых числа x(0≤x≤229) и k(0≤k≤29), выведите значение k-го бита числа x.
Пример 5
Даны два целых числа x(0≤x≤229) и k(0≤k≤29), установите последние k битов числа x в 0 и выведите результат.
Пример 6
Даны два целых числа x(0≤x≤109) и y(0≤y≤109), вычислите их произведение, не используя операции *, / или %.
Решения примеров
Пример 1
Чтобы получить 2x, мы можем использовать 1 << x. Аналогично, 1 << y даёт 2y.
Поскольку x=y, эти два числа имеют установленные разные одиночные биты, поэтому мы можем объединить их с помощью побитового OR.
Пример 2
Чтобы инвертировать k-й бит, мы используем XOR с маской, у которой только k-й бит равен 1.
Пример 3
Чтобы установить k-й бит в 0, мы можем сначала проверить, равен ли он 1. Если да, мы переворачиваем его.
Более короткая версия:
Пример 4
Чтобы получить значение k-го бита, мы сдвигаем его в последнюю позицию и берём последний бит.
Пример 5
Решение с циклом
Мы проверяем последние k битов по одному и очищаем их при необходимости.
Решение без цикла
Мы сдвигаем число вправо на k битов, что удаляет последние k битов, а затем сдвигаем его обратно влево на k битов.
Пример 6
Мы можем использовать двоичное представление y.
Если i-й бит y равен 1, то мы добавляем x⋅2i, что то же самое, что x << i.
int x = 11; // x = 1011 in binarycout <<(x << 2)<< "\n"; // 101100 in binary
int x = 11; // x = 1011 in binarycout <<(x >> 2)<< "\n"; // 10 in binary
int x = 11; // x = 1011int y = 6; // y = 0110cout <<(x & y)<< "\n"; // 0010 in binary
int x = 9; // x = 1001int y = 4; // y = 0100cout <<(x | y)<< "\n"; // 1101 in binary
int x = 12; // x = 1100int y = 6; // y = 0110cout <<(x ^ y)<< "\n"; // 1010 in binary
cout <<((1<< x) |(1<< y))<< "\n";
cout <<(x ^(1<< k))<< "\n";
if(x &(1<< k)){ x ^=(1<< k);}cout << x << "\n";
cout <<(x &(~(1<< k)))<< "\n";
cout <<((x >> k) & 1)<< "\n";
for(int i = 0; i < k; i++){ if(x &(1<< i)){ x ^=(1<< i);}}cout << x << "\n";
cout <<((x >> k)<< k)<< "\n";
long long res = 0;for(int i = 0; i < 30; i++){ if(y &(1<< i)){ res +=(1LL * x << i);}}cout << res << "\n";