Bitwise operators

Lecture




  1. 32-bit signed integer format
  2. List of operators
  3. Operators Job Description
    1. & (bitwise AND)
    2. | (Bitwise OR)
    3. ^ (Exclusive OR)
    4. ~ (Bitwise NOT)
    5. Bit shift operators
      1. << (Left shift)
      2. >> (Right shift carrying sign)
      3. >>> (Right shift with padding with zeros)
  4. The use of bitwise operators
    1. Mask
    2. Binary numbers in javascript
    3. Access check
    4. Masks in functions
    5. Rounding
    6. Check on -1
    7. Multiplication and division by degrees 2
  5. Total

Bitwise operators interpret operands as a sequence of 32 bits (zeros and ones). They perform operations using the binary representation of a number, and return a new sequence of 32 bits (a number) as a result.

This chapter is complex, requires additional programming knowledge and is not very important, you can skip it.

32-bit signed integer format

Bitwise operators in JavaScript work with 32-bit integers in their binary representation.

This representation is called “A 32-bit integer with a sign, the most significant bit on the left, and a complement of two”.

Let us analyze how the numbers inside are arranged in more detail; it is necessary to know this for bit operations with them.

  • I hope that you already know what binary number system is. When parsing bitwise operations, we will discuss precisely the binary representation of numbers, out of 32 bits.
  • The most significant bit on the left is the scientific name for the most common way to write numbers (from the highest order to the next). In this case, if the higher bit is absent, then the corresponding bit is zero.

    Examples of representing numbers in binary:

    1 a = 0; // 00000000000000000000000000000000
    2 a = 1; // 00000000000000000000000000000001
    3 a = 2; // 00000000000000000000000000000010
    4 a = 3; // 00000000000000000000000000000011
    5 a = 255; // 00000000000000000000000011111111

    Note that each number consists of exactly 32 bits.

    Low bit left

    Despite the fact that this way of writing numbers seems to us to be not quite usual, there are languages ​​and technologies that use the way to write the “low bit to the left,” when the bits are written the other way around, from the least bit to the most.

    That is why the EcmaScript specification explicitly says "most significant bit to the left."

  • Addition to two is the name of the method of supporting negative numbers.

    The binary form of the inverse of a given number (for example, 5 and -5 ) is obtained by inverting all bits with the addition of 1.

    That is, zeros are replaced by ones, units - by zeros and 1 added to the number. It turns out the internal representation of the same number, but with a minus sign.

    For example, here's the number 314 :

    00000000000000000000000100111010

    To get -314 , the first step is to reverse the bits of the number: replace 0 with 1 , and 1 with 0 :

    11111111111111111111111011000101

    The second step is to add a one to the received binary number, the usual binary addition: 11111111111111111111111011000101 + 1 = 11111111111111111111111011000110 .

    So we got:

    -314 = 11111111111111111111111011000110

    The complement to two principle divides all binary representations into two sets: if the leftmost bit is 0 , the number is positive, if 1 , the number is negative. Therefore, this bit is called a sign bit .

List of operators

The following table lists all bitwise operators.
Next, the operators are parsed in more detail.

Operator Using Description
Bitwise AND (AND) a & b Puts 1 on the result bit, for which the corresponding bits of the operands are 1.
Bitwise OR (OR) a | b Puts 1 on the result bit, for which at least one of the corresponding bits of the operands is 1.
Bitwise exclusive OR (XOR) a ^ b Puts 1 on the result bit, for which only one of the corresponding bits of the operands is 1 (but not both).
Bitwise NOT (NOT) ~a Replaces every bit of operand with the opposite.
Left shift a << b Shifts the binary representation of a by b bits to the left, adding zeros to the right.
Right shift carrying sign a >> b Shifts the binary representation of a by b bits to the right, discarding the shifted bits.
Right shift with zero padding a >>> b Shifts the binary representation of a by b bits to the right, discarding the shifted bits and adding zeros to the left.

Operators Job Description

Bitwise operators work like this:

  1. Operands are converted to 32-bit integers, represented by a sequence of bits. The fractional part, if any, is discarded.
  2. For binary operators, each bit in the first operand is considered together with the corresponding bit of the second operand: the first bit with the first, the second with the second, and so on. An operator is applied to each pair of bits, giving the corresponding bit of the result.
  3. The resulting bit sequence is interpreted as a normal number.

Let's see how the operators work, with examples.

& (bitwise AND)

Performs an AND operation on each pair of bits.

The result of a & b is equal to one only when both bits a and b are equal to one.

Truth Table for & :

a b a & b
0 0 0
0 1 0
1 0 0
1 1 1

Example:

1 9 (по осн. 10)
2    = 00000000000000000000000000001001 (по осн. 2)
3 14 (по осн. 10)
4    = 00000000000000000000000000001110 (по осн. 2)
5                     --------------------------------
6 14 & 9 (по осн. 10)
7    = 00000000000000000000000000001000 (по осн. 2)
8    = 8 (по осн. 10)

| (Bitwise OR)

Performs an OR operation on each pair of bits. Result a | b a | b is 1 if at least one bit from a,b is 1.

Truth Table for | :

a b a | b
0 0 0
0 1 1
1 0 1
1 1 1

Example:

1 9 (по осн. 10)
2    = 00000000000000000000000000001001 (по осн. 2)
3 14 (по осн. 10)
4    = 00000000000000000000000000001110 (по осн. 2)
5                     --------------------------------
6 14 | 9 (по осн. 10)
7    = 00000000000000000000000000001111 (по осн. 2)
8    = 15 (по осн. 10)

^ (Exclusive OR)

Performs an “exclusive OR” operation on each pair of bits.

a Exclusive OR b is 1 if only a=1 or only b=1 , but not both at the same time a=b=1 .

Truth Table for XOR:

a b a ^ b
0 0 0
0 1 1
1 0 1
1 1 0

As you can see, it gives 1, if it is either on the left 1 , or on the right 1 , but not simultaneously. Therefore, it is called the "exclusive OR".

Example:

1 9 (по осн. 10)
2    = 00000000000000000000000000001001 (по осн. 2)
3 14 (по осн. 10)
4    = 00000000000000000000000000001110 (по осн. 2)
5                     --------------------------------
6 14 ^ 9 (по осн. 10)
7    = 00000000000000000000000000000111 (по осн. 2)
8    = 7 (по осн. 10)

Exclusive OR Encryption

Exclusive or can be used for encryption, since this operation is completely reversible. The double use of the exclusive OR with the same argument gives the original number.

In other words, the formula is true: a ^ b ^ b == a .

Let Vasya wants to transfer to Petya secret information data . This information is pre-converted into a number; for example, a string is interpreted as a sequence of character codes.

Vasya and Peter agree in advance on the numeric key encryption key .

Algorithm:

  • Vasya takes a binary representation of data and makes a data ^ key operation. If necessary, data beats into parts equal in length to the key , so that one can conduct a bitwise OR ^ along the entire length. JavaScript allows you to do ^ operation with 32-bit integers, so data needs to be broken down into a sequence of such numbers.
  • The result of the data ^ key sent to Petya, this is encryption.

For example, suppose in data next number is 9 , and the key key is 1220461917 .

Данные: 9 в двоичном виде
00000000000000000000000000001001
Ключ: 1220461917 в двоичном виде
01001000101111101100010101011101
Результат операции 9 ^ key:
01001000101111101100010101010100
Результат в 10-ной системе (шифровка):
1220461908

  • Peter, having received the next encryption number 1220461908 , applies the same ^ key operation to it.
  • The result will be the original number data .

In our case:

Полученная шифровка в двоичной системе:
9 ^ key = 1220461908
01001000101111101100010101010100
Ключ: 1220461917 в двоичном виде:
01001000101111101100010101011101
Результат операции 1220461917 ^ key:
00000000000000000000000000001001
Результат в 10-ной системе (исходное сообщение):
9

Of course, such encryption is susceptible to frequency analysis and other decryption methods, so modern algorithms use XOR as one of the important parts of a more complex multi-step scheme.

~ (Bitwise NOT)

Performs an operation NOT on each bit, replacing it with the opposite one.

Truth table for NOT:

a ~a
0 1
1 0

Example:

1 9 (по осн. 10)
2    = 00000000000000000000000000001001 (по осн. 2)
3                 --------------------------------
4 ~9 (по осн. 10)
5    = 11111111111111111111111111110110 (по осн. 2)
6    = -10 (по осн. 10)

Because of the internal representation of negative numbers, it turns out that ~n == -(n+1) .

For example:

1 alert(~3); // -4
2 alert(~-1); // 0

Bit shift operators

Bit shift operators take two operands. The first is the number to shift, and the second is the number of bits that need to be shifted in the first operand.

The direction of the shift is the same as the direction of the arrows in the operator.

<< (Left shift)

This operator shifts the first operand a specified number of bits to the left. Extra bits are discarded, zero bits are added to the right.

For example, 9 << 2 will give 36 :

1 9 (по осн.10)
2    = 00000000000000000000000000001001 (по осн.2)
3                    --------------------------------
4 9 << 2 (по осн.10)
5    = 00000000000000000000000000100100 (по осн.2)
6    = 36 (по осн.10)

>> (Right shift carrying sign)

This operator shifts the bits to the right, discarding the extra ones. Copies of the left-most bit are added to the left. Since the final left-most bit has the same meaning as the original bit, the sign of the number (represented by the left-most bit) does not change.

Therefore, it is called "carrying the sign."

For example, 9 >> 2 will give 2 :

1 9 (по осн.10)
2    = 00000000000000000000000000001001 (по осн.2)
3                    --------------------------------
4 9 >> 2 (по осн.10)
5    = 00000000000000000000000000000010 (по осн.2)
6    = 2 (по осн.10)

Similarly, -9 >> 2 will give -3 , since the sign is saved:

1 -9 (по осн.10)
2    = 11111111111111111111111111110111 (по осн.2)
3                     --------------------------------
4 -9 >> 2 (по осн.10)
5    = 11111111111111111111111111111101 (по осн.2) = -3 (по осн.10)

>>> (Right shift with padding with zeros)

This operator shifts the bits of the first operand to the right. Extra bits on the right are discarded. Zero bits are added to the left.

The sign bit becomes 0, so the result is always positive.
For non-negative numbers, the right shift with filling with zeros and the right shift with transfer of the sign will give the same result, because in both cases, zeros will be added to the left.

For negative numbers - the result of the work is different. For example, -9 >>> 2 will give 1073741821 , in contrast to -9 >> 2 (gives -3 ):

1 -9 (по осн.10)
2    = 11111111111111111111111111110111 (по осн.2)
3                      --------------------------------
4 -9 >>> 2 (по осн.10)
5    = 00111111111111111111111111111101 (по осн.2)
6    = 1073741821 (по осн.10)

The use of bitwise operators

Bitwise operators are rarely used, but still used.

The use cases of bitwise operators, which we will examine here, make up the majority of all uses in JavaScript.

Careful priorities!

In JavaScript, the bitwise operators ^ , & , | are performed after comparisons == .

For example, in comparing a == b^0 , a comparison of a == b^0 will be performed first, and then an operation ^0 , as if brackets are (a == b)^0 .

Usually this is not what we want. To guarantee the desired order, you need to put brackets: a == (b^0) .

Mask

For this example, imagine that our script works with users:

  • Гость
  • Редактор
  • Админ

Each of them has a number of accesses that can be tabulated:

User View articles Change of articles View products Change of goods General administration
a guest Yes Not Yes Not Not
Editor Yes Yes Yes Yes Not
Admin Yes Yes Yes Yes Yes

If instead of "Yes" put 1 , and instead of "No" - 0 , then each set of accesses is described by a number:

User View articles Change of articles View products Change of goods General administration In decimal
a guest one 0 one 0 0 = 20
Editor one one one one 0 = 30
Admin one one one one one = 31

We have packed a lot of information into one number. It saves memory. But, besides this, it is very easy to check by it whether a visitor has a given combination of accesses .

To do this, let's see how in the 2-nd system each access is represented separately.

  • Access corresponding to general administration only: 00001 (=1) (all zeros except 1 in the position corresponding to this access).
  • Access corresponding only to changing products: 00010 (=2) .
  • Access matching only product view: 00100 (=4) .
  • Access matching only article changes: 01000 (=8) .
  • Access corresponding to viewing articles only: 10000 (=16) .

For example, viewing and editing articles will allow access access = 11000 .

As a rule, accesses are specified as constants:

1 var ACCESS_ADMIN = 1; // 00001
2 var ACCESS_GOODS_CHANGE = 2; // 00010
3 var ACCESS_GOODS_VIEW = 4; // 00100
4 var ACCESS_ARTICLE_CHANGE = 8; // 01000
5 var ACCESS_ARTICLE_VIEW = 16; // 10000

From these constants, the desired combination of accesses can be obtained using the operation | .

var access = ACCESS_ARTICLE_VIEW | ACCESS_ARTICLE_CHANGE; access = ACCESS_ARTICLE_VIEW | ACCESS_ARTICLE_CHANGE; // 11000

Binary numbers in javascript

For convenient work with examples in this article, two functions will be useful.

  • parseInt("11000", 2) - translates the string with the binary number in the number.
  • n.toString(2) - gets for the number n entry in the 2nd system as a string.

For example:

1 var access = parseInt( "11000" , 2); // получаем число из строки
2
3 alert(access); // 24, число с таким 2-ным представлением
4
5 var access2 = access.toString(2); // обратно двоичную строку из числа
6
7 alert(access2); // 11000

Access check

In order to understand whether access necessary access, for example, the right of administration, it is enough to apply the bitwise AND operator ( & ) to it with the appropriate mask.

For example, let's create a series of accesses and check them:

1 var access = parseInt( "11111" , 2); // 31, все 1 означает, что доступ полный
2
3 alert(access & ACCESS_ADMIN); // если результат не 0, то есть доступ ACCESS_ADMIN

And now the same check for a visitor with other rights:

1 var access = parseInt( "10100" ); // 20, нет 1 в конце
2
3 alert(access & ACCESS_ADMIN); // 0, нет доступа к общему администрированию

Such a check works, because the AND operator puts 1 on those positions of the result, where 1 is in both operands.

So access & 1 for any number of access will set all bits to zero, except the rightmost one. And the rightmost one will become 1 only if it is equal to 1 in access .

For completeness, we will also check whether access 11111 gives the right to change the goods. To do this, apply the AND ( & ) operator with 00010 (= 2 in the 10th system) to the access. **

1 var adminAccess = 31; // 111 1 1
2
3 alert(adminAccess & ACCESS_GOODS_CHANGE); // не 0, есть доступ к изменению товаров

You can check one of several accesses.

For example, check if there are rights to view or change products. The corresponding rights are set by bit 1 in the second and third place from the end, which gives the number 00110 (= 6 in the 10th system).

1 var check = ACCESS_GOODS_VIEW | ACCESS_GOODS_CHANGE; check = ACCESS_GOODS_VIEW | ACCESS_GOODS_CHANGE; // 6, 00110
2
3 var access = 30; // 11 11 0;
4
5 alert(access & check); // не 0, значит есть доступ к просмотру ИЛИ изменению
6
7 access = parseInt( "11100" , 2);
8
9 alert(access & check); // не 0, есть доступ к просмотру ИЛИ изменению

As can be seen from the example above, if the check argument is OR from several ACCESS_* accesses, then the test result will tell if there is at least one of them. And what - you need to watch a separate test, if it is important.

So, the mask makes it possible to conveniently “pack” many bit values ​​into one number with the help of OR | and also, using the AND operator ( & ), to check the mask for the combination of bits set.

Masks in functions

Often masks are used in functions to transfer several "flags" in one parameter, i.e. single bit values.

For example:

// найти пользователей с правами на изменение товаров или администраторов
findUsers(ACCESS_GOODS_CHANGE | ACCESS_ADMIN);

Rounding

Since bit operations discard the decimal part, they can be used for rounding. It is enough to take any operation that does not change the value of the number.

For example, double NOT ( ~ ):

1 alert( ~~12.345 ); // 12

An exclusive OR ( ^ ) with zero is also appropriate:

1 alert( 12.345^0 ); // 12

The latter is even more convenient, since it reads well:

1 alert( 12.3 * 14.5 ^ 0); // (=178) "12.3 умножить на 14.5 и округлить "

Bitwise operators have a low enough priority, it is less than the rest of the arithmetic:

1 alert( 1.1 + 1.2 ^ 0 ); // 2, сложение выполнится раньше округления

Check on -1

The internal format of numbers is designed so that to change the character you need to replace all the bits with the opposite (“draw”) and add 1 .

Bit inversion is bitwise NOT ( ~ ). That is, with this format, the representation of the number -n = ~n + 1 . Or, if you move the unit: ~n = -(n+1) .

As can be seen from the last equation, ~n == 0 only if n == -1 . Therefore, you can easily check the equality n == -1 :

1 var n = 5;
2
3 if (~n) { // сработает, т.к. ~n = -(5+1) = -6 // сработает, т.к. ~n = -(5+1) = -6
4    alert( "n не -1" ); // выведет!
5 }

1 var n = -1;
2
3 if (~n) { // не сработает, т.к. ~n = -(-1+1) = 0 // не сработает, т.к. ~n = -(-1+1) = 0
4    alert( "...ничего не выведет..." );
5 }

A check of -1 useful, for example, when searching for a character in a string. A call to str.indexOf("подстрока") returns the position of the substring to str , or -1 if not found.

1 var str = "Проверка" ;
2
3 if (~str.indexOf( "верка" )) { // Сочетание "if (~...indexOf)" читается как "если найдено"
4    alert( 'найдено!' );
5 }

Multiplication and division by degrees 2

Operator a << b , shifting the bits, essentially multiplies a by 2 b .

For example:

1 alert( 1 << 2 ); // 1*(2*2) = 4
2 alert( 1 << 3 ); // 1*(2*2*2) = 8
3 alert( 3 << 3 ); // 3*(2*2*2) = 24

The operator a >> b , shifting the bits, produces an integer division of a by 2 b .

1 alert( 8 >> 2 ); // 2 = 8/4, убрали 2 нуля в двоичном представлении
2 alert( 11 >> 2 ); // 2, целочисленное деление (менее значимые биты просто отброшены)

Total

  • Binary bitwise operators: & | ^ << >> >>> & | ^ << >> >>> .
  • Unary bitwise operator one: ~ .

Typically, the bit representation of a number is used for:

  • Packing multiple bit values ​​("flags") into one value. This saves memory and allows you to check for a combination of flags with a single & operator. In addition, such a packed value will be for the function just one parameter, it is also convenient.
  • Number rounding: (12.34^0) = 12 .
  • Checks for equality -1 : if (~n) { n не -1 } .

Importance: 5

Why do the bitwise operations in the examples below do not change the number? What are they doing inside?

1 alert( 123 ^ 0 ); // 123
2 alert( 0 ^ 123 ); // 123
3 alert( ~~123 ); // 123

Decision
  1. The a^b operation puts the result bit in 1 if the corresponding bit position in a or b (but not simultaneously) is 1 .

    Since 0 everywhere in 0 , the bits are taken exactly as in the second argument.

  2. The first bitwise NOT ~ turns 0 into 1 , and 1 into 0 . And the second does not turn again, in the end it turns out as it was.
[Open task in new window]

Importance: 3

Write the function isInteger(num) , which returns true if num is an integer, otherwise false .

For example:

alert( isInteger(1) ); // true
alert( isInteger(1.5) ); // false
alert( isInteger(-0.5) ); // false

Decision

One of the variants of such a function:

1 function isInteger(num) {
2    return (num ^ 0) === num;
3 }
4
5 alert( isInteger(1) ); // true
6 alert( isInteger(1.5) ); // false
7 alert( isInteger(-0.5) ); // false

Note: num^0 - in brackets! This is because the priority of the operation is very low. If you do not put a bracket, then === will work before. It turns out num ^ (0 === num) , and this is quite another matter.

[Open task in new window]

Importance: 5

Is it true that for any a and b , the equalities below hold?

  • a ^ b == b ^ a
  • a & b == b & a
  • a | b == b | a

In other words, when changing places - is the result always the same?

Decision

The operation on numbers ultimately comes down to bits.

Let's see if you can swap bits left and right.

For example, a truth table for ^ :

a b result
0 0 0
0 1 1
1 0 1
1 1 0

Cases 0^0 and 1^1 will not change in the course of changing places, so we are not interested. But 0^1 and 1^0 equivalent and equal to 1 .

Similarly, you can see that other operators are symmetric.

The answer is yes .

[Open task in new window]

Importance: 5

Why is the result of alert'ов different?

1 alert( 123456789 ^ 0 ); // 123456789
2 alert( 12345678912345 ^ 0 ); // 1942903641

Decision

The result is different, because usually the number in JavaScript has a 64-bit floating point format. At the same time, part of the bits ( 52 ) are reserved for numbers, part ( 11 ) are reserved for storing the number of the position where the decimal point is located, and one bit is the sign of the number.

This means that the maximum integer that can be stored is 52 bits.

Bitwise operations convert a number to a 32-bit integer. The higher of these 52 bits will be discarded. If the number initially occupied more than 31 bits (one more bit stores not a digit, but a sign) - it will change.

Here is another example:

01 // в двоичном виде 1000000000000000000000000000000
02 alert( Math.pow(2, 30) ); // 1073741824
03 alert( Math.pow(2, 30) ^ 0 ); // 1073741824, всё ок, длины хватает
04
05 // в двоичном виде 100000000000000000000000000000000
06 alert( Math.pow(2, 32) ); // 4294967296
07 alert( Math.pow(2, 32) ^ 0 ); // 0, отброшены старшие биты!
08
09 // пограничный случай
10 // в двоичном виде 10000000000000000000000000000000
11 alert( Math.pow(2, 31) ); // 2147483648
12 alert( Math.pow(2, 31) ^ 0 ); // -2147483648, старший бит стал знаковым

[Opened

Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Scripting client side JavaScript, jqvery, BackBone

Terms: Scripting client side JavaScript, jqvery, BackBone