Я не буду говорить, насколько быстр битовый алгоритм, если вы мне не верите, вы можете использовать 1 миллиард данных для его моделирования.Сегодня я расскажу вам несколько классических примеров битовой операции. Однако самое главное не понимать эти примеры, а больше использовать навыки битовых операций в будущем.Конечно, использование битовых операций можно и принудительно.Если не верите, посмотрите вниз. Я начну с самого простого, и каждый из них сложнее другого, но на самом деле речь идет о навыках, так что это не будет слишком сложно, я думаю, вы сможете понять это за несколько минут.
Судейский паритет
Судя по тому, основано ли число на или на четном числе, я полагаю, что многие люди сделали это, общий код выглядит следующим образом.
if( n % 2) == 01
// n 是个奇数
}
Фактически, если n отображается в двоичной форме, нам нужно только определить, является ли последняя двоичная цифра 1 или 0. Если это 1, это представляет нечетное число, а если это 0, оно представляет четное число, поэтому используется метод битовой операции. Код показан ниже:
if(n & 1 == 1){
// n 是个奇数。
}
Кто-то может сказать, что если мы запишем его в виде n % 2, то компилятор автоматически оптимизирует для нас побитовую операцию, действительно, некоторые компиляторы автоматически оптимизируют ее для нас. Однако было бы лучше, если бы мы могли написать его сами в виде битовых операций. Другие видят ваш код, я полагаюсь на него, круто. Незримо вы все еще можете притворяться навязчивым, верно? Конечно, эффективность времени также намного быстрее.Если вы мне не верите, проверьте это.
2. Поменять местами два номера
Я полагаю, что многие люди писали об обмене двумя числами каждый день, и я также считаю, что вы будете использовать дополнительную переменную каждый раз, чтобы облегчить обмен.Например, мы хотим обменять значения x и y.Традиционный код выглядит следующим образом:
int tmp = x;
x = y;
y = tmp;
Есть ли проблема написать это? Нет проблем, это легко понять, если кто-то захочет вас однажды опозорить, ** не позволяет вам использовать дополнительные вспомогательные переменные для завершения обмена? **Не упоминайте об этом, некоторых людей действительно спрашивали в интервью, и в это время Дафа побитовой операции уже здесь. код показывает, как показано ниже:
x = x ^ y // （1）
y = x ^ y // （2）
x = x ^ y // （3）
Я полагаюсь на, Ниуби! Все три равны x ^ y, так что обмен необъяснимо успешен. Позвольте мне объяснить здесь, мы знаем, что два одинаковых числаисключающее ИЛИТогда результат будет равен 0, т. е. n ^ n = 0. И любое число подвергается операции XOR с 0 и равно самому себе, т.е. n ^ 0 = n. Итак, объяснение следующее:
Переводя x в (1) в x в (2), мы имеем
у = х ^ у = (х ^ у) ^ у = х ^ (у ^ у) = х ^ 0 = х. Значение x успешно присвоено y.
Для (3) вывод следующий:
х = х ^ у = (х ^ у) ^ х = (х ^ х) ^ у = 0 ^ у = у.
Объясните здесь, операция XOR поддерживает операциюКоммутативные и ассоциативные законыОй.
В будущем, если другие не поймут ваш код и попытаются быть высокоуровневыми, вы можете использовать такую формулу в коде для обмена значениями двух переменных.Не приходите ко мне, если вас побьют .
Говоря об этом, я хочу рассказать вам о силе битовых операций, чтобы вы могли больше использовать битовые операции для решения некоторых задач в будущем. Продолжайте смотреть вниз, следующие вопросы также очень распространены, и вы, возможно, задавали их раньше.
3. Найдите число, которое не повторяется
Учитывая набор целочисленных данных, в этих данных одно из чисел встречается только один раз, а другие числа встречаются дважды, позвольте вам найти число.
Многие люди могут использовать хеш-таблицу для хранения этого вопроса.Каждый раз, когда она сохраняется, записывается количество вхождений определенного числа, и, наконец, хеш-таблица просматривается, чтобы увидеть, какое число встречается только один раз. Временная сложность этого метода составляет O(n), а пространственная сложность также равна O(n).
Однако, что я хочу вам сказать, так это то, что использование битовых операций для этого абсолютно качественно!
Мы только что сказали, что результатом операции XOR двух одинаковых чисел является 0, а результатом операции XOR числа и 0 является он сам, поэтому мы выполняем операцию XOR всех целых чисел этой группы, например, эта группа данных: 1, 2 , 3, 4, 5, 1, 2, 3, 4. 5 из них появляются только один раз, остальные появляются дважды, XOR их всех, и результат следующий:
Так как XOR поддерживает коммутативные и ассоциативные законы, то:
1^2^3^4^5^1^2^3^4 = (1^1)^(2^2)^(3^3)^(4^4)^5=0^0^0^ 0^5 = 5.
То есть те числа, которые появляются дважды, становятся 0 после операции XOR, а число, которое появляется один раз, становится равным самому себе после операции XOR с 0. Просто спросите, является ли это решение потрясающим? Итак, код выглядит следующим образом
int find(int[] arr){
int tmp = arr[0];
for(int i = 1;i < arr.length; i++){
tmp = tmp ^ arr[i];
}
return tmp;
}
Временная сложность — O(n), пространственная сложность — O(1), и выглядит это потрясающе.
4, 3 в энной степени
Если бы вас попросили решить число 3 в n-й степени, а вы не смогли бы использовать функцию pow, которая поставляется вместе с системой, что бы вы сделали? Это не просто, просто умножьте n 3 подряд, код такой:
int pow(int n){
int tmp = 1;
for(int i = 1; i <= n; i++) {
tmp = tmp * 3;
}
return tmp;
}
Но если вы сделаете это, то смогу только я, ха-ха, временная сложность O(n), боюсь, что смогут даже ученики начальной школы! Если бы вас попросили сделать это с помощью побитовых операций, что бы вы сделали?
Приведу пример, например, n = 13, тогда двоичное представление n равно 1101, тогда 3 в 13-й степени можно разобрать так:
3^1101 = 3^0001 * 3^0100 * 3^1000.
Мы можем прочитать 1101 бит за битом с помощью & 1 и >> 1, а когда оно равно 1, умножить множитель, представленный этим битом, на окончательный результат. Просто посмотрите на код, его легче понять:
int pow(int n){
int sum = 1;
int tmp = 3;
while(n != 0){
if(n & 1 == 1){
sum *= tmp;
}
tmp *= tmp;
n = n >> 1;
}
return sum;
}
Временная сложность почти O(logn), и это выглядит потрясающе.
Позвольте мне рассказать об этом здесь.Во многих случаях битовые операции очень бинарно связаны, поэтому мы должны судить, битовые ли это операции или нет.Во многих случаях мы будем разбивать их на двоичные, а затем наблюдать за характеристиками, или просто использоватьИ, ИЛИ, Исключающее ИЛИКороче говоря, я думаю, что проще начать работу, посмотрев несколько примеров и сделав больше самостоятельно. Итак, продолжайте смотреть вниз, будьте внимательны, не смотрите сначала на ответ, посмотрите, сможете ли вы сделать это сами.
5. Найдите наибольшую степень степени 2, не превышающую N.
Традиционный способ — продолжать умножать 1 на 2. Код выглядит следующим образом:
int findN(int N){
int sum = 1;
while(true){
if(sum * 2 > N){
return sum;
}
sum = sum * 2;
}
}
Таким образом, временная сложность равна O(logn), а что, если изменить ее на битовую операцию? Как я только что сказал, если мы хотим использовать побитовые операции, мы часто разбиваем число на двоичное и смотрим, что находим. Позвольте мне привести пример здесь.
Например, N = 19, тогда преобразование в двоичный код будет 00010011 (для удобства я использую для представления 8-битный двоичный код). Тогда число, которое мы ищем, помещается в двоичный кодКрайняя левая 1 зарезервирована, а все последующие 1 становятся 0. То есть наш целевой номер 00010000. Итак, как получить этот номер? Соответствующее решение выглядит следующим образом:
1. Найдите самую левую единицу и превратите все 0 справа от нее в единицы.
2. Добавьте 1 к полученному значению, чтобы получить 00100000 или 00011111 + 1 = 00100000.
3. Сдвинуть полученное 00100000 на один разряд вправо, чтобы получилось 00010000, то есть 00100000 >> 1 = 00010000.
Итак, вопрос в том, как преобразовать 0 за крайней левой 1 в 1 на первом шаге? Я сначала дам код, а потом объясню. Следующий код может преобразовать все 0 после самой левой 1 в 1,
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
делается путем сдвига n вправо и выполненияилиможно получить операцию. Поясню, мы предполагаем, что самая левая 1 находится в k-м бите в двоичном бите (считая слева направо), тогда после сдвига n вправо на единицу, k+1-й бит в полученном результате тоже должен быть 1 , а затем ИЛИ над n и результатом после сдвига вправо, то k-й и k + 1-й биты в полученном результате должны быть равны 1; аналогичным образом сдвинем n вправо еще на два разряда, тогда k-й в полученный результат должен быть 1 + 2, а k + 3-й бит должен быть 1, а затем снова выполнить операцию ИЛИ, тогда вы можете получить k-й, k + 1, k + 2, k + 3 все равны 1 и т. д. ....
Окончательный код выглядит следующим образом
int findN(int n){
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8 // 整型一般是 32 位，上面我是假设 8 位。
return (n + 1) >> 1;
}
Временная сложность этого подхода составляет примерно O(1), и дело в высокой силе.
Суммировать
Вопросов выше 5. Хотел написать десять вопросов, но обнаружил, что давно написал пять вопросов. Если у вас есть десять вопросов, боюсь, что у вас не хватит терпения их закончить, а один сложнее, чем другие. , .
Однако в примерах, которые я привел, дело не в том, что вы будете в порядке после изучения этих вопросов, а в том, что у вас появится осознание:Во многих случаях побитовые операции являются хорошим выбором., по крайней мере эффективность времени будет намного быстрее, иВысокая сила, обязательно для принуждения. Так что в будущем можете попробовать больше использовать битовые операции, а я найду для вас несколько вопросов, о которых вы сможете поговорить в будущем. учиться.
Если вы считаете, что эта статья хороша, вы можете также
1,как, чтобы больше людей могли увидеть этот контент.
2,Подписывайтесь на меня, пусть будут долгосрочные отношения
3. Подпишитесь на официальный аккаунт »трудолюбивый кодер», в нем более 100 оригинальных статей, а также я поделился большим количеством видео, книжных ресурсов и средств разработки, приветствую ваше внимание и читайте мои статьи как можно скорее.