An operation

background

Why do we do JS bits?

  • Because RECENTLY I am learning hash algorithm, which uses a lot of bit operation

  • In addition, the Internet also found a lot of information, but most of the more one-sided, did not explain the processing of special circumstances, for several groups of data calculation results will be wrong.

Back to an integer

ECMAScript integers have two types, namely:

  • Signed integers (positive and negative numbers allowed)
  • What does it mean that in ECMAScript all integer literals are signed integers by default?

The signed integer uses the 31st bit to represent the value of the integer, the 32nd bit to represent the symbol of the integer, 0 for a positive number and 1 for a negative number.

The value ranges from -2147483647 to 2147483647.

The bitwise operation limits the binary number to 32 bits, and anything beyond that is discarded

Debugging a few common methods of bit operation

toString(2)

Convert to a base 2 string

var a = 1732584193; a.toString(2); / / 1100111010001010010001100000001Copy the code

parseInt(‘11001’, 2)

Converts a 2-base string to a 10-base number

parseInt('11001'. 2) / / 25Copy the code

padStart(32, ‘0’)

The total length of the string

'1100000001'.padStart(32, 0) // 00000000000000000000001100000001
Copy the code

Source code, inverse code, complement

The source code

A binary number converted from a number to a sign bit on the leftmost, 1 negative, 0 positive

5 source code: 0101-10 source code: 11010Copy the code

Radix-minus-one complement

The inverse of a positive number is the same as its original code

The inverse of a negative number takes all bits except the sign bit

5 source code: 0101 inverse: 0101-10 source code: 11010 inverse: 10101Copy the code

complement

The complement of a positive integer is the same as the source

The complement of a negative integer takes the inverse +1

5 source code: 0101 complement: 0101-10 source code: 11010 complement: 10110Copy the code

Ok, let’s get down to business

An operator

  • Not (~)
  • And (&)
  • Or (|)
  • Xor (^)
  • Move left with sign (<<)
  • Move right with sign (>>)
  • Unsigned right shift (>>>)

Bitwise operators: not (~)

Operation steps:

  1. Take the number negative
  2. Then minus 1
~ / / 25-26Copy the code

Process:

  • Minus 25: -25
  • Minus 1: – 26
~1  // -2
~-1 // 0
~100 // -101
~-100 // 99
Copy the code

Bitwise operators: and (&)

Operation steps:

  1. Convert two numbers to 2-base complement
  2. Compare the same position (both 1, result 1, otherwise 0)
  3. If the result is negative, you have to do the complement

If the number of digits is insufficient, 0 is added to the left of the positive number and 1 is added to the negative number

Is operation

10 &3 // 2Copy the code

Process:

  • 10 complement: 1010
  • 3 Complement: 0011
  • Result: 0010, that is 2

Positive and negative operations (1)

14 &-13 // 2Copy the code

Process:

  • 14 Complement: 01110 (complement one sign bit)
  • -13 source code: 11101, complement: 10011
  • And operation: 00010, that is, 2

Positive and negative operations (2)

88 & -19 // 72
Copy the code

Process:

  • 88 complement: 01011000 (complement one sign bit)
  • -19 source: 110011, complement: 101100
  • 01011000 & 101100
  • Negative number (101100) not enough digits, the left side of the 1, 11101100
  • So 01011000 and 11101100
  • The result is: 01001000, that is: 72

Two negative operation

-12&-5 // -16Copy the code

Process:

  • -12 Complement: 10100
  • -5 Complement code: 11011
  • And operation: 10000
  • If the result is negative, take the complement again: 110000: -16

practice

3 & 7
-21 & 16
-271733879 & -1732584194
1125899778533470 & 812930
20 & 0xF
48192342 & 0xFFFF
Copy the code

Operator: or (|)

Operation steps:

  1. Convert two numbers to 2-base complement
  2. Compare the same position (if one is 1, the result is 1)
  3. If the result is negative, you have to do the complement

Is operation

10 | 3 / / 11Copy the code

Process:

  • 10 source code: 1010
  • 3 source code: 0011
  • Result: 1011, that is 11

Plus or minus operation

10 | - 3 / / - 1Copy the code

Process:

  • 10 Complement: 01010
  • -3 Complement: 11101
  • Or operation: 11111
  • If the result is negative, pick code: 10001, namely: -1

Two negative operation

- 15 | - 21 / / - 5Copy the code

Process:

  • -15 Complement: 110001
  • -21 Complement: 101011
  • Or operation: 111011
  • If the result is negative, take the complement code: 10101, namely: -5

practice

15 20 and 40 | | | 1732584193-14-271733879 (1732584194) - 271733879 & - | (~ - 271733879 & 271733878)Copy the code

Bitwise operators: xor (^)

Operation steps:

  1. Convert two numbers to 2-base complement
  2. Compare the same position (must be 0 and 1 or 1 and 0 to get 1)
  3. If it’s negative, take the complement

Is is xor

10 ^ 3 // 9
Copy the code

Process:

  • 10 complement: 1010
  • 3 Complement: 0011
  • Result: 1001, or 9

The positive and negative xor

10 to the minus 3 // minus 9Copy the code

Process:

  • 10 Complement: 01010
  • -3 Complement: 11101
  • Xor operation: 10111
  • If the result is negative, take the complement code: 11001, namely -9

Two negative xor

Minus 10 to the minus 3 // 11Copy the code

Process:

  • -10 Complement: 10110
  • -3 Complement: 11101
  • Xor operation: 01011, i.e. : 11

practice

5 ^ 8-10 ^ 9-13 ^ -20-271733879 ^ -1732584194 ^ 271733878Copy the code

Bitwise operators: signed left shift (<<)

Operation steps:

  1. Convert numbers to 2-base complement
  2. Move the specified number of digits to the left, and add 0 to the right
  3. If the result is not negative, take the complement

The part that exceeds 32 bits is discarded

Positive shift to the left

1 << 2 // Complement: 00000001 Moves 2 bits to the left, that is 00000100, resulting in: 4 5 << 3 // Complement: 00000101 moves 3 bits to the left, that is 00101000, resulting in: 40Copy the code

You can see that the positive numbers shifted to the left, that a << n, is actually a times 2 to the NTH power

Negative shift to the left

- 3 < < 4Copy the code
  • -3 Complement: 101
  • Four to the left 1010000
  • If the flag bit is negative, take the complement code: 1110000, namely -48
-6 << 3 // 1010 << 3 equals 1010000, take the complement code, 1110000 is: -48-11 << 4 // 10101 << 4 equals 101010000, take the complement code, 110110000 is: -176Copy the code

Edge cases

Case 1: Positive numbers become negative

1732584193 << 2  // -1659597820
Copy the code

The calculation process

  • 1732584193 converted to hexadecimal source code: 1100111010001010010001100000001 (31)
  • Left two, two 0:11 0011101000101001000110000000100 (33)
  • Remove the left spare one: 10011101000101001000110000000100 (32)
  • Becomes negative, complement: 11100010111010110111001111111100
  • Namely: – 1659597820

Case 2: Negative becomes positive

-1732584193 << 2  // 1659597820
Copy the code

The calculation process

  • – 1732584193 into 2 base: 11100111010001010010001100000001 (32)
  • Negative, complement: 10011000101110101101110011111111 (32)
  • Left two: 1001100010111010110111001111111100 (34)
  • Spare parts to abandon: 01100010111010110111001111111100 (32)
  • If the sign bit is positive, there is no need to add the code, that is, 1659597820

practice

1 << 32 
1 << 33 
1 << 40
2147483648 << 2
1732584193 << 6
Copy the code

Bitwise operators: signed shift right (>>)

Operation steps:

  1. Take the numeric binary complement
  2. Move the specified digit right, and the left complement corresponds to the sign bit
  3. Redundant bits are discarded
  4. If the result is negative, take the complement

Positive moves to the right

5 >> 1 // 0101 move right 1 bit 0010, that is 2 1 >> 2 // 0001 move right 1 bit 0000, that is 0Copy the code

It is easy to move a positive number to the right. The content removed can be discarded directly, and the left side can be supplemented with 0

Negative moves to the right

-5 >> 2 // -2
Copy the code

Analysis:

  • -5 Complement: 1011
  • Move 2 places to the right: 1110
  • If the result is negative, take the complement code: 1010, namely -2

practice

5 + 64 >> 9
1732584193 >> 4
Copy the code

Bitwise operators: Unsigned right shift (>>>)

Operation steps:

  1. Convert numbers to 32 – bit 2 – base complement
  2. Moves the specified bit right, along with the sign bit
  3. Bits moved to the right are discarded and the left side is filled with zeros

Because the sign bit is zero, it’s always positive

Positive moves to the right

>> and >>> are the same in positive numbers

5 >>> 2 // 101:001 5 >>> 2 // 101:001Copy the code

Negative moves to the right

-5 >>> 2 // 1073741822
Copy the code

Process:

  • -5 source code: 10000000 00000000 00000000 00000101
  • Complement: 11111111 11111111 11111111 11111011
  • Move two to the right: 00111111 11111111 11111111 11111110
  • The value is 1073741822 when converted to decimal notation

Question: Why does this fill 32 bits when none of the previous operations did?

Because in the previous operation, positive numbers complement 0, while negative numbers complement 1, but after calculation, the number of complementary bits does not affect the final calculation

And if you move to the right unsigned, it affects the operation. So you have to complete it

practice

-23 >>> 2
45678765 >>> 31
Copy the code

About the core idea of bit operation

  • We take the complement before we do the operation
  • The operation results in a negative number. Take the complement again

The above content is collected by myself and tried many times.

Because many articles on the Internet are wrong in the way of calculation, although the examples given are no problem, but several groups of numbers are wrong.

This article is sorted out, and we learn together