Поразрядные операции

Поразрядные операции выполняются над отдельными разрядами или битами чисел. Данные операции производятся только над целыми числами. Но сначала вкратце рассмотрим, что представляют собой разряды чисел.

Двоичное представление чисел

На уровне компьютера все данные представлены в виде набора бит. Каждый бит может иметь два значения: 1 (есть сигнал) и 0 (нет сигнала). И все данные фактически представляют набор нулей и единиц. 8 бит представляют 1 байт. Подобную систему называют двоичной.

Например, число 13 в двоичной системе будет равно 1101₂. Как мы это получили:

// перевод десятичного числа 13 в двоичную систему
13 / 2 = 6      // остаток 1 (13 - 6 *2 = 1)
6 / 2 = 3      // остаток 0 (6 - 3 *2 = 0)
3 / 2 = 1      // остаток 1 (3 - 1 *2 = 1)
1 / 2 = 0      // остаток 1 (1 - 0 *2 = 1)

Общий алгоритм состоит в последовательном делении числа и результатов деления на 2 и получение остатков, пока не дойдем до 0. Затем выстраиваем остатки в линию в обратном порядке и таким образом формируем двоичное представление числа. Конкретно в данном случае по шагам:

1. Делим число 13 на 2. Результат деления - 6, остаток от деления - 1 (так как 13 - 6 *2 = 1)

2. Далее делим результат предыдущей операции деления - число 6 на 2. Результат деления - 3, остаток от деления - 0

3. Делим результат предыдущей операции деления - число 3 на 2. Результат деления - 1, остаток от деления - 1

4. Делим результат предыдущей операции деления - число 1 на 2. Результат деления - 0, остаток от деления - 1

5. Последний результат деления равен 0, поэтому завершаем процесс и выстраиваем остатки от операций делений, начиная с последнего - 1101

При обратном переводе из двоичной системы в десятичную умножаем значение каждого бита (1 или 0) на число 2 в степени, равной номеру бита (нумерация битов идет от нуля):

// перевод двоичного числа 1101 в десятичную систему
1(3-й бит)1(2-й бит)0(1-й бит)1(0-й бит)
1 * 23 + 1 * 22 + 0 * 21 + 1 * 20
=
1 * 8 + 1 * 4 + 0 * 2 + 1 * 1
=
8 + 4 + 0 + 1 
=
13

В JavaScript для определения чисел в двоичном формате перед числом применяется префикс 0b:

const num = 0b1101;  // 13 в десятичной системе
console.log(num);	// 13 

Представление отрицательных чисел

Для записи чисел со знаком в JavaScript применяется дополнительный код (two's complement), при котором старший разряд является знаковым. Если его значение равно 0, то число положительное, и его двоичное представление не отличается от представления беззнакового числа. Например, 0000 0001 в десятичной системе 1.

Если старший разряд равен 1, то мы имеем дело с отрицательным числом. Например, 1111 1111 в десятичной системе представляет -1. Соответственно, 1111 0011 представляет -13.

Чтобы получить из положительного числа отрицательное, его нужно инвертировать и прибавить единицу:

Например, получим число -3. Для этого сначала возьмем двоичное представление числа 3:

310 = 0000 00112 

Инвертируем биты

~0000 0011 = 1111 1100

И прибавим 1

1111 1100 + 1 = 1111 1101

Таким образом, число 1111 1101 является двоичным представлением числа -3.

Рассмотрим, как будет идти сложение числа со знаком и без знака. Например, сложим 12 и -8:

1210 = 000011002
+
-810 = 111110002 (8 - 00001000, после инверсии - 11110111, после +1 = 11111000)
=
410 = 000001002

Мы видим, что в двоичной системе получилось число 00000100₂ или 4₁₀ в десятичной системе.

Мы можем это увидеть на практике:

let num = 0b1100;     // 12 в десятичной системе
num = ~num;         // инверсия разрядов
num = num + 1;
console.log(num);	// -12

Операции сдвига

Каждое целое число в памяти представлено в виде определенного количества разрядов. И операции сдвига позволяют сдвинуть битовое представление числа на несколько разрядов вправо или влево. Операции сдвига применяются только к целочисленным операндам. Есть две операции:

• << (сдвиг влево)

  Сдвигает битовое представление числа, представленного первым операндом, влево на определенное количество разрядов, которое задается вторым операндом.

  const res = 2 << 2;			// 10  на два разрядов влево = 1000 - 8
  console.log(res);      // 8
  

  Число 2 в двоичном представлении 00102. Если сдвинуть число 0010 на два разряда влево, то получится 1000, что в десятичной системе равно число 8.

• >> (арифметический сдвиг вправо)

  Сдвигает битовое представление числа вправо на определенное количество разрядов.

  const res = 16 >> 3;  // 10000 на три разряда вправо = 10 или 2 в десятичной системе
  console.log(res);           // 2
  

  Число 16 в двоичном представлении 100002. Если сдвинуть число 10000 на три разряда вправо (три последних разряда отбрасываются), то получится 00010, что в десятичной системе представляет число 2.

  Стоит отметить, что это так называемый арифметический сдвиг, при котором сдвинутые влевой части разряды заполняются знаковым битом - 0 для положительных и 1 для отрицательных чисел. Таким образом, при сдвиге отрицательных чисел не будет опасения, что после сдвига они станут положительными. Например:

  const res = -16 >> 3;  // 11111110000 на три разряда вправо = 1111111111111110
  console.log(res);      // -2
  

  Так, при сдвиге вправо -16 на 3 разряда мы получим -2, что вполне естественно.

• >>> (логический сдвиг вправо)

  Сдвигает битовое представление числа вправо на определенное количество разрядов, но в отличие от операции >> заполняет сдвинутые в левой части разряды нулями, то есть мы получаем беззнаковый сдвиг. Таким образом, даже если мы сдвигаем отрицательное число, на выходе мы в любом случае получим положительное:

  const res = -16 >>> 3; 
  console.log(res);      // 536870910
  

Можно заметить, что сдвиг на один разряд влево фактически аналогично умножению на 2, тогда как сдвиг вправо на один раз эквивалентно делению на два. Мы можем обобщить: сдвиг влево на n аналогичен умножению числа на 2n, а сдвиг вправо на n разрядов аналогичен делению на 2n, что можно использовать вместо умножения/деления на степени двойки:

const res1 = 8 << 2;  // эквивалентно 8 * 4
console.log(res1);      // 32

const res2 = 64 >> 4;  // эквивалентно 64 / 16
console.log(res2);      // 4

Поразрядные операции

Поразрядные операции также проводятся только над соответствующими разрядами чисел:

• &: поразрядная конъюнкция (операция И или поразрядное умножение). Возвращает 1, если оба из соответствующих разрядов обоих чисел равны 1

• |: поразрядная дизъюнкция (операция ИЛИ или поразрядное сложение). Возвращает 1, если хотя бы один из соответствующих разрядов обоих чисел равен 1

• ^: поразрядное исключающее ИЛИ. Возвращает 1, если только один из соответствующих разрядов обоих чисел равен 1

• ~: поразрядное отрицание или инверсия. Инвертирует все разряды операнда. Если разряд равен 1, то он становится равен 0, а если он равен 0, то он получает значение 1.

Применение операций:

const a = 5 | 2;			// 101 | 010 = 111  - 7
const b = 6 & 2;			// 110 & 010 = 10  - 2
const c = 5 ^ 2;			// 101 ^ 010 = 111 - 7
const d = ~9;				// -10

Например, выражение 5 | 2 равно 7. Число 5 в двоичной записи равно 101, а число 2 - 10 или 010. Сложим соответствующие разряды обоих чисел. При сложении если хотя бы один разряд равен 1, то сумма обоих разрядов равна 1. Поэтому получаем:

1	0	1
0	1	0
1	1	1

В итоге получаем число 111, что в десятичной записи представляет число 7.

Возьмем другое выражение 6 & 2. Число 6 в двоичной записи равно 110, а число 2 - 10 или 010. Умножим соответствующие разряды обоих чисел. Произведение обоих разрядов равно 1, если оба этих разряда равны 1. Иначе произведение равно 0. Поэтому получаем:

1	1	0
0	1	0
0	1	0

Получаем число 010, что в десятичной системе равно 2.