Битовые операции

Сводка

Битовые операции обращаются со своими операндами как с 32-х разрядными последовательностями нулей и единиц, а не как с десятичными, восьмеричными или шестнадцатиричными числами. К примеру десятичное число 9 в двоичном представлении будет выглядеть как 1001. Битовые операции производят свои преобразования именно с двоичным представлением числа, но возвращают стандартные числовые значения языка JavaScript.

Следующая таблица содержит сводные данные о битовых операциях в JavaScript:

Представление чисел (Signed 32-bit integers)

Операнды всех битовых операций конвертируются в 32-х битовые целые со знаком представленные в дополнительном коде и с использованием порядка битов от "старшего к младшему". Порядок битов "от старшего к младшему" означает, что наиболее значимый бит (бит с наибольшим значением) находится слева если 32-х разрядное число представлено в виде горизонтальной линии (шкалы). Представление в дополнительном коде  означает, что отрицательное значение числа (например 5 и -5) получается путем инвертирования числа (операция "побитовое НЕ", также известное как "обратный код") и прибавления к нему единицы.

Возьмем, к примеру, число 314. Представим его в двоичном коде:

00000000000000000000000100111010

Следующая строка представляет собой его обратный код или ~314:

11111111111111111111111011000101

Прибавив к нему единицу, мы получаем двоичное представление числа  -314, оно же 314 в дополнительном коде:

11111111111111111111111011000110

Дополнение до 2-х гарантирует нам, что у положительного числа самый левый бит равен 0, в то время как у отрицательного он равен 1. Он зовется знаковым битом.

Число 0 есть число, у которого во ввсех битовых позициях записаны нули.

Число -1 есть число, у которого во всех битовых позициях записаны единицы.

Побитовые логические операции

Побитовые логические операции работают следующим образом:

• Операнды конвертируются в 32-х битовые числа отображаемые последовательностью нулей и единиц
• Каждый бит первого операнда считается парным соотвествующему биту второго операнда. Первый бит - первому, второй второму итд.
• Операция применяется к каждой паре битов, and the result is constructed bitwise.

& (Побитовое AND)

Производит побитовое И над каждой парой битов. Операция a AND b веренет 1 если только и a и b равны 1. Таблица истинности для этой операции выглядит так:

Пример:

     9 (основание 10) = 00000000000000000000000000001001 (основание 2)
    14 (основание 10) = 00000000000000000000000000001110 (основание 2)
                   --------------------------------
14 & 9 (основание 10) = 00000000000000000000000000001000 (осн. 2) = 8 (осн. 10)

Побитовое  AND любого числа x с нулем вернет 0.

Побитовое  AND любого числа x с числом -1 вернет х.

| (Побитовое OR)

Производит побитовое ИЛИ над каждой парой битов. Операция a OR b веренет 1 если a или b равны 1. Таблица истинности для этой операции выглядит так:

Пример:
     
9 (base 10) = 00000000000000000000000000001001 (base 2)
14 (base 10) = 00000000000000000000000000001110 (base 2)
                   --------------------------------
14 | 9 (base 10) = 00000000000000000000000000001111 (base 2) = 15 (base 10)

Побитовое OR любого числа x c нулем вернет x.

Побитовое OR любого числа x с числом -1 вернет -1.

^ (Побитовое XOR)

Производит побитовое XOR над каждой парой битов. Операция a XOR b вернет 1 если a  и b различны. Таблица истинности для этой операции выглядит так:

Пример:

     9 (base 10) = 00000000000000000000000000001001 (base 2)
    14 (base 10) = 00000000000000000000000000001110 (base 2)
                   --------------------------------
14 ^ 9 (base 10) = 00000000000000000000000000000111 (base 2) = 7 (base 10)

Побитовое XOR любого числа x c нулем вернет x.

Побитовое XOR любого числа x c числом -1 вернет ~x.

~ (Побитовое NOT)

Производит операцию NOT над каждым битом. NOT a вернет побитово инвертированное значение (обратный код) операнда. Таблица истинности для этой операции выглядит так:

Пример:

 9 (base 10) = 00000000000000000000000000001001 (base 2)
               --------------------------------
~9 (base 10) = 11111111111111111111111111110110 (base 2) = -10 (base 10)

Побитовое NOT любого числа x вернет -(x + 1). Например, ~5 вернет -6.

Побитовые операции сдвига

The bitwise shift operators take two operands: the first is a quantity to be shifted, and the second specifies the number of bit positions by which the first operand is to be shifted. The direction of the shift operation is controlled by the operator used.

Shift operators convert their operands to 32-bit integers in big-endian order and return a result of the same type as the left operand.

<< (Left shift)

This operator shifts the first operand the specified number of bits to the left. Excess bits shifted off to the left are discarded. Zero bits are shifted in from the right.

For example, 9 << 2 yields 36:

     9 (base 10): 00000000000000000000000000001001 (base 2)
                  --------------------------------
9 << 2 (base 10): 00000000000000000000000000100100 (base 2) = 36 (base 10)

>> (Sign-propagating right shift)

This operator shifts the first operand the specified number of bits to the right. Excess bits shifted off to the right are discarded. Copies of the leftmost bit are shifted in from the left. Since the new leftmost bit has the same value as the previous leftmost bit, the sign bit (the leftmost bit) does not change. Hence the name "sign-propagating".

For example, 9 >> 2 yields 2:

     9 (base 10): 00000000000000000000000000001001 (base 2)
                  --------------------------------
9 >> 2 (base 10): 00000000000000000000000000000010 (base 2) = 2 (base 10)

Likewise, -9 >> 2 yields -3, because the sign is preserved:

     -9 (base 10): 11111111111111111111111111110111 (base 2)
                   --------------------------------
-9 >> 2 (base 10): 11111111111111111111111111111101 (base 2) = -3 (base 10)

>>> (Zero-fill right shift)

This operator shifts the first operand the specified number of bits to the right. Excess bits shifted off to the right are discarded. Zero bits are shifted in from the left. The sign bit becomes 0, so the result is always positive.

For non-negative numbers, zero-fill right shift and sign-propagating right shift yield the same result. For example, 9 >>> 2 yields 2, the same as 9 >> 2:

      9 (base 10): 00000000000000000000000000001001 (base 2)
                   --------------------------------
9 >>> 2 (base 10): 00000000000000000000000000000010 (base 2) = 2 (base 10)

However, this is not the case for negative numbers. For example, -9 >>> 2 yields 1073741821, which is different than -9 >> 2 (which yields -3):

      -9 (base 10): 11111111111111111111111111110111 (base 2)
                    --------------------------------
-9 >>> 2 (base 10): 00111111111111111111111111111101 (base 2) = 1073741821 (base 10)

Примеры

Example: Flags and bitmasks

The bitwise logical operators are often used to create, manipulate, and read sequences of flags, which are like binary variables. Variables could be used instead of these sequences, but binary flags take much less memory (by a factor of 32).

Suppose there are 4 flags:

• flag A: we have an ant problem
• flag B: we own a bat
• flag C: we own a cat
• flag D: we own a duck

These flags are represented by a sequence of bits: DCBA. When a flag is set, it has a value of 1. When a flag is cleared, it has a value of 0. Suppose a variable flags has the binary value 0101:

var flags = 0x5;   // binary 0101

This value indicates:

• flag A is true (we have an ant problem);
• flag B is false (we don't own a bat);
• flag C is true (we own a cat);
• flag D is false (we don't own a duck);

Since bitwise operators are 32-bit, 0101 is actually 00000000000000000000000000000101, but the preceding zeroes can be neglected since they contain no meaningful information.

A bitmask is a sequence of bits that can manipulate and/or read flags. Typically, a "primitive" bitmask for each flag is defined:

var FLAG_A = 0x1; // 0001
var FLAG_B = 0x2; // 0010
var FLAG_C = 0x4; // 0100
var FLAG_D = 0x8; // 1000

New bitmasks can be created by using the bitwise logical operators on these primitive bitmasks. For example, the bitmask 1011 can be created by ORing FLAG_A, FLAG_B, and FLAG_D:

var mask = FLAG_A | FLAG_B | FLAG_D; // 0001 | 0010 | 1000 => 1011

Individual flag values can be extracted by ANDing them with a bitmask, where each bit with the value of one will "extract" the corresponding flag. The bitmask masks out the non-relevant flags by ANDing with zeros (hence the term "bitmask"). For example, the bitmask 0100 can be used to see if flag C is set:

// if we own a cat
if (flags & FLAG_C) { // 0101 & 0100 => 0100 => true
   // do stuff
}

A bitmask with multiple set flags acts like an "either/or". For example, the following two are equivalent:

// if we own a bat or we own a cat
if ((flags & FLAG_B) || (flags & FLAG_C)) { // (0101 & 0010) || (0101 & 0100) => 0000 || 0100 => true
   // do stuff
}

// if we own a bat or cat
var mask = FLAG_B | FLAG_C; // 0010 | 0100 => 0110
if (flags & mask) { // 0101 & 0110 => 0100 => true
   // do stuff
}

Flags can be set by ORing them with a bitmask, where each bit with the value one will set the corresponding flag, if that flag isn't already set. For example, the bitmask 1010 can be used to set flags C and D:

// yes, we own a cat and a duck
var mask = FLAG_C | FLAG_D; // 0100 | 1000 => 1100
flags |= mask;   // 0101 | 1100 => 1101

Flags can be cleared by ANDing them with a bitmask, where each bit with the value zero will clear the corresponding flag, if it isn't already cleared. This bitmask can be created by NOTing primitive bitmasks. For example, the bitmask 1010 can be used to clear flags A and C:

// no, we don't neither have an ant problem nor own a cat
var mask = ~(FLAG_A | FLAG_C); // ~0101 => 1010
flags &= mask;   // 1101 & 1010 => 1000

The mask could also have been created with ~FLAG_A & ~FLAG_C (De Morgan's law):

// no, we don't have an ant problem, and we don't own a cat
var mask = ~FLAG_A & ~FLAG_C;
flags &= mask;   // 1101 & 1010 => 1000

Flags can be toggled by XORing them with a bitmask, where each bit with the value one will toggle the corresponding flag. For example, the bitmask 0110 can be used to toggle flags B and C:

// if we didn't have a bat, we have one now, and if we did have one, bye-bye bat
// same thing for cats
var mask = FLAG_B | FLAG_C;
flags = flags ^ mask;   // 1100 ^ 0110 => 1010

Finally, the flags can all be flipped with the NOT operator:

// entering parallel universe...
flags = ~flags;    // ~1010 => 0101

Совместимость с браузерами

Смотрите также

• Wikipedia Битовые операции
• Wikipedia Дополнительный код
• Wikipedia Обратный код
• Логические операции