Two days ago to work, suddenly leaflet gave me a message: brother, you see these two pieces of code is what mean?



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

I drank water, and thought calmly 3s: hey, isn’t this the bit operator? I’ve learned it in college before, and I’ve seen it in the React source before.

Little leaf: brother, can you tell me what this is?

Me: no problem, wait for me to tidy up ~

What is bitwise operation?

Bit operations are simply operations performed on the binary representation of integers. It deals directly with every bit, which is a very low-level operation. The advantage is that it’s very fast, but the disadvantage is that it’s not very intuitive.

Now you might ask,binaryWhat is?

Haha, in fact, if not the class of students, a little strange to the binary is normal. So let me give you a brief introduction to binary.

binary

We commonly used 2, 8, 16 and other numbers are decimal representation, and the basis of bitwise operation is binary. In other words, humans use decimal system, while machines use binary system. To understand bitwise operation, we need to understand the conversion method and corresponding relationship between decimal system and binary system.

10 to binary

Decimal integers are converted to binary integers by taking mod by two and ordering in reverse order. How to do it is: use 2 to divide decimal integer, can get a quotient and remainder; Then divide the quotient by 2, and you get a quotient and remainder, and so on, until the quotient is less than 1, and then the remainder as the low significant bits of the binary number, and the remainder as the high significant bits of the binary number, and then the remainder as the high significant bits.

Take the decimal number 156 as an example:

Binary to decimal

Before the decimal point or whole number, you multiply each binary number from right to left by the corresponding power of 2 and increase it, and after the decimal point you multiply it from left to right by the corresponding power of 2 and decrease it.

Take 1011.01 as an example:

With the introduction to binary and decimal conversion, let’s take a look at some of the bit operators commonly used in JS.

JS commonly used seven bit operators

There are 7 basic bit operations, respectively

  • By bit AND (AND) &
  • The bitwise OR (OR) |
  • XOR by bits (XOR) ^
  • By bit NOT (NOT) ~
  • Left shift (Left shift) <<
  • Signed to the right >>
  • Unsigned move >, >, >

Here is a table to summarize the above seven operators:

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

By bit AND (AND) &

&Operator (bit and) is used to compare two binary operands bit by bit. If all the corresponding bits are 1, the result is 1, and if any of the bits are 0, the result is 0.

The bitwise OR (OR) |

|Operator (bit or) is used to compare two binary operands bit by bit. It is a 1 if one of the two corresponding bits has a 1, otherwise it is a 0.

XOR by bits (XOR) ^

^Operator (bit XOR) is used to compare two binary operands bit by bit. It’s only 1 if the two corresponding bits are different.

By bit NOT (NOT) ~

~Operator (bit non) is used to compare two binary operands bit by bit. Reverse the position, 1 goes to 0, 0 goes to 1.

1 inverse binary means: 1111111111 1111111111 1111111110. Since the first (sign bit) is 1, this number is a negative number. Inside JavaScript, negative numbers are represented by a complement, which means you have to subtract 1 from the number, negate it again, and then add a minus sign to get the decimal value of the negative number.

The inverse of 1 minus 1 is: 1111111111 111111111101.

Reverse code is reversed: 00000000 00000000 00000010. Plus the sign bit minus. And you end up with a 1 which is not a bitwise negative 2.

The negative of a binary number is to take the complement of the binary number and then +1. A binary number with the highest bit 0 denotes a positive number and the highest bit 1 denotes a negative number.
~In fact, the bitwise non-operation is the process of obtaining the complement, which is the inverse process of obtaining the negative value above. Therefore, it can be simply understood as the negative value of the value followed by a reduction of 1.

And there’s a little trick here: a number plus the inverse of itself is equal to negative 1.

Left shift (Left shift) <<

<<Operator (shift left) indicates that the specified binary is moved to the left by the specified number of bits.

Signed to the right >>

>>Operator (right shift) indicates that the specified binary is moved to the right by the specified number of bits.



inMDNAbove you can see:



This sentence is mentioned in the last sentence"sign-propagating"“, the Chinese translation isSymbols transmittedWe know that the computer stores numbers in binary, and the leftmost digit in binary is called the first digitThe sign bitSo it’s pretty obvious that when we move 2 to the right, we’re missing 2 digits on the left, so we should fill in the digits. So what do 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 has not been changed. That’s why it’s called “symbol propagation.”

Unsigned move >, >, >

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

Again, there’s a core word: zero-fill right shift. It translates as zero – fill, and it’s even more obvious, but if you move to the right, I’m just going to fill in the zero whatever sign bit you have.

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

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

Scenarios in React

EffectTag

We know that each React element corresponds to a Fiber object. A Fiber object is usually a basic unit of 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 = {// Tag: WorkTag, // Return to the parent node: Fiber | null, / / the child to child nodes: Fiber | null, / / to the node (: Fiber | null, / / setting props value at the beginning of the execution pendingProps: MemoizedProps: Any, // The current state memoizedState: Any, // The current state memoizedState: Any SideEffectTag, / / effect node pointer to the next effect nextEffect: Fiber | null, / / effect list is a singly linked list, the first effect firstEffect: Fiber | null, / / effect list is a singly linked list, the last effect lastEffect: Fiber | null, / / the work of the expiration time, can be used to identify a work priority order expirationTime: expirationTime,};

Each Fiber node has a effectTag value associated with it. We call some work that cannot be completed in the Render phase side effects. React lists all possible side effects, 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;

You can see that most of the values have only one digit and all the other digits are 0.

0bxxxIs a representation of native binary literals

Here’s a scenario where EffectTag is used:

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

Here we are doing and on binary: we are doing & with Update and didCapture, and the result is obvious: all bits are 0.

So the ampersand operation is used to determine whether a variable contains a property. For example, check if the workInProgress.effectTag property contains didCapture.

There are many more bitwise scenarios in the React source code, which I won’t describe here. Here’s a look at some of the scenarios in which bit-based computing is more commonly used in real business development.

The use of bitwise operators in JS

Toggle the variable 0 or 1

Usually we do some variable state switch, will probably write like this:

if (flag) {
    flag = 0;
} else {
    flag = 1;
}

Or simply:

flag = flag ? 0:1;

If you use bitwise operation to achieve:

toggle ^= 1;

Does not feel very simple ~

Use the & operator to determine whether a number is even or odd

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

// Even & 1 = 0 // Odd & 1 = 1 console.log(2 & 1) // 0 console.log(3 & 1) // 1

Swap two numbers (cannot use extra variables)

The most intuitive way to exchange the values of two integers is with a temporary variable:

Let a = a a = b b = c let a = a a = b b = c

It is now required that you cannot use additional variables or content space to exchange the values of two integers. In this case, we have to use bit operation. We can do this by using XOR:

let a = 5, b = 6; a = a ^ b; // 3 b = a ^ b; // 5 a = a ^ b; / / 6

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

(a = 0101 ^ 0110 = 0011 = 3) (a = 0101 ^ 0110 = 0011 = 3)

B = 0011 ^ 0110 = 0101 = 5;

A = 0011 ^ 0101 = 0110 = 6.

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

About powers of two

This is one of the things that I saw when I was scrolling LeetCode. Let’s take a look at it:

A power of 2

The normal way to do it is to divide it by 2, and see if it’s going to be 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);
};

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 whether a number is a power of 2, that is, to determine whether there is only one digit in the binary representation in the first place. For example, if n=00010000, then n-1=00001111, that is, n&(n-1)==0

From this can judge!

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

The number of ones there are

And there’s a little trick here, which is easy to figure out. That’s n & n minus 1, which cancels out the last 1 in n.

If you are familiar with arithmetic, you must be familiar with this one
skillFamiliar with 🙈

So we can keep going n equals n & (n minus 1) until n equals equals equals equals equals zero, which means we don’t have a 1. To count by count ~

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

Permission System Design

It is a very common behavior to control the operation authority of different users in the background management system. We usually use an array to represent the privileges that a user has:

roles: ["admin", "editor"],

Imagine if we designed this permission system using bitwise operations:

  • Administrator (Level 1 permission) : 0B100
  • Development (secondary authority) : 0B010
  • Operation (Level 3 authority) : 0B001

If the A operation can only be operated by administrators and developers, then the permission value is expressed as 6 = 0B110, which is the same as the administrator permission: 6&4 = 0B110&0B100 = 4. The result is not 0, so it is considered authorized. Similarly, development permissions & 6 & 2 = 2 are not 0, and operation permissions & 6 & 1 = 0, so operation has no permissions.

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 for permission determination.

conclusion

This forAn operationMade a more systematic explanation. In fact, in the actual development, do not knowBit isMy classmates are also quite a few. But it can be used reasonably in certain situationsAn operationIt can also solve a lot of practical problems.