Побитовые операции
Побитовые операции работают напрямую с двоичным представлением целых чисел.
| Оператор | Символ | Пример | Значение |
|---|---|---|---|
| Побитовый сдвиг влево | << | x << k | Сдвигает все биты x влево на k позиций |
| Побитовый сдвиг вправо | >> | x >> k | Сдвигает все биты x вправо на k позиций |
| Побитовое И | & | x & y | Применяет AND к каждой паре соответствующих битов |
| Побитовое ИЛИ | | | x | y | Применяет OR к каждой паре соответствующих битов |
| Побитовое исключающее ИЛИ | ^ |
x ^ y| Применяет XOR к каждой паре соответствующих битов |
Когда мы сдвигаем двоичное число
влево на позиций, мы приписываем нулей справа:
Таким образом, сдвиг влево на одну позицию эквивалентен умножению на , а сдвиг влево на позиций эквивалентен умножению на .
Вывод:
Когда мы сдвигаем двоичное число
вправо на позиций, последние битов удаляются:
Для неотрицательных целых чисел сдвиг вправо на одну позицию эквивалентен целочисленному делению на , а сдвиг вправо на позиций эквивалентен целочисленному делению на .
Вывод:
Побитовое AND двух чисел и — это число , где
Это означает, что мы применяем AND к каждой паре соответствующих битов.
Результат x & y равен 1 только если оба бита равны 1. В противном случае он равен 0.
| x | y | Результат |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Вывод:
Побитовое OR двух чисел и — это число , где
Это означает, что мы применяем OR к каждой паре соответствующих битов.
Результат x | y равен 1, если хотя бы один из битов равен 1. В противном случае он равен 0.
| x | y | Результат |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Вывод:
Побитовое XOR двух чисел и — это число , где
Это означает, что мы применяем XOR к каждой паре соответствующих битов.
Результат x ^ y равен 1, если ровно один из битов равен 1. Если оба бита одинаковые, результат равен 0.
| x | y | Результат |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Вывод:
Попробуйте решить эти задачи самостоятельно, прежде чем смотреть решения.
Даны два целых числа и , где , выведите значение
Даны два целых числа и , выведите число, полученное из после инвертирования -го бита.
Даны два целых числа и , выведите число, полученное из после установки -го бита в 0.
Даны два целых числа и , выведите значение -го бита числа .
Даны два целых числа и , установите последние битов числа в 0 и выведите результат.
Даны два целых числа и , вычислите их произведение, не используя операции *, / или %.
Чтобы получить , мы можем использовать 1 << x. Аналогично, 1 << y даёт .
Поскольку , эти два числа имеют установленные разные одиночные биты, поэтому мы можем объединить их с помощью побитового OR.
Чтобы инвертировать -й бит, мы используем XOR с маской, у которой только -й бит равен 1.
Чтобы установить -й бит в 0, мы можем сначала проверить, равен ли он 1. Если да, мы переворачиваем его.
Более короткая версия:
Чтобы получить значение -го бита, мы сдвигаем его в последнюю позицию и берём последний бит.
Решение с циклом
Мы проверяем последние битов по одному и очищаем их при необходимости.
Решение без цикла
Мы сдвигаем число вправо на битов, что удаляет последние битов, а затем сдвигаем его обратно влево на битов.
Мы можем использовать двоичное представление .
Если -й бит равен 1, то мы добавляем , что то же самое, что x << i.
int x = 11; // x = 1011 in binary
cout << (x << 2) << "\n"; // 101100 in binary
int x = 11; // x = 1011 in binary
cout << (x >> 2) << "\n"; // 10 in binary
int x = 11; // x = 1011
int y = 6; // y = 0110
cout << (x & y) << "\n"; // 0010 in binary
int x = 9; // x = 1001
int y = 4; // y = 0100
cout << (x | y) << "\n"; // 1101 in binary
int x = 12; // x = 1100
int y = 6; // y = 0110
cout << (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";