Two days ago, I went to work, and suddenly little leaf sent me a message: Brother, what do you mean by these two pieces of code?

At first glance, this code feels both familiar and unfamiliar. I seem to have seen it somewhere, but I don’t seem to use it very often.

I drink saliva, calm thought 3s: yi, this is not that bit operator? React/react/react/react

Xiao Ye: Brother, can you tell me what it is?

Me: No problem. Let me tidy it up

What is a bit operation?

Bitwise operations are simply operations based on the binary representation of integers. It deals directly with every bit and is a very low-level operation, which has the advantage of being extremely fast but has the disadvantage of not being very intuitive.

Now you might ask:binaryWhat is?

Haha, in fact, if you are not a student, it is normal to be a little strange to binary. Let me briefly introduce binary.

binary

The numbers 2, 8, 16 we use are expressed in decimal, and the basis of bit operation is binary. That is, humans use the decimal system, and machines use the binary system. To understand the bit operation, we need to understand the conversion method and corresponding relationship between the decimal system and the binary system.

Decimal to binary

Decimal integers are converted to binary integers in reverse order, mod by 2. Specific approach is: use 2 to divide decimal integer, can get a quotient and remainder; Then divide the quotient by 2, and another quotient and remainder will be obtained, and so on until the quotient is less than 1. Then, the remainder obtained first as the lowest significant bit of the binary number, and the remainder obtained later as the highest significant bit of the binary number are arranged in order.

Take the decimal number 156 as an example:

Binary to decimal

Before the decimal point or the integer is multiplied from right to left by the corresponding power of 2 and increasing, after the decimal point is multiplied from left to right by the corresponding power of 2 and decreasing.

Take 1011.01 as an example:

After the introduction of binary and decimal conversion, we will take a look at a few bit operators often used in JS.

JS common 7 bit operators

There are seven basic bit operations, respectively

  • Bitwise AND (AND) &
  • The bitwise OR (OR) |
  • Bitwise XOR ^
  • Bitwise NOT (NOT) ~
  • Left shift <<
  • Sign move right >>
  • Unsigned move right >>>

Here’s a table summarizing the seven operators:

The operator usage describe
Bitwise AND (AND) & a & b For each bit, the result is 1 only if the corresponding bit bits of both operands are 1; otherwise, it is 0.
‘bitwise OR (OR) ` a
Bitwise XOR ^ a ^ b For each bit, the result is 1 if there is one and only one 1 in the corresponding bit of the two operands, and 0 otherwise.
Bitwise NOT (NOT) ~ ~a Invert the operand’s bits, i.e., 0 becomes 1,1 becomes 0.
Left shift << a << b Shift the binary form of A to the left by b (< 32) bits, filling the right with zeros.
Sign move right >> a >> b Move the binary representation of A to the right by b (< 32) bits, discarding the removed bits.
Unsigned move right >>> a >>> b Move the binary representation of A to the right by b (< 32) bits, discard the removed bits, and fill in the left side with zeros.

Bitwise AND (AND) &

&The operator (bitwise and) is used to compare two binary operands bitwise. If the corresponding bits are all 1’s, the result is 1, and if any of the bits are 0’s, the result is 0.

The bitwise OR (OR) |

|The operator (bit or) is used to compare two binary operands bit by bit. 1 as long as one of the two corresponding bits 1, otherwise 0.

Bitwise XOR ^

^The operator (bitwise xor) is used to compare two binary operands bit by bit. 1 only if the two corresponding bits are different.

Bitwise NOT (NOT) ~

~The operator (bitwise non) is used to compare two binary operands bitwise. Inverse, 1 becomes 0, 0 becomes 1.

1 inverse binary representation: 11111111 11111111 11111111 111111 11111110. Since the first digit is 1, the number is a negative number. JavaScript internally uses the form of complement to represent negative numbers, which means that you need to subtract 1 from the number, negate it again, and then add a negative sign to get the corresponding decimal value.

The inverse of 1 minus 1 is: 11111111 11111111 11111111 11111101.

Reverse code: 00000000 00000000 00000000 00000010. Plus the sign bit. So I end up with the bitwise of 1 is negative 2.

The negative of a binary number is taking the complement of that binary number and then +1. A binary number, with the highest digit 0 representing a positive number and the highest digit 1 representing a negative number. The bitwise non-operation of ~ is actually the process of taking the complement, which is also the inverse process of finding the negative value above, so it can be simply understood as the value of the negative value after subtracting 1.

There’s actually a trick here: a number that adds to its negative value equals negative 1.

Left shift <<

<<The (left shift) operator moves the specified binary to the left by the specified number of bits.

Sign move right >>

>>The operator (right shift) moves the specified binary to the right by the specified number of bits. 在MDNOn you can see:It is mentioned in the last sentence of the sentence"sign-propagating"The Chinese translation isSymbols transmittedWe know that computers store numbers in binary, and the first digit on the leftmost of the binary is calledThe sign bitSo it’s pretty obvious, when we move 2 to the right, we’re missing 2 digits on the left, so we should fill in the digits. What should we fill in?What's the sign bit? What do I fill in. Since the new leftmost bit is always the same as before, the sign bit is not changed. That’s why it’s called “symbol propagation.”

Unsigned move right >>>

Many of you might be right>>>and>>I’m curious about the difference, but again let’s seeMDNOn theUnsigned move right >>>Explanation:

Again, there is a core word: zero-fill right shift. It translates to zero fill, and this is even more obvious, because if YOU move it to the right, the empty space whatever your sign bit is, I’m just going to fill in 0.

This leads to the conclusion that for non-negative numbers, signed and unsigned right shifts always return the same result.

To this point, JS commonly used in the introduction of the 7 bit operators. Let’s take a lookReactFor in theBitwise operatorsThe usage scenario of. (After all, this is the first time I’ve seen bitwise operators used in a real business scenario)

React usage scenarios

EffectTag

We know that each React element corresponds to a Fiber object. A fiber object is usually a basic unit representing work:

// packages/react-reconciler/src/ReactFiber.js

// A Fiber is work on a Component that needs to be done or was done. There can
// be more than one per component.
export type Fiber = {
// Identify the label of type fiber
    tag: WorkTag,

    // point to the parent node
    return: Fiber | null.// point to a child node
    child: Fiber | null.// point to sibling nodes
    sibling: Fiber | null.// Set the props value at the start of execution
    pendingProps: any,

    // Props value set at the end
    memoizedProps: any,

    / / the current state
    memoizedState: any,

    // Effect type, see the following effectTag for details
    effectTag: SideEffectTag,

    // effect node pointer to the next effect
    nextEffect: Fiber | null.// Effect list is a one-way list
    firstEffect: Fiber | null.// Effect list is a one-way list, the last effect
    lastEffect: Fiber | null.// Expiration time of work, which can be used to identify a work priority order
    expirationTime: ExpirationTime,
};

Copy the code

Each fiber node has an effectTag value associated with it. React lists the possible side effects of work that cannot be done in the Render phase as follows:

// packages/shared/ReactSideEffectTags.js

export type SideEffectTag = number;

// Don't change these two values. They're used by React Dev Tools.
export const NoEffect = / * * / 0b000000000000;
export const PerformedWork = / * * / 0b000000000001;

// You can change the rest (and add more).
export const Placement = / * * / 0b000000000010;
export const Update = / * * / 0b000000000100;
export const PlacementAndUpdate = / * * / 0b000000000110;
export const Deletion = / * * / 0b000000001000;
export const ContentReset = / * * / 0b000000010000;
export const Callback = / * * / 0b000000100000;
export const DidCapture = / * * / 0b000001000000;
export const Ref = / * * / 0b000010000000;
export const Snapshot = / * * / 0b000100000000;
export const Passive = / * * / 0b001000000000;

// Passive & Update & Callback & Ref & Snapshot
export const LifecycleEffectMask = /*   */ 0b001110100100;

// Union of all host effects
export const HostEffectMask = / * * / 0b001111111111;

export const Incomplete = / * * / 0b010000000000;
export const ShouldCapture = / * * / 0b100000000000;
Copy the code

You can see that most of the values have only one 1 and all the other bits are zeros.

0bxxx is a representation of native binary literals

Here’s a scenario where effectTag is used:

  • (workInProgress.effectTag & DidCapture) ! == NoEffect

Here we are doing ampersand on binary: we are doing ampersand on Update and DidCapture, and it is obvious that all bits are zeros.

So the & operation is used to determine whether a variable contains an attribute. For example, check whether workinProgress. effectTag contains DidCapture.

The react source code contains a number of bit-operation scenarios, which are not explained here. Let’s take a look at the scenarios where bit operations are commonly used in actual business development.

Bit operators in JS clever use

Toggle variables 0 or 1

Usually we do some variable state switch, most of the write like this:

if (flag) {
    flag = 0;
} else {
    flag = 1;
}
Copy the code

Or for short:

flag = flag ? 0 : 1;
Copy the code

If implemented with bit operations:

toggle ^= 1;
Copy the code

There is no feeling very simple ~

Use the & operator to determine the parity of a number

Compared with the mod of 2, this method is also simpler:

// Even &1 = 0
// 奇数 & 1 = 1
console.log(2 & 1)    / / 0
console.log(3 & 1)    / / 1
Copy the code

Swap two numbers (no extra variables)

The most intuitive way to swap two integers is with a temporary variable:

let a = 5,
  b = 6
// Switch the values of a and b
let c = a
a = b
b = c
Copy the code

It is now required that you cannot exchange two integer values using additional variables or content space. This is where bit operations are used. Xor can be used to do this:

let a = 5,
  b = 6;

a = a ^ b; / / 3
b = a ^ b; / / 5
a = a ^ b; / / 6
Copy the code

If you don’t get it, let’s break it down.

A = a ^ b, i.e. a = 0101 ^ 0110 = 0011 = 3;

B = 0011 ^ 0110 = 0101 = 5;

Finally: A = a ^ b, i.e. a = 0011 ^ 0101 = 0110 = 6.

At this point, the two integer values are swapped without using additional variables.

The use of powers of two

Let’s take a look at this:

A power of 2

The conventional way to do it is to divide by 2 and see if you get a 1, which is to do it recursively.

/ * * *@param {number} n
 * @return {boolean}* /
var isPowerOfTwo = function(n) {
    if (n < 1) {return false;
    }
    if (n == 1) {
        return true;
    }
    if (n % 2 > 0) {
        return false;
    }
    return isPowerOfTwo(n / 2);
};
Copy the code

Let’s consider a faster solution: look at 2^0, 2^1, 2^2…… 2^n, their binary representation is 1, 10, 100, 1000, 10000……

To determine if a number is two to the NTH power, that is, to determine if there is only one digit in the binary representation that is in the first place. For example, if n=00010000, then n-1=00001111, that is, n&(n-1)==0

From this you can judge!

/ * * *@param {number} n
 * @return {boolean}* /
var isPowerOfTwo = function(n) {
    return n > 0 && (n & (n-1= = =))0
};
Copy the code

The number of ones

So here’s a little trick that you can easily figure out. It’s n ^ (n – 1) that cancels the last 1 of n.

If you are familiar with bitwise operations, you must be familiar with the above skill 🙈

So we can keep doing n = n ^ (n-1) until n === = 0, which means we don’t have any 1’s left. Use count to count ~

/ * * *@param {number} n - a positive integer
 * @return {number}* /
var hammingWeight = function(n) {
    let count = 0;
    while(n ! = =0) {
        // n & (n-1) cancels the last 1 of n
        n = n & (n-1)
        count++
    }
    return count
};
Copy the code

Permission System design

It is a common behavior to control the operation permissions of different users in the background management system. We usually use an array to represent the operation permissions of certain users:

roles: ["admin"."editor"].Copy the code

Imagine if we used bit operations to design the permission system:

  • Administrator (level 1) : 0b100
  • Development (Level 2 permission) : 0B010
  • Operation (Level 3 permission) : 0B001

If operation A can only be performed by administrator and development, then the value of this permission is expressed as 6 = 0b110, which is the same as the administrator permission: 6&4 = 0b110&0b100 = 4, which is not 0, so it is considered to have permission. Similarly, the development permission is not 0, while the operation permission is 0, so the operation has no permission.

The advantage of this is that we can use a number instead of an array to represent the set of permissions for an operation, and it is also very convenient to make permissions judgments.

conclusion

This article has done a more systematic explanation to the bit operation. In fact, in the actual development, do not understand the bit calculation of the students are also many. However, the reasonable use of bit operation in some scenarios can also solve a lot of practical problems.