Введение в побитовые операторы (и способы их применения).
Далее следует краткое введение в обработку двоичных чисел и поразрядных логических операций в JavaScript, за которым следуют 13 уроков с разрядностью. Наслаждаться!
Странный (но необходимый) бит
Все числа в JavaScript представляют собой 64-битные числа с плавающей запятой. Однако, когда используются побитовые операторы, JavaScript внутренне преобразует их в усеченные 32-битные целые числа со знаком в дополнении до 2, а затем выполняет побитовые операции с ними перед преобразованием результата обратно в 64-битное число двойной точности. Вы можете думать об этом так:
5 << 1 // valid expression 00000000000000000000000000000101 << 1 // (whats basically going on 00000000000000000000000000001010 // …behind the scenes) 10 // return value
Если вы хотите работать в двоичном формате, вы можете ожидать, что будет хороший способ представления чисел в двоичном формате, и ... вы были бы правы! ES6 представил двоичные литералы, которые имеют форму 0b, за которой следует последовательность из единиц и нулей, например, 0b1001 представляет число, представленное десятичным целым числом 9. Как и все числовые литералы в JavaScript, они просто выражают 64-битные числа с двойной точностью другим способом, для удобства. Они определенно не ближе к металлу, и JavaScript все еще должен выполнять фактическое преобразование в / из 32-битных целых чисел за кулисами. Таким образом, использование двоичных литералов вместо их десятичных или шестнадцатеричных эквивалентов не позволяет сэкономить время. При этом побитовые решения данной проблемы обычно быстрее и занимают меньше места, чем их небитовые аналоги.
—
Обратите внимание: если мы хотели работать с базой 2 до ES6, лучшее, что мы могли сделать, - это проанализировать двоичную строку в базе (основание) 2, а затем выполнить побитовую операцию с возвращаемым значением.
0b101 // using ES6 binary literal
parseInt('101',2) // before binary literals
Конечно, бывают случаи, когда все еще бывает полезно преобразовать в / из двоичных строковых представлений.
const b2d = x => parseInt(x,2) // binary to decimal const d2b = x => x.toString(2) // decimal to binary b2d(101) // 5 d2b(5) // 101
13 вещей, которые нужно знать [и любить] о битах.
1. Поразрядный сдвиг влево `‹
<< - оператор сдвига влево. Он сдвигает число влево на указанное количество бит, отбрасывая сдвинутые биты.
0b0001 << 1 // 2 (0010) 0b0001 << 2 // 4 (0100) 0b0001 << 3 // 8 (1000)
Напомним, что для основания 10 каждый раз, когда мы перемещаем десятичный разряд влево, мы умножаем его на 10, поэтому, если мы перемещаем x цифр, мы умножаем на 10**x.
0 0 1 0 # 10 10^3 10^2 10^1 10^0 1 0 0 0 # 10 << 2 = 10 x 10^2 = 1000 10^3 10^2 10^1 10^0
Это работает для любой базы! Для основания 2 сдвиг влево x цифр влево эквивалентен умножению на 2**x.
0b0010 // 0010 = 2 0b0011 // 0011 = 3 0b0010 << 1 // 0100 = 4 0b0011 << 1 // 0110 = 6 0b0010 << 2 // 1000 = 8 0b0011 << 2 // 1100 = 12
2. Поразрядный сдвиг вправо «›› x» эквивалентен делению этажа на 2 ** x.
Если сдвиг влево на x приводит к умножению на 2**x, мы можем ожидать, что сдвиг вправо на x битов приведет к делению на 2**x, что и происходит… почти. Эта операция приводит к разделению этажа на 2**x. Округление происходит потому, что мы сдвигаем самые правые биты и отбрасываем их.
0b1001 // 1001 = 9 0b1000 // 1000 = 8 0b1001 >> 1 // 0100 = 4 = Math.floor( 9/2 ) 0b1000 >> 1 // 0100 = 4 = Math.floor( 8/2 ) 0b1001 >> 2 // 0010 = 2 = Math.floor( 9/4 ) 0b1000 >> 2 // 0010 = 2 = Math.floor( 8/4 ) 0b1001 >> 3 // 0001 = 1 = Math.floor( 9/8 ) 0b1000 >> 3 // 0001 = 1 = Math.floor( 8/8 )
3. Отключите биты с помощью `& 0`
(и оставьте остальное без изменений с помощью `& 1`)
Учитывая две двоичные цифры или биты, a и b, a AND b дает a1, если и только если оба бита оцениваются как 1. Другой способ сказать то же самое - a & 0 -> 0 и a & 1 -> a. Еще один способ: & 0 немного отключается (если он еще не отключен), а & 1 вообще ничего не делает.
a b a & b 0 0 0 // a & 0 = 0 0 1 0 // a & 1 = a 1 0 0 // a & 0 = 0 1 1 1 // a & 1 = a
С Javascript мы работаем не с отдельными битами, а с 32 битами за раз, и наша забота заключается в том, чтобы отключить некоторые биты, оставив другие в покое. С этой целью мы можем определить еще одно 32-битное число, называемое маской, так что для каждого бита, который мы хотим отключить, мы устанавливаем соответствующий бит в маске на 0, а все остальные биты устанавливаем на 1. Когда мы применяем маска с побитовым оператором AND, входные биты, соответствующие 0 в маске, будут отключены (& 0 выключает биты), а оставшиеся биты останутся неизменными (& 1 вообще ничего не делает).
v
101 (input)
AND 011 (mask)
-------
001 (result)
В JavaScript, используя нашу вспомогательную функцию, это выглядит так:
a = 0b101 // 101 mask = 0b011 // 011 mask 3rd bit a = a & mask // 001 turn 3rd bit off // turn ith bit off const turnOFF = (num, i) => num & ~(1 << i - 1)
4. Включите биты с помощью `| 1`
(и оставьте остальное без изменений с помощью `| 0`)
a OR b дает 1 при условии, что либо бит, a, либо b, оценивается как 1. Это ленивое удержание ворот можно выразить как a | 1 -> 1 и a | 0 -> a, и, в свою очередь, как | 1 немного включается, а | 0 ничего не делает.
a b a | b 0 0 0 // a | 0 = a 0 1 1 // a | 1 = 1 1 0 1 // a | 0 = a 1 1 1 // a | 1 = 1
Как и в случае с поразрядным AND, мы определяем 32-битную маску, чтобы включить одни биты, оставив другие без изменений. На этот раз биты маски, соответствующие входным битам, которые мы хотим включить, будут установлены на 1, а оставшиеся биты - на 0. Когда мы применяем маску с помощью оператора побитового ИЛИ, входные биты, соответствующие единицам в маске, будут включен (| 1 включает биты), а остальные биты не изменятся (| 0 ничего не делает).
v 010 (input) OR 100 (mask) ------- 110 (result)
И в JavaScript:
a = 0b010 // 010 mask = 0b100 // 100 mask 3rd bit a = a | mask // 110 turn 3rd bit on // turn ith bit on const turnON = (num, i) => num | (1 << i - 1)
5. Переверните биты с помощью `^ 1`
(и оставьте остальное без изменений с помощью `^ 0`)
a XOR b возвращает 1, если любой бит, a или b, но не оба, оценивается как 1. Таким образом, XOR «исключает» случаи, в которых операнды равны по значению, и из этого следует, что a ^ 1 -> !a и a ^ 0 -> a, или ^ 1 немного переключает, а ^ 0, как ни странно, ничего не делает. !a используется здесь для обозначения переключаемого битового значения a.
a b a ^ b 0 0 0 // a ^ 0 = a 0 1 1 // a ^ 1 = !a 1 0 1 // a ^ 0 = a 1 1 0 // a ^ 1 = !a
Теперь давайте определим 32-битную маску для переключения подмножества одного или нескольких битов, оставив остальные без изменений. Биты, которые соответствуют входным битам, которые мы хотим переключить, будут установлены в 1, а оставшиеся биты - в 0. Когда мы применяем маску с помощью побитового оператора XOR, входные биты, соответствующие 1 в маске, будут переключены, а оставшиеся биты будут переключены. останется в покое.
v
110
XOR 100 (mask)
-------
010
В Javascript:
a = 0b110 mask = 0b100 // mask 3rd bit a = a ^ mask // flip 3rd bit // flip ith bit const flip = (num, i) => num ^ (1 << i - 1)
6. Выполните небольшой запрос с помощью `& 1`
(отключив остальные биты с помощью `& 0`)
Мы знаем, что x & 1 оставляет бит x без изменений. Другими словами, состояние бита x равно x & 1. Для нескольких битов мы можем вывести состояние бита, отключив все остальные биты и наблюдая, что состояние рассматриваемого бита равно 1, только если результат ›0.
// input a = 0b101 // masks 1st_bit = 0b001 2nd_bit = 0b010 3rd_bit = 0b100 // queries a & 1st_bit > 0 // true (1st bit is on) a & 2nd_bit > 0 // false (2nd bit is off) a & 3rd_bit > 0 // true (1st bit is on)
Конечно, внутри условного выражения JavaScript мы можем опустить оператор сравнения и привести к значению true / false.
mask = 0b100
if (0b110 & mask) {
console.log('third bit is on')
}
А чтобы запросить i-й бит, сдвиг влево на i — 1 даст маску с i-м битом, установленным в 1.
// query ith bit const query = (num, i) => num & (1 << i - 1)
7. Установите «1» на место с помощью «1 ‹---------------- n-1«.
(вставьте «0» на место, переключив результат установки 1 на место.)
Очень часто бывает, что мы хотим указать n-й бит числа программно, например, чтобы переключить или установить его. Безусловно, самый простой способ сделать это - сдвигать 1 на n-1 влево, создавая маску с n-м битом, установленным в 1. Затем мы можем использовать эту маску для переключения или установки соответствующего бита.
a = 0b10001 // 00001 input mask = (1 << 4) // 10000 mask 5th bit with 1 a = a ^ mask // 10001 toggle 5th bit a = a | mask // 00001 turn 5th bit on // slide a 1 into ith place (mask ith bit to 1) const mask = (i) => (1 << i - 1) // slide a 0 into ith place (mask ith bit to 0) const mask = (i) => ~(1 << i - 1)
8. Создайте n единиц с помощью `(1 ‹( n) - 1`
Ранее мы создали маску и использовали ее для переключения и установки 5-го бита с помощью XOR и OR соответственно, но что, если мы хотим включить 5-й бит. Мы можем сделать это с помощью И, если бы у нас была битовая маска вида 01111. Мы можем использовать не побитовое, но в случае, если наш ключ тильды сломан, этот шаблон также может быть создан с помощью XOR-ing 10000 с 11111, т.е. переключить все биты. Мы знаем, как сдвинуть 1 на n-ю позицию, то есть 1 << n-1, но как создать маску с n единицами. Ответ: сдвигая 1 на позицию n+1 и вычитая 1, т.е. (1 << n) — 1. Выглядит так:
a = 0b11001 // 11001 input mask = (1 << 4) // 10000 mask 5th bit with 1 ones = (1 << 5) - 1 // 11111 generate all ones mask = mask ^ ones // 01111 inverted mask a = a & mask // 01001 turn 5th bit off!
Это работает, потому что число с основанием 2 с 1 в n-й позиции представляет десятичное число 2**(n-1), поэтому 2**(n-1)-1 - это наибольшее число, которое вы можете представить с помощью n-1 бит (потому что мы начинаем с нуля). Это число соответствует n-1 единицам!
n 2^(n-1) 2^(n-1) 2^(n-1)-1 2 2 10 01 3 4 100 011 4 8 1000 0111
9. Используйте `~ i`, чтобы перевернуть все биты, и используйте` ~ i + 1`, чтобы инвертировать число.
Дополнение до двух, которое JavaScript использовал для представления отрицательных чисел, эквивалентно переворачиванию битов и добавлению 1. Важно отличать его от побитового, а не ~i. Побитовое НЕ, также называемое дополнением или дополнением до единицы, является результатом простого переворота битов. Обратите внимание, мы могли бы использовать его в предыдущем примере, чтобы перевернуть биты в маске и сэкономить себе несколько шагов.
a = 0b11001 // 11001 input mask = ~(1 << 4) // 01111 mask 5th bit with 1 a = a & mask // 01001 turn 5th bit off!
(Хотите узнать больше о дополнении двух? Начните здесь. Поверьте мне.)
10. Установите бит, сначала очистив его с помощью `& 0`, а затем установив с помощью` | val`
Пока мы можем немного включать, выключать и переключать его, но для того, чтобы установить его на значение v, где v может быть 0 или 1, мы должны сначала сбросить бит на известное значение, 0 или 1. Если мы сбросим до 0, мы сможем установить v с помощью OR v. Если мы сбросим до 1, мы сможем установить v с помощью AND v. Либо работает. Мне нравится последнее.
// set ith bit to val
const set = (num, i, val) => {
let mask = ~(1 << i - 1) // mask ith bit
num = num & mask // reset ith to 1
val = val << i - 1 // shift val by i
num = num | val // set ith to val
}
Конечно, если мы хотим установить несколько битов, мы должны замаскировать несколько битов. Типичная задача собеседования принимает следующую форму: вам дается два 32-битных числа, N и M, и две позиции битов, i и j. Напишите метод для вставки M в N таким образом, чтобы M начиналась с бита j и заканчивалась в бите i. Сравните решение с заданной функцией выше.
const insert_m_into_n(n, m, i, j) {
// mask bits i thru j
ones = (1 << (j - i + 1)) - 1
mask = ~(ones << i - 1)
// reset bits i thru j to one
n = n & mask
// shift m by i
m = m << i - 1
// merge i thru j
return n | m
}
11. Проверьте, не является ли число нечетным с "& 1".
(нечетно, если последний бит равен 1)
Целое число является нечетным, если последний бит равен 1. Поэтому запросите его с помощью & 1. Если результат 1, то последний бит равен 1 → число нечетное. Если результат равен 0, то последний бит равен 0 → число четное.
00101011 01100010
& 00000001 & 00000001
-------- --------
00000001 00000000
В JavaScript 0 и1 являются ложными / правдивыми значениями, поэтому мы можем принудить их к true / false с помощью !
const is_even = (x) => {
return !(x & 1)
}
const is_odd = (x) => {
return !!(x & 1)
}
12. Поменяйте биты с помощью 3 XOR.
Если мы хотим поменять местами два целых числа без создания временной переменной и без оператора распространения (это обман), есть очень крутая битовая магия, которая выполнит это: три XOR. Можете пройти через это, чтобы увидеть, как это работает, но на самом деле это просто работает.
a b a b a | b | a^b | a^b | a^b | 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 1
JavaScript:
let a = 0b0011 // a = 0011 (3) let b = 0b0101 // b = 0101 (5) a = a^b // a = 0110 b = a^b // b = 0011 a = a^b // a = 0101 a.toString(2) // a = 0101 (5) b.toString(2) // b = 0011 (3)
13. Отфильтруйте набор с помощью «›› 1» и «& 1».
Одна из самых полезных вещей, которые можно сделать с битами, - это использовать их как логические значения. Настоящие логические значения в JavaScript - это не 1-битные, а 32-битные или, может быть, 64-битные. Я действительно не знаю. Но определенно не 1, а биты (то есть 1 бит), поэтому давайте использовать их. Допустим, у вас есть набор вещей. Допустим, у вас много подмножеств. Есть много способов справиться с этим. Можно дублировать данные или поддерживать словарь для каждого подмножества, где ключи сопоставляются с истинными / ложными значениями, которые представляют включение в базовый набор. Или представьте подмножества как логические массивы. Это неплохо. Вот другой способ: вы можете представить каждое подмножество как одно число, которое при выражении в базе 2, отдельные биты соответствуют элементам в наборе, где 1 представляет включение, а 0 - невключение!
i
v
set: { 'a', 'b', 'c', 'd' }
msk: 0 1 0 1
subset: { 'b', 'd' }
Затем, если мы хотим запечь подмножество. Мы можем фильтровать базовый набор, многократно сдвигая и проверяя включение первого бита с помощью >> 1 и & 1. Напомним, что & 1 используется для запроса первого бита, а >> 1 сдвигает первый бит, перемещая второй бит в первую позицию. Это побитовый эквивалент итерации по массиву. биты не индексируются, поэтому мы не можем увеличивать указатель. Мы могли бы сдвинуть бит маски влево и запросить каждый бит по очереди, но проще постепенно сдвигать биты и продолжать запрашивать только первый бит.
i = set.length - 1
subset = new Set()
while (msk > 0) {
if (msk & 1) subset.add(set[i])
msk >> 1
i -= 1
}
использованная литература
- Https://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesXOR
- Https://bits.stephan-brumme.com/
- Http://aggregate.org/MAGIC/
—
Спасибо, приветствуем любое / все обсуждение в комментариях. С удовольствием напишу следующий пост, если есть интерес ...
