Метод битовых операций одинаков для других языков, не ограничиваясь JS, поэтому битовые операции, упомянутые в этой статье, применимы и к другим языкам.
Битовая операция является низкоуровневой операцией, поэтому скорость часто самая высокая (по сравнению с другими операциями, такими как сложение, вычитание, умножение и деление), а некоторые алгоритмы могут быть реализованы с помощью характеристик битовых операций. Правильное использование арифметики имеет много преимуществ. Вот несколько примеров.
1. Используйте побитовое НЕ~, чтобы судить о существовании индекса
Это очень распространенный трюк, например определение того, находится ли число в массиве:
// 如果url含有?号，则后面拼上&符号，否则加上?号
url += ~url.indexOf("?") ? "&" : "?";потому что:
~-1 === 0
Двоичные символы, представленные -1 в памяти, все равны 1, и после побитового отрицания они становятся 0. Дальнейшее объяснение - представление 1 в памяти: 0000...0001, первый 0 указывает, что бит знака положительный, Если это -1, бит знака отрицательный и 1 используется для представления 1000... 0001. Это исходный код -1, тогда бит знака не меняется, а остальные биты инвертируются, чтобы стать 1111...1110, что является обратным к -1. Код указывает, что добавление 1 к обратному коду дает 1111...1111. Это дополнение к -1. В памяти представлены отрицательные числа (машинные числа) с использованием дополнительного кода, а в исходном коде используются положительные числа. Таким образом, номера машин, которые все равны 1, становятся всеми 0 после побитового отрицания. Все остальные числа не равны 0 в битах, поэтому эту функцию можно использовать для вынесения суждений indexOf, что делает код более лаконичным.
2. Поменяйте местами два числа, используя XOR
Самый интуитивно понятный способ поменять местами значения двух целых чисел — использовать временную переменную:
let a = 5,
b = 6;
// 交换a, b的值
let c = a;
a = b;
b = c;Теперь требуется, чтобы никакая дополнительная переменная или пространство содержимого не могли использоваться для замены значений двух целых чисел. В настоящее время мы должны использовать побитовые операции для достижения этой цели с помощью XOR:
let a = 5,
b = 6;
a = a ^ b;
b = a ^ b; // b 等于 5
a = a ^ b; // a 等于 6Почему это? Очень просто, поставьте 1 и 2 формулы:
a = a ^ b;
b = a ^ b;Вместе это эквивалентно:
b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a;Точно так же вместе с уравнением 3 мы можем получить:
a = (a ^ b) ^ a // 在执行第3式的时候b已经变成a了，而a是第1式的a ^ b
= a ^ a ^ b = 0 ^ b = b;Почему a^a = 0, b^b = 0? Потому что операция XOR именно такая. Следующий пример:
01011010
^ 10010110
-----------
11001100Процесс операции XOR можно рассматривать как сложение двух чисел вместе, а затем удаление переноса, 0 + 0 = 0, 1 + 0 = 1, 1 + 1 = 0. Это легко запомнить. Таким образом, a ^ a равно 0 или 1 для всех двоичных битов, результат сложения равен 0 и, наконец, равен 0.
XOR также часто используется для шифрования.
3. Используйте побитовое И & для удаления старших битов
Побитовое И имеет много функций, одна из которых — удалить старшие биты операнда и оставить только младшие.Например, есть два числа a и b:
let a = 0b01000110; // 十进制为70
let b = 0b10000101; // 十进制为133Теперь, когда их старшие биты бесполезны, полезны только младшие 4 бита, то есть последние 4 бита.Чтобы сравнить размер последних 4 битов a и b, вы можете сравнить их следующим образом:
a & 0b00001111 < b & 0b00001111 // trueПервые 4 цифры a и b и 0000 и 0000 станут 0 после тире, а последние 4 цифры и 1111 останутся исходным числом после тире. Фактический результат этого состоит в том, чтобы иметь число, первые несколько цифр которого используются как использование A, а последние цифры используются как использование B. Чтобы устранить влияние первых нескольких цифр на использование B, его можно использовать как это.
Другим примером является маска подсети.Предположим, теперь, когда я являюсь администратором сети, IP-адреса, которыми я могу управлять, находятся в диапазоне от 192.168.1.0 до 192.168.1.255, то есть могут быть выделены только последние 8 бит. Теперь разделите эти IP-адреса на 6 подсетей и различайте их по IP-адресу.Поскольку 6 равно 110 в двоичном формате, первые 3 бита из последних 8 бит используются для представления подсети, а последние 5 бит используются для представления хост (то есть общий хост Диапазон чисел 00001 ~ 11111, всего 30). Маска подсети текущей сети принимается равной 255.255.255.11100000 — это 255.255.255.224. Предположим, IP-адрес определенного хоста — 192.168.1.120. Теперь, чтобы узнать, в какой подсети он находится, вы можете использовать его IP-адрес и маску подсети: 120 и 224 = 96 = 0b01100000, вы знаете, что он находится в подсети 011, которая является подсетью № 3.
Это пример сохранения старших битов и удаления младших битов, что прямо противоположно приведенному выше примеру.
4. Используйте побитовое И & для оценки битов флага
Теперь есть фоновая система управления.Полномочия эксплуатации разделены на администраторов первого, второго и третьего уровня, среди которых администратор первого уровня имеет высшие полномочия, а администраторы второго и третьего уровней - ниже. Некоторые операции разрешены только администраторам первого и второго уровня. , некоторые операции разрешены только администраторам первого и третьего уровня. Пользователь с определенными полномочиями, вошедший в систему, теперь хочет выполнить определенную операцию.Какую структуру данных он может использовать, чтобы легко судить, может ли он выполнить эту операцию?
Мы используем биты для представления прав управления, первый уровень использует третий бит, второй уровень использует второй бит, а третий уровень использует первый бит, то есть полномочия первого уровня выражаются как 0b100 = 4, второго уровня полномочия выражены как 0b010 = 2, а третий уровень выражен как 0b100 = 4. Разрешения уровня представлены как 0b001 = 1. Если операция A может выполняться только операциями первого и второго уровня, то это значение разрешения выражается как 6 = 0b110, что совпадает с разрешением первого уровня: 6 и 4 = 0b110 и 0b100 = 4. , полученное значение не равно 0, поэтому считается, что Разрешение есть.Точно так же разрешение второго уровня и следующие за ним 6&2=2 не равны 0, а разрешение третьего уровня и следующие за ним 6&1=0 , поэтому разрешение третьего уровня не имеет разрешения. 1 флага здесь означает открытие, а 0 означает закрытие.
Преимущество этого заключается в том, что мы можем использовать число вместо массива для представления набора разрешений операции, и это также очень удобно при оценке разрешений.
5. Используйте побитовый | для построения наборов свойств
Набор атрибутов разрешений построен выше. Примеров наборов атрибутов много. Например, в моем "Краткий обзор разработки Google Карт"Включает в себя пример оценки границ - всплывающее окно с плавающей рамкой в текущей позиции мыши, как показано слева на следующем рисунке, но когда мышь находится ближе к стороне, это приведет к тому, что плавающая рамка превысит границу , как показано справа на следующем рисунке.
Для этого необходимо определить границы. Существует три вида условий превышения: правое, верхнее и левое, и они могут накладываться друг на друга. Например, когда мышь находится в верхнем левом углу, левое и верхнее стороны превысят одновременно. Необходимо записать ситуацию превышения и отрегулировать ее.Используйте 001, чтобы указать правое превышение, 010, чтобы указать верхнее превышение, и 100, чтобы указать левое превышение.Следующий код вычисляет:
let postFlag = 0;
//右边超出
if(pos.right < maxLen) posFlag |= 1;
//上面超出
if(pos.top < maxLen) posFlag |= 2;
//左边超出
if(pos.left < maxLeftLen) posFlag |= 4;
//对超出的情况进行处理，代码略
switch(posFlag){
case 1: //右
case 2: //上
case 3: //右上
case 4: //左
case 6: //左上
}Если левая часть и вышеуказанная превышены одновременно, то 6 = 0b110 получается операцией ИЛИ 2|4 = 6. Вы знаете ситуацию превышения, и этот код лучше, чем писать два суждения в if.
6. Комплексное применение битовых операций
Вот пример — выполнение сложения без сложения, вычитания, умножения и деления часто используется для проверки владения битовыми операциями. Читатели могут попытаться проанализировать и реализовать его самостоятельно.
Вы не можете использовать сложение, вычитание, умножение и деление, а это значит, что вам нужно использовать побитовые операции для выполнения вычислений. Для иллюстрации на практическом примере, таком как a = 81 = 0b1010001, b = 53 = 0b0110101. С помощью операции XOR мы обнаруживаем, что XOR складывает два числа, но не может их переносить, а с помощью операции AND мы можем узнать, какие биты нужно переносить, следующим образом:
1010001
^ 0110101
---------
1100100
1010001
& 0110101
---------
0010001Сдвиг значения, полученного операцией И, влево на один бит и добавление значения, полученного операцией XOR, эквивалентно реализации переноса, что не должно быть трудным для понимания. Чтобы реализовать сложение этих двух чисел, этот процесс можно повторить: сначала XOR, затем AND, а затем перенос, пока сложение не будет завершено, когда перенос больше не нужен. Так что нетрудно написать следующий код:
function addByBit(a, b) {
if (b === 0) {
return a;
}
// 不用进位的相加
let c = a ^ b;
// 记录需要进位的
let d = a & b;
d = d << 1;
// 继续相加，直到d进位为0
return addByBit(c, d);
}
let ans = addByBit(5, 8);
console.log(ans);Битовые операции также часто используются для генерации случайных чисел и хэшей, например, алгоритм Chrome для хеширования строк выглядит так:
uint32_t StringHasher::AddCharacterCore(uint32_t running_hash, uint16_t c) {
running_hash += c;
running_hash += (running_hash << 10);
running_hash ^= (running_hash >> 6);
return running_hash;
}Продолжайте накапливать значение ASCII текущей строки, которая использует XOR, сдвиг влево и сдвиг вправо.
В этой статье представлено несколько практических примеров использования битовых операций с целью углубить понимание битовых операций и помочь в разработке.