Все мы знаем, как работает двусвязный список и что он неэффективно использует память. Но что, если я скажу, что двусвязный список можно реализовать с той же пространственной сложностью, что и односвязный список, с помощью какой-нибудь простой побитовой операции? Да, вы не ослышались! Битовые манипуляции — это то, что пригодится, когда нам нужно что-то оптимизировать. Здесь вместо сохранения исходного адреса памяти мы сохраняем побитовое XOR предыдущего и следующего узла, тем самым уменьшая пространство одного адреса в каждом узле.
Что такое битовая манипуляция?
Битовые манипуляции – это метод манипулирования данными на уровне битов с помощью побитовых операторов. Поскольку компьютеры обычно хранят целые числа в форме дополнения до двух, работа напрямую с битами делает операцию быстрее, чем обычные арифметические операции. Как только вы освоите их, это можно будет применять к огромному количеству проблем, однако всегда следите за тем, чтобы не ставить под угрозу читабельность кода, применяя эти методы.
В этой статье мы рассмотрим основы побитовых операций и некоторые классные фрагменты кода с использованием битов, которые могут сделать наш код элегантнее и быстрее.
Побитовые операторы
Побитовые операторы позволяют вам манипулировать отдельными необработанными битами данных в структуре данных. Давайте посмотрим на различные типы побитовых операторов.
Побитовое И.Операция побитовое И (&) выполняет логическое И битов в каждой позиции числа в двоичной форме, то есть дает 1, только если оба биты равны 1.
Например: 101 и 111 равны 101, так как оба бита становятся единицей только в единицах и сотнях.
Побитовое ИЛИ: оператор побитового ИЛИ (|) работает так же, как побитовое И. Разница в том, что только один из битов должен быть равен 1, чтобы бит этой позиции на выходе был равен 1.
Например: 101 | 111 равно 111, так как оба бита никогда не становились равными нулю вместе.
Побитовое НЕ:в отличие от других побитовых операторов побитовое НЕ (~) принимает только один операнд и инвертирует все его биты, то есть дополнение числа до единицы.
Например: ~101 = 010.
Побитовое исключающее ИЛИ.оператор побитового исключающего ИЛИ или «оператор исключающего ИЛИ» (^) сравнивает биты двух чисел один за другим и дает 1, только если оба бита различны.
Например: 101 ^ 111 равно 010, так как оба бита отличаются только разрядом десятков.
Сдвиг влево: оператор сдвига влево (‹‹) — это бинарный оператор, который сдвигает биты числа влево и добавляет ноль в конце. Интересно, что это эквивалентно умножению числа на степень двойки.
Например: 110 ‹‹ 1 = 1100
То есть 6‹‹1 равно 12, умножение на 2.
Сдвиг вправо: Оператор сдвига вправо(››) — это двоичный оператор, который сдвигает биты числа вправо. Если внимательно присмотреться, это эквивалентно делению числа на степени двойки.
Например: 110 ›› 1 = 11
То есть 6 ›› 1 равно 3, деление на 2.
Трюки с битами
Давайте посмотрим на несколько замечательных битовых хаков, использующих эти концепции.
1. Чтобы получить K-й бит справа
int getBit(int num, int k) {
return num & (1<< (i-1));
}
2. УСТАНОВИТЕ K-й бит справа
void setBit(int &n, int k) {
n = n|(1<< (k-1));
}
3. Переключение K-го бита справа в числе
void toggle(int &n, int k) {
n = n ^ (1 << k - 1);
}
4. Проверить, равны ли два числа
bool equal(int a, int b) {
if (a ^ b == 0)
return True;
return False;
}
5. Проверить, является ли число степенью двойки
bool isPowerof2(int number) {
if (number & (number-1) ==0)
return True;
return False;
}
6. Проверить, является ли число четным или нечетным
bool isEven (int number) {
if(number & 1 == 0)
return True;
return False;
}
7. Найти наибольший общий делитель двух чисел
int gcd(int a, int b){
while(b){
b^=a^=b^=a%=b;
}
return a;
}
8. Поменять местами два целых числа a и b
void swap(int &a, int &b){
a^=b;
b^=a;
a^=b;
}
9. Минимум x и y
int minimum(int x, int y){
int min = (y ^ (x ^ y) & - (x < y));
return min;
}
10. Максимум x и y
int maximum(int x, int y){
int max= (x ^ (x ^ y) & - (x < y));
return max;
}
Практикуйте проблемные ссылки
Поменять местами все нечетные и четные биты
Максимум последовательных единиц III
Следующий больший элемент III
Минимальное количество переворотов, чтобы сделать a OR b равным c
Преобразование вещественное число (от 0 до 1) в двоичную строку
Ресурсы
Связанный список XOR — двусвязный список с эффективным использованием памяти | Набор 1
Хаки с битами
Трюк XOR
Побитовые операции 2 — popcount & bitsets
Спасибо за чтение этой статьи!
