For the sake of brevity, the beginning of 0D is omitted in the binary of this paper. The specific binary representation is subject to the specific language.

brainteasers

Let’s start with a classic interview quiz.

There are 1000 bottles of medicine, one of which is poisonous. If the rats drink it, they die a day later. What’s the minimum number of rats it takes to know which bottle is toxic a day later.

The answer is10Mice,'2 ** 10 = 1024 > 1000'.Copy the code

  1. We can number 1000 bottles in binary: the first bottle is 00 0000 0001, the second bottle is 00 0000 0010… To the thousandth bottle 11, 1110, 1000.

  2. Then ten mice, representing the number from 0 to 9, will drink all the potion numbered 0 and the first mouse will drink all the potion numbered 1, and so on.

  3. The dead mouse will tell you which potion is poisonous. If mice 0 and 5 die, the poison is 00 0001 0001, bottle 17.

The whole process is similar to each mouse as a binary digit, reminiscent of qin Shi Huang’s 30 million human computer in the Three-Body Problem.

extension

There are 1000 bottles of medicine, one of which is poisonous. If the rats drink it, they die a day later. How many mice is the minimum to know which bottle is poisonous in two days.

The answer is7Mice,3 ** 7 = 2187 > 1000.Copy the code

It’s similar to what we did before, but we’re going to use ternary.

  1. We can number 1000 bottles of medicine in ternary order: the first bottle is 000 0001, the second bottle is 000 0002… To the thousandth bottle 110, 1001.

  2. On the first day, seven mice, numbered from 0 to 6, drank all the drops numbered 0 and all the drops numbered 2, and the first mouse drank all the drops numbered 1…

  3. The next day, the number of the dead rat could be used to determine that the ternary digit of the poison was 2. On the second day, the mice that did not die continued to drink the potion numbered 1. On the third day, the number of the dead mice could be used to determine that the ternary bit of the poison was 1.

  4. Finally, the mice that died the first or second day could tell which bottle was poisonous. If mouse 0 or 5 died on the first day and mouse 1 died on the second day, the poison would be 002 0012, bottle 167.

singleNumber

1. Find the number in the array that appears only once. All other numbers appear twice (even times).

The answer is xor ^.Copy the code

Xor operation, i.e. 0 ^ 0 = 0, 1 ^ 1 = 0, 1 ^ 0 = 1. The result of any xor of a number and itself is 0, and any xor of a number and 0 is itself.

So we can be bold, and we can xor all the numbers in the array, and we’ll end up with numbers that only appear once. If [3, 3, 1], 3 ^ 3 ^ 1 = 1;

extension

2. Find the number in the array that appears only once. All other numbers appear three times (an odd number).

The triple case can be complicated, and the common practice is to save the number of occurrences using a Map and then iterate over the Map. Of course, binary is also possible:

Considering [5.5.5.1]
1 0 1
1 0 1
1 0 1
0 0 1Understanding the numbers as binary, the sum of each digit yields:3 0 4Each again %3To:0 0 1
Copy the code

Js implementation is as follows:

/ * * *@param {number[]} nums
 * @return {number}* /
function singleNumber(nums) {
    let res = 0;
    for (let i=0; i<32; i++) {
        let cnt = 0;
        let bit = 1 << i;
        nums.forEach(val= > {
            if (val & bit) cnt++;
        })
        if (cnt%3! =0)  res = res | bit;
    }
    return res;
};
Copy the code

Is it over? Force button: the number II that appears only once

We can refer to the idea of binary calculation, use A and B to count the number of occurrences of n, and get:

The initial value occurs the first time, occurs the second time, and occurs the third time0           0           n           0

b    0           n           0           0So if you do this three times, you get a and B0,0. The last value of b is the number that occurs only once.Copy the code

Js implementation is as follows (& ~ can be understood as the elimination operation, see 3. Authentication) :

/ * * *@param {number[]} nums
 * @return {number}* /
function singleNumber(nums) {
    let a = 0, b = 0;
    for (let num of nums) {
       b = (b ^ num) & ~a;         
       a = (a ^ num) & ~b;
    }
    return b;
};
Copy the code

authentication

We can use binary to store user permissions, for example

add0001Modify the0010delete0100The query1000
Copy the code

The advantage is, if you have multiple permissions can | operation directly. Such as/add, modify permissions at the same time have is 0001 | 0010 results for 0011.

In the query permission can be directly & operation. Add permission if (0011&0001) {}

The & ~ operation can be performed when removing permissions. For example, remove add permission 0011&~ 0001.

React, for example, represents effecttags in binary mode, allowing multiple effects to be easily assigned by bitwise manipulation.

// DOM needs to be inserted into the page
export const Placement = / * * / 0b00000000000010;
// DOM needs to be updated
export const Update = / * * / 0b00000000000100;
// The DOM needs to be inserted into the page and updated
export const PlacementAndUpdate = / * * / 0b00000000000110;
// DOM needs to be deleted
export const Deletion = / * * / 0b00000000001000;
Copy the code
// Initialize, no effect
fiber.effectTag = NoEffect;
/ / mark Update
fiber.effectTag |= Update;
// mark Placement. This fiber has both Update and Placement flags
fiber.effectTag |= Placement;
/ / delete the Placement
fiber.effectTag &= ~Placement;
// Determine if there is a Placement tag
(fiber.effectTag & Placement) === NoEffect ? false : true;
Copy the code

Gray code

The typical Binary Gray Code, or Gray Code for short, was named after Frank Gray’s (18870913-19690523) patent Pulse Code Communication published in 1953. It is now commonly used in analog-digital conversion and position-digital conversion. A variant of the Baudot code was used in 1880 by jean-Maurice Emile Baudot (18450911-19030328), a French telecommunications engineer. In 1941, George Stibitz designed an 8-element binary mechanical counter which exactly conforms to the counting law of gray code counter.

In computer networks, digital baseband signals usually use amplitude modulation, frequency modulation and phase modulation to change the waveform in order to carry more data.Take mixed-quadrature amplitude modulation QAM-16 as an example:

  • 12 kinds of phase
  • Each phase has 1 or 2 amplitudes to choose from
  • A total of 16 codes can be modulated

The constellation diagram is shown as follows:If the above codes are defined in binary, each can carry four bits. Such as0000，0001Can four bits and symbols be defined arbitrarily? The answer is no, because in data transmission, the signal is usually distorted by interference, and the modulated code is not accurate after demodulation. Here is a randomly defined constellation:

The five code elements A, B, C, D and E all correspond to 0000, but they do not fall in the ideal position in the constellation diagram due to signal distortion. Where A, B, C can be demodulated to 0000 (correct), but D is demodulated to 0001 (one bit error), and code element E is demodulated to 1111 (four all errors). Therefore, it can be seen that four bits and symbols cannot be defined randomly. In order to reduce the error rate, gray codes should be adopted, that is, each adjacent symbol has only one bit difference, as shown in the following figure:

The resources

Encoding and modulation