We all know about bitwise operations when we learn JS. We also see bitwise operations frequently in React and Typescript source code, but we never write bitwise operations like this in business code.

But is bit computing really far away?

It’s not. All the code you write is eventually converted to bitwise arithmetic, which hides the secrets of the CPU’s implementation.

Let’s talk about the relationship between bit operations and CPU and the application of bit operations in code.

Build cpus from transistors

The transistor

Let’s start with the transistor.

The next one is a triode, which is a kind of transistor. The characteristic is that when one end is energized, the current from the other ends can pass through. If the other end is not energized, the current from the other ends cannot pass through.

Isn’t that a switch?

It’s similar to the one below, except instead of turning it on and off manually, you switch it on and off with electricity.

On and off, that’s 1 and 0. This is how the building blocks of the computer world, units 1 and 0, are implemented.

Logic circuit

With 01 you can form a logic circuit, that is, a circuit with a gate, or gate, not gate, xOR gate, etc.

Their circuit symbol looks like this:

And the door:

Or the door:

Gate:

Xor gate:

How are they represented in JS?

With &

Or |

Non –

Exclusive or ^

They are the basic unit of logic circuit constituted by triode and can realize logic based on 0 1.

What is the logic?

1 over 0 is 0

1 | 0 to 1

~ 1 to 0

0 to the 0 is 0

With or not we are more familiar with, here is the xor:

If it’s different or identical it’s 0, if it’s different it’s 1, so it’s a 0 and a 1, otherwise it’s 0

Arithmetic unit

We know what a bit operation is, what a logic circuit is, so what can a logic circuit do?

There’s a lot you can do. The CPU is just a big logic circuit, and it’s based on bit computing.

For example, we implement the ALU algorithm:

First implement addition:

Addition in binary is xor, let’s try it:

1 and 0, 0 and 1 add up to 1, 0 and 0 add up to 0, 1 and 1 add up to 0, that’s xor.

Of course, you also have to deal with the carry, which can be obtained by the and operation, for example, the above four, only 1 and 1 are 1, otherwise they are all 0, and that’s the carry.

To be able to add and carry by bit, can realize the adder.

function add(a, b) {
    let sum = a;
    let carry = b;

    let temp;
    while(carry ! =0) {
        temp = sum;
        sum = temp ^ carry;
        carry = (temp & carry) << 1;
    }

    return sum;
}
Copy the code

Test the adder:

Note, the above and the xor do not have logic circuit, that circuit implementation of the above code is not the hardware implementation of the adder?

With addition, it’s easy to get a subtracter:

function subtract(a, b) {
    var substrahend= add(~b, 1)
    var sub= add(a, substrahend)

    return sub
}
Copy the code

Is it not subtraction to make the minuend negative and add it to it?

And why we’re taking the inverse plus one here, which involves the original inverse complement,

Because 1 corresponds to negative 1, and 0? There’s no minus 0, so there’s one less place. So you have to add one to make a match, which is what the complement means, to make up for the missing code without the minus zero.

After the implementation of the adder, subtracter, multiplication and division will also have, because multiplication is not multiple addition? Isn’t division just multiple subtractions?

In this way, we add, subtract, multiply and divide from bitwise operations.

How does that correspond to hardware? That is, we realized the logic circuit through the audion, and then realized the addition, subtraction, multiplication and division with the logic circuit.

CPU

That thing up there in the CPU is called the ALU, the arithmetic logic unit, which can do logical operations, arithmetic operations.

And based on the triode can also be done to store 0, 1 and other purposes, constitute a register.

With these things we can implement a CPU.

No wonder, with transistors and bit computing, we can build cpus, even though we only need hundreds of millions of transistors.

Of course, we only know this is not meaningful, but also to understand the application of bitwise operations.

Application of bit operation

The file system

A hard disk is divided into data blocks for use, and a file is composed of multiple data blocks:

The file uses a structure called the inode to record which blocks of data are used:

So how do I know which blocks are available when I want to save a file?

A block has only two states: idle and non-idle. A bit 0 and 1 can be saved, so bitmap is used to record.

For example, when I store images occupying blocks 2 and 4, I set the corresponding bitmap position to 1, otherwise it is 0. So when I need to store a file, I can look it up from the bitmap and know which blocks are available.

State is recorded by bitmap and judged by bit operation. Small space, high computing efficiency.

This is done at the operating system level, as are many performance-oriented libraries.

React and Typescript

In source code like React and Typescript, you’ll often see something called flags. Flags are similar to bitmaps, where a bit identifies a state.

React:

This determines whether fiberNode has Placement or Hydrating status and if so XXX.

Take a look at the Typescript source code again:

~ is to take the opposite condition, & again is determining whether not the state, and then through setting to | flags, which means that the flags of xx state with no logo.

Business code

Operating system, excellent libraries are used in the bit operation, because of their high performance, directly with the circuit, storage space is also small, that is not our code can be used?

Yes, but business code is more about maintainability, and if you write bitwise operations like the typescript source code above, you’ll be surprised if whoever takes over doesn’t want to kill you.

conclusion

The CPU realizes the switch of the circuit through the transistor, that is, 0 and 1, and then constitutes and or not or gate, further constitutes the logic circuit, the logic circuit can realize addition, subtraction, multiplication and division, constitute ALU, plus registers and other components constitute the CPU.

So bit operations are done directly by circuit, which is the most efficient, and all other operations will eventually be converted to bit operations.

Bitmaps and bitoperations are used in the design of operating system file systems, and flags is used extensively in React and Typescript sources. But that doesn’t mean business code should be used, because maintainability is more important.

Bit arithmetic hides the secret of CPU implementation, and is not just a trick.