The previous article introduced the IEEE-754 standard for floating-point storage and explained in detail why 0.1 + 0.2 is not equal to 0.3. This article continues as a companion article to talk about binary operators in JS.

Review of Basic Knowledge

In introducing the IEEF-754 standard, we learned that shift code (the order of a double-precision floating-point number is moved 1023 to the right) is a binary number encoding method. In this chapter on bit operations, we need to look at three other common encoding methods.

Source, inverse, and complement

The original code is very simple and intuitive, with the first digit to represent the positive and negative numbers, the remaining bits (bit) used to represent the number. Let’s see how 11 and -11 are represented in code in one byte.

/ / + 11
00001011

// -11 is different only from the first one
10001011
Copy the code

The advantage of the original code representation is that it is intuitive and user-friendly to read. The disadvantage is that it is not user-friendly to calculate, and the computer cannot directly take the two numbers to do operations (such as addition).

Reverse code is on the basis of the original code, reserving the sign bits, negative numeric bits all “reverse”, if the original is 1, 0 becomes 0,0 becomes 1.

/ / + 11
00001011

// the value of -11 is negative except the sign bit
11110100
Copy the code

So once you code it, it’s pretty easy to do the operation, so a plus minus a is going to be equal to 11111111 (minus 0). The remaining problem, of course, is that this encoding produces zeros and -zeros.

/ / 0
00000000
/ / - 0
11111111
Copy the code

Having two representations of the same number is bound to lead to unnecessary judgments. So the complement appears.

The complement code is optimized on the basis of inverse code, the sign bit remains unchanged, and the negative value is +1 on the original basis.

/ / + 11
00001011

// -11 in the inverse code
11110100

// Complement -11
11110101
Copy the code

By adding 1, a plus minus a will add up to a carry.

  00001011 (11)
+ 11110101 (-11)
________________
 100000000
Copy the code

The extra bit will be ignored because of overflow, so a + -a = 0 is still true. So minus 0 doesn’t exist anymore. If I take the inverse of 00000000 and I add one, it’s still 00000000.

Ten million is used to represent negative numbers, so in the design of the complement, negative numbers are one bit more than formal. In modern computer systems, complement is used when referring to bit operations.

Bit operations in JavaScript

JS and base related methods

In operation before, first introduce two common Javascript method and hexadecimal related methods parseInt and Number prototype. ToString (base). Master these two methods so you don’t have to go alone

parseInt

ParsetInt is familiar with converting a string to an integer. The first argument is the string to parse, and the second argument is a base base, indicating what base to read the string from.

parseInt('1111'.2) / / 15
parseInt('1111'.8) / / 585
parseInt('1111'.16) / / 4369
parseInt('1111') / / 1111
Copy the code

⚠️ Note that in most cases parseInt will parse strings in decimal by default, whereas strings starting with 0x will be treated as hexadecimal numbers. ParseInt (‘ 0 x21 ‘) = = = 33. Other base strings in the ES6 standard, such as 0o12(octal) and 0b11(binary), do not automatically convert bases. To ensure the correctness and stability of the final result, do not omit the second parameter parseInt.

Numer.prototype.toString

Numer.prototype.toString does the opposite of parseInt, passing in a base that converts a number to a corresponding base representation.

15..toString(2) / / 1111
585..toString(8) / / 1111
4369..toString(16) / / 1111
Copy the code

In this example.. Number literals cannot directly call the method on the prototype chain. The extra point will be parsed into a Number object by JavaScript. You can also write it as Number(15).tostring (2).

By the way, be careful that the toString method for negative numbers yields the corresponding base representation of the absolute value of – +. For example – 11.. ToString (2) is -1011. If you want to get the correct negative complement, you can use the unsigned right shift described later.

An operator

Note that all operands and results in bitwise operations are reserved for 32-bit integers (only 8 bits are used for later examples), and as we saw in the previous article, the maximum range of safe numbers that JavaScript can represent is -(2^ 53-1) to 2^ 53-1. Not knowing this detail might confuse some of the results.

Before: 11100110111110100000000000000110000000000001
After:              10100000000000000110000000000001
Copy the code

Next we’ll look at one-by-one fine-digit operations and their applications, using 8-bit binary representation for convenience in the example.

The bitwise and &

The result is 1 if both bits are 1, 0 otherwise

  00001011 (11)
& 00001001 (9) the...00001001 (9)
Copy the code

Common application

For example, num & 1 is used to determine the parity of a number.

8(00001000) & 1= = =0
9(00001001) & 1= = =1
Copy the code

The React source code also uses binary bits to indicate the type of operations that need to be performed on the Fiber node.

export const Placement = / * * / 0b000000000000000000010;
export const Update = / * * / 0b000000000000000000100;
Copy the code

For example, to check whether the operation is Update, check whether flag & Update is zero.

Bitwise or |

The result is 0 if both bits are 0, and 1 otherwise

  00001011 (11)
| 00001001 (9) the...00001011 (11)
Copy the code

Common applications still use the React Fiber Flags example, using bitwise or combined operations. For example, use the insert and update combination to get a new type of insert or update.

export const PlacementAndUpdate = / * * / Placement | Update;
Copy the code

Xor ^ by bit

The result is 0 if both bits are 0 or 1, and 1 otherwise. The xOR of any number and itself is zero, and the xor of zero is itself.

  00001011 (11)
^ 00001001 (9) opinion00000010 (2)
Copy the code

Common applications are bitwise xor often appear in algorithm interviews, such as nums, a total of N numbers, one number occurs once, all the other numbers occur twice, O(n) time complexity, O(0) space complexity to find the number that occurs only once.

Using the property of xor cancelling in pairs, you can get the answer by xor everything up.

nums[0] ^ nums[1] ^... ^ nums[n -1]
Copy the code

Another common algorithm that takes advantage of the cancelling property is swapping two numbers without using intermediate variables.

let a = 11
let b = 9

a = a ^ b // a ^ b
b = a ^ b // a ^ b ^ b = a
a = a ^ b // a ^ b ^ a ^ b ^ b = b
Copy the code

Bitwise not ~

Bitwise 1 becomes 0,0 becomes 1, and the result appears as a complement.

~ 00001001 (9)..11110110 (-10)
Copy the code

For example, we use one byte to indicate the day of the week, from right to left, with the first byte indicating Sunday, the second byte indicating Monday…

To remove Sunday from a numeric value, use a bitwise non-generated mask and then do the and.

export const Sunday = / * * / 0b00000001;
export const Month =  / * * / 0b00000010;

const clearDay = (num, day) = > {
  let mask = ~day

  return num & mask
}

clearDay(num, Sunday)
Copy the code

The left < <

If you shift the binary representation of a value to the left, the removed bits are discarded and zeros are added at the end

01100001 << 2
____________________
10000100
Copy the code

In common applications, moving one digit to the left is equivalent to multiplying the value by 2. Note that bitwise operations are only 32 bits. More than 32 bits produces “weird” results.

1 << 30 / / 1073741824
1 << 31 / / - 2147483648
1 << 32 / / 1

3 << 31 / / - 2147483648
3 << 32 / / 3
Copy the code

Moves to the right > >

If you shift the binary representation of a number to the right, the last bit is discarded and the first bit is filled in by the sign bit, which is 1, complement 1, and 0, complement 0.

11010011 >> 1
____________________
11101001
Copy the code

The common application of moving a digit to the right is to divide the value by two.

Unsigned move right >>>

Unsigned to the right, just as the name implies, when you move to the right, you don’t care about the sign bit, you fill in all zeros.

11010011 >>> 1
____________________
01101001
Copy the code

Commonly used in JavaScript, there is no type of unsigned integer, and binary operations can only retain 32-bit results (whereas JS’s maximum safe representation range can be up to 53 bits). If you want to preserve a 32-bit unsigned result during a bit operation, you can use the unsigned right-shift operator, which yields a 32-bit unsigned integer.

1 << 31 / / - 2147483648
1 << 31 >>> 0 / / 2147483648
Copy the code

Mentioned negative execution Number. The prototype. ToString (2) the result of not complement, it is ok to use unsigned moves to the right.

(-11 >>> 0).toString(2)
"11111111111111111111111111110101" （4294967285)Copy the code

conclusion

This article reviews the basics of binary and common bit operations, including some less common “dirty” operations. For example, 15.. ToString (2), unsigned right shift, etc. Hope this article has been a success for you.

Finally, there are flaws with limited levels. Welcome correction, welcome thumbs-up + attention ━(‘ ∀´) Blue! .

The resources

  • Developer.mozilla.org/zh-CN/docs/…
  • Zh.wikipedia.org/wiki/%E4%BA…
  • 2 ality.com/2012/02/js-…
  • www.zhihu.com/question/38…
  • stackoverflow.com/a/1822769