The foundation is weak and the earth shakes. This article has been https://www.yourbatman.cn included, along with all the inside have Spring technology stack, MyBatis, middleware, such as the JVM, small and beautiful column study for free. Pay attention to the public number [BAT utopia] one by one to break, in-depth grasp,

The foreword ✍

Hi, I’m YourBatman.

We are serializing the Jackson In-depth analysis series, although we have covered only that so farStreaming APILayers, but have been exposed to its multipleFeatureCharacteristics. More importantly, I praised its exquisite design and elegant treatment in the article, so some friends sent me a private letter asking me:Digression: Jackson is such a niche topic that I can hardly feel confident enough to write about it. But what I said wasoweStay up late also have to commit to the paid content to open over, after all, there are so many people in white whoring is not 😄.

Voice: Later work, brag less forced ┭┮﹏┭┮

Although the minority, even want to know more about a wave of small partners, did let me excited for so three seconds. Since so that do, this article first to understand understandingBit operations in Java. Bitarithmetic is rarely used in Java, so why Jackson’s obsession? All in two words:performance/efficient. It’s a no-brainer to talk to a computer in a language it can understand directly.

✍ body

The mention of bit operations is both familiar and unfamiliar to most Java programmers. Familiar because you certainly learned JavaSE when you were studying it, and you can see it when you look at some open source frameworks (especially JDK source code); Strange because chances are we’re not going to use it. Of course, there are reasons why it doesn’t “catch on” : it’s hard to understand, it doesn’t fit the human mind, it’s not easy to read… .

Tip: In general, it is far more important for programs to be understood by humans than by machines

Bitarithmetic is used a lot in low-level languages, but rarely in high-level languages like Java. Java is supported even though we don’t use it much, because it’s often best practice to use bitwise.

Bit arithmetic is rarely used in daily development, but clever use of bit arithmetic can greatly reduce the running overhead and optimize the algorithm. A single statement may have little effect on the code, but it can save a lot of overhead in cases of high duplication and large data volumes.

binary

Before we understand what a bit operation is, it is important to introduce the concept of binary.

Binary is a number system widely used in computing technology. Binary data are numbers represented by 0 and 1 digits. It has a base of 2, the carry rule is to advance one every two, and the borrow rule is to borrow one as two. Because it only uses 0, 1 two numeric symbols, very simple and convenient, easy to use electronic means to achieve.

Tip: Semiconductor on represents 1, off represents 0, which is the basic principle of CPU computing 😄

Let’s start with an example:

o1011(binary) +11What's the sum of binary? The result is:1110(binary)Copy the code

Binary is very, very easy to understand, much easier than base 10. You might also be thinking about how binary and decimal interrotate. After all, you can’t see 1110 either. Or further thinking: how to convert to octal, hexadecimal, thirty binary…… Base conversion is not the content of this article, please search for yourself.

Binary and encoding

This is not very relevant to the content of this article, but by the way, coding problems are quite common in development.

The only ones and zeros that a computer can recognize are the ones and zeros that represent every word and language in the world. How do you express words and symbols? This is where character encoding comes in. Character encoding forces each character to correspond to a decimal number (note the difference between a character and a number, for example, the decimal number 48 for a zero character) and converts the decimal number into a binary that the computer understands, and the computer reads the ones and zeros and displays the corresponding text or symbol.

  • Typically for English characters, one byte represents one character, but for Chinese characters, since the low encoding was already used (early computers did not support Chinese, so the only way to extend support was to use more bytes), the high encoding had to be extended
  • The range of character set encodingutf-8>gbk>iso-8859-1(latin1)>ascll. The ASCLL code, short for American Standard Information Interchange Code, contains 255 common characters such as Arabic numerals, Letters, and some print symbols

Utf-8: A variable length encoding of 8 bits that encodes a code point (Unicode) from 1 to 4 bytes (1 byte for English and 3 bytes for most Chinese characters).

Binary in Java

Prior to Java version 7, Java did not support direct writing of literal numbers other than decimal. But this is allowed in Java7 and later:

  • Binary: prefix 0B /0B
  • Octal: prefix 0
  • Decimal: default value, no prefix is required
  • Hexadecimal: prefix 0x/ 0x
@Test
public void test1(a) {
    / / binary
    int i = 0B101;
    System.out.println(i); / / 5
    System.out.println(Integer.toBinaryString(i));
    / / octal
    i = 0101;
    System.out.println(i); / / 65
    System.out.println(Integer.toBinaryString(i));
    / / decimal
    i = 101;
    System.out.println(i); / / 101
    System.out.println(Integer.toBinaryString(i));
    // Hexadecimal
    i = 0x101;
    System.out.println(i); / / 257
    System.out.println(Integer.toBinaryString(i));
}
Copy the code

Result program, output:

5
101
65
1000001
101
1100101
257
100000001
Copy the code

System.out.println() will automatically convert to base 10 before output; ToBinaryString () is converted to a binary string for output.

Convenient base conversion API

The JDK has provided a very convenient BASE conversion API since 1.0, which is useful when we need it.

@Test
public void test2(a) {
    int i = 192;
    System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
    System.out.println("Decimal to binary:" + Integer.toBinaryString(i)); / / 11000000
    System.out.println("Decimal to octal:" + Integer.toOctalString(i)); / / 300
    System.out.println("Decimal to hexadecimal:" + Integer.toHexString(i)); //c0
    System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
    // Use the Integer valueOf() method,parseInt method is ok
    System.out.println("Binary to decimal:" + Integer.valueOf("11000000".2).toString()); / / 192
    System.out.println("Octal to decimal:" + Integer.valueOf("300".8).toString()); / / 192
    System.out.println("Hex to decimal:" + Integer.valueOf("c0".16).toString()); / / 192
    System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
}
Copy the code

Run the program, output:

--------------------------------- Decimal to binary:11000000Decimal to octal:300Turn the decimal hexadecimal: c0 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the binary to decimal:192Octal to decimal:192From hexadecimal to decimal:192
---------------------------------
Copy the code

How to prove that Long is 64-bit?

I’m sure every Javaer knows that the Long type in Java is 8 bytes (64 bits), so how do you prove it?

Tip: This is a classic interview question, at least one I’ve asked many times

The easiest way to do this is to take the maximum value of the Long type, convert it to a string, and look at the length as follows:

@Test
public void test3(a) {
    long l = 100L;
    // The output will not be that long if it is not the maximum (so use the Max/min example below)
    System.out.println(Long.toBinaryString(l)); / / 1100100
    System.out.println(Long.toBinaryString(l).length()); / / 7

    System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -");

    l = Long.MAX_VALUE; // 2 to the 63rd minus 1
    // The length of a positive number is 63.
    / / 111111111111111111111111111111111111111111111111111111111111111
    System.out.println(Long.toBinaryString(l));
    System.out.println(Long.toBinaryString(l).length()); / / 63

    System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -");

    l = Long.MIN_VALUE; // Minus 2 to the 63
    // The length of a negative number is 64 bits.
    / / 1000000000000000000000000000000000000000000000000000000000000000
    System.out.println(Long.toBinaryString(l));
    System.out.println(Long.toBinaryString(l).length()); / / 64
}
Copy the code

Run the program, output:

1100100
7
---------------------------------------
111111111111111111111111111111111111111111111111111111111111111
63
---------------------------------------
1000000000000000000000000000000000000000000000000000000000000000
64
Copy the code

Description: In computers, negative numbers are expressed as their positive complement. Therefore, you can prove for yourself that the Integer type is 32 bits (4 bytes) in the same way.

Bit operations in Java

The Java language supports a wide range of bitwise operators, listed below:

  • &: the bitwise and
  • |: or by location
  • ~: not by location
  • ^: XOR by bit
  • <<: left shift operator
  • >>: right shift operator
  • >>>: unsigned right shift operator

All except ~ and are binary operators that operate on data that can only be integers or char characters. For these operation types, the following examples are given at a glance.

Since it is an operation, it can still be divided into simple operation and compound operation for classification and explanation.

Tip: FOR ease of understanding, I’ll use binary for literal examples; using decimal (any base) doesn’t affect the result

Simple operation

Simple operations, as the name implies, use only one operator at a time.

& : bitwise and

Operation rule: 1 if both are 1, otherwise 0. The output is 1 only if both operands are 1, otherwise 0.

Note: 1. All literals in this example (the same below) are represented in decimal notation, so please use binary thinking to understand; 2. This article does not talk about the bit operation between negative numbers

@Test
public void test(a) {
    int i = 0B100; // The decimal value is 4
    int j = 0B101; // The decimal value is 5

    // Binary result: 100
    // Decimal result: 4
    System.out.println(Binary result: + Integer.toBinaryString(i & j));
    System.out.println("Decimal result: + (i & j));
}
Copy the code

| : or by location

Operation rule: 0 if both values are 0, otherwise 1. The output is 0 only if both operands are 0.

@Test
public void test(a) {
    int i = 0B100; // The decimal value is 4
    int j = 0B101; // The decimal value is 5

    // Binary result: 101
    // Decimal result: 5
    System.out.println(Binary result: + Integer.toBinaryString(i | j));
    System.out.println("Decimal result: + (i | j));
}
Copy the code

~ : indicates bitwise non

Operation rule: 0 is 1,1 is 0. All the zeros are going to be 1, and 1 is going to be 0.

Tip: Make sure it’s all in. Don’t ignore the zeros before the positive numbers

@Test
public void test(a) {
    int i = 0B100; // The decimal value is 4

    / / binary results: 11111111111111111111111111111011
    // Decimal result: -5
    System.out.println(Binary result: + Integer.toBinaryString(~i));
    System.out.println("Decimal result: + (~i));
}
Copy the code

^ : bitwise xOR

Operation rule: If the value is the same, the value is 0. If the value is different, the value is 1. If the operands are different (1 meets 0, 0 meets 1), the output result is 1; otherwise, it is 0.

@Test
public void test(a) {
    int i = 0B100; // The decimal value is 4
    int j = 0B101; // The decimal value is 5

    // Binary result: 1
    // Decimal result: 1
    System.out.println(Binary result: + Integer.toBinaryString(i ^ j));
    System.out.println("Decimal result: + (i ^ j));
}
Copy the code

<< : move to the left bit

Operation rule: move all the digits of a number to the left.

@Test
public void test(a) {
    int i = 0B100; // The decimal value is 4

    // Binary result: 100000
    // Decimal result: 32 = 4 * (2 ^ 3)
    System.out.println(Binary result: + Integer.toBinaryString(i << 2));
    System.out.println("Decimal result: + (i << 3));
}
Copy the code

The left shift is used so much that it’s easy to understand. If you shift x to the left by N bits, you can multiply it by 2 to the N in decimal, but you need to be careful about the overflow.

>> : Move to the right bit

Operation rule: move all the digits of a number to the right.

@Test
public void test(a) {
    int i = 0B100; // The decimal value is 4

    // Binary result: 10
    // Decimal result: 2
    System.out.println(Binary result: + Integer.toBinaryString(i >> 1));
    System.out.println("Decimal result: + (i >> 1));
}
Copy the code

Negative numbers shift right:

@Test
public void test(a) {
    int i = -0B100; // The decimal value is -4

    / / binary results: 11111111111111111111111111111110
    // Decimal result: -2
    System.out.println(Binary result: + Integer.toBinaryString(i >> 1));
    System.out.println("Decimal result: + (i >> 1));
}
Copy the code

Right shift is also used more, but also more understanding: the operation is actually the binary number to the right of the N bit directly cut off, and then the positive number to the right to fill 0, negative number to the right to fill 1.

>>> : Unsigned move right

Note: there is no unsigned left shift, there is no <<< sign

The difference between this and the >> sign shift to the right is that both positive and negative numbers complement 0. So for positive numbers, there’s no difference; So let’s see what happens with negative numbers:

@Test
public void test(a) {
    int i = -0B100; // The decimal value is -4

    / / binary results: 11111111111111111111111111111110 (> >)
	/ / binary results: 1111111111111111111111111111110 (> > >)
    // Decimal result: 2147483646
    System.out.println(Binary result: + Integer.toBinaryString(i >>> 1));
    System.out.println("Decimal result: + (i >>> 1));
}
Copy the code

I purposely put the >> results on top for you to compare. It doesn’t show up because it’s filled with 0, but you should know what’s going on.

Compound operation

Compound operations in the broad sense refer to multiple operations nested, usually of the same type. The compound operation is used with the = sign, like += -=. Originally this belongs to basic common sense need not do alone explanation, but who lets A elder brother tube unlive tube raise, tube kill tube bury 😄.

Mixed operation: refers to the same formula contains a variety of BAI operators, such as addition, subtraction, multiplication, division, multiplication, opening, du, etc..

Take the & and operation as an example, the others are the same:

@Test
public void test(a) {
    int i = 0B110; // The decimal value is 6
    i &= 0B11; // the same effect as: I = I & 3

	// Binary result: 10
	// Decimal result: 2
    System.out.println(Binary result: + Integer.toBinaryString(i));
    System.out.println("Decimal result: + (i));
}
Copy the code

For review, the operation rule of & is: if both are 1, then 1; otherwise, 0.

Example of bit operation scenarios

In addition to the high efficiency of bit operation, there is another feature that can not be ignored in application scenarios: reversibility of computation. Through this feature we can achieve the effect of hiding data, and also ensure efficiency.

In JDK source code. There are a lot of initial values that are computed by bit operations. The most typical example is a HashMap:

HashMap:
	
	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
	static final int MAXIMUM_CAPACITY = 1 << 30;
Copy the code

Bitwise operations have many nice features that can be useful in linearly growing data. And for some operations, bit operation is the most direct, the most convenient method. Here are some specific examples (usually interview questions) to get a feel for them.

Check whether two numeric symbols are the same

Both positive and negative numbers are the same, otherwise they are different. Small cases like this can be done by adding the >/< comparison to decimal, but it is more straightforward (and most efficient) to use bitwise operators:

@Test
public void test4(a) {
    int i = 100;
    int j = -2;

    System.out.println(((i >> 31) ^ (j >> 31)) = =0);

    j = 10;
    System.out.println(((i >> 31) ^ (j >> 31)) = =0);
}
Copy the code

Run the program, output:

false
true
Copy the code

Int (32 bits, 31 bits to the right, 0 to the right, 1 to the left)

Review ^ xor operation rule: same is 0, different is 1.

Judge the parity of a number

This can be done in decimal numbers by mod and 2, but there is a more efficient way of doing bit operations:

@Test
public void test5(a) {
    System.out.println(isEvenNum(1)); //false
    System.out.println(isEvenNum(2)); //true
    System.out.println(isEvenNum(3)); //false
    System.out.println(isEvenNum(4)); //true
    System.out.println(isEvenNum(5)); //false
}

/**
 * 是否为偶数
 */
private static boolean isEvenNum(int n) {
    return (n & 1) = =0;
}
Copy the code

Why can &1 judge the evenness? Because in binary the last digit of an even number must be 0, and the lowest digit of an odd number must be 1. The first 31 bits of a binary 1 are all zeros, so all the digits must be zeros after the first 31 bits of a binary 1 are zeros, so the only difference is the result of the operation on the lowest digit (1&0 or 0&0).

Swap two values (without third-party variables)

It’s an old interview question, swap A and B. If you don’t have the words in parenthesis, you can do it well.

@Test
public void test6(a) {
    int a = 3, b = 5;
    System.out.println(a + "-- -- -- -- -- -- --" + b);
    a = a + b;
    b = a - b;
    a = a - b;
    System.out.println(a + "-- -- -- -- -- -- --" + b);
}
Copy the code

Run the program, output (successfully swapped) :

3-------5
5-------3
Copy the code

The biggest advantage of using this approach is that it’s easy to understand. The biggest disadvantage is that a+ B can exceed the maximum range of ints, causing errors due to loss of accuracy, and causing very subtle bugs. So if you use it in the production environment, there are relatively large safety risks.

Tip: This is ok if your estimate is unlikely to exceed the maximum. Of course, if you’re a string, please forget I said that

This approach introduces third-party variables and poses significant security risks. Therefore, this article introduces a safe alternative to complete the operation by virtue of the reversibility of bit operation:

@Test
public void test7(a) {
    // The maximum value is used here to prove that overflow is not possible in this way
    int a = Integer.MAX_VALUE, b = Integer.MAX_VALUE - 10;
    System.out.println(a + "-- -- -- -- -- -- --" + b);
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    System.out.println(a + "-- -- -- -- -- -- --" + b);
}
Copy the code

Run the program, output (successfully completed exchange) :

2147483647-------2147483637
2147483637-------2147483647
Copy the code

As there is no addition operation on A/B in the whole text, overflow phenomenon cannot occur, so it is safe. The core rationale for this approach is the reversibility of bit operations, the use of xor to achieve the purpose.

Bit operations used on database fields (important)

This case is of great practical application significance, because I have used it many times in production, and I feel it is not generally good.

The embarrassing phenomenon of database design in business system: usually our data table may contain various state attributes, for example, in the blog table, we need to have fields indicating whether it is public, whether it has a password, whether it is blocked by the administrator, whether it is placed on the top and so on. In the later operation and maintenance, you will need to add new fields due to the planning requirements of adding new functions, which will cause maintenance difficulties in the later period, such as too many fields and index increase. At this time, the use of bit operation can be cleverly solved.

For example, when we conduct authentication and authorization on the website, we generally support multiple authorization methods, such as:

  • Personal certification 0001 -> 1
  • Mailbox authentication 0010 -> 2
  • Wechat authentication 0100 -> 4
  • Supertube certification 1000 -> 8

In this way, we can use the four digits 1111 to express whether the respective location is authenticated or not. The conditional statement to query wechat authentication is as follows:

select * from xxx where status = status & 4;
Copy the code

To query both through personal authentication, and through wechat authentication:

select * from xxx where status = status & 5;
Copy the code

Of course, you may also have sorting requirements, something like this:

select * from xxx order by status & 1 desc
Copy the code

This case is the same as Linux permission control that everyone is familiar with. It uses bitwise operations to control: permissions are r read, W write, and X execute, with weights of 4, 2, and 1, and you can combine permissions as you like. For example, chomd 7, 7=4+2+1 indicates that the user has RWX permission,

Matters needing attention

  1. You need your DB store to support bit operations, as MySql does
  2. Make sure your field type is not a char character, but a number
  3. This way it can invalidate the index, but generally the status value does not need an index
  4. Don’t just use it for show. If you use it wrong, you may be criticized

Serial number Generator (Order number generator)

Generate order serial number, of course this is not a very difficult function, the most direct way is the date + host Id+ random string to concatenate a serial number, or even see a lot of places directly using UUID, of course this is not recommended.

UUID is a string that is too long and unordered to carry valid information and therefore cannot provide effective help in locating problems. Therefore, it is usually an alternative

We learned bit operations today, and I think there’s a more elegant way to do it. What is elegant: you can refer to the order number of Taobao and JINGdong, seemingly regular, but actually not regular:

  • I don’t want that information out there.
  • Using a serial number allows you to quickly get relevant business information and quickly locate problems (this is very important, and the most important reason UUID is not recommended).
  • Using AtomicInteger increases concurrency and reduces collisions (another important reason not to use UUID because numbers are more efficient than strings)

Introduction to Implementation Principles

This serial number: date + Long value of a Long string of Numbers, like 2020010419492195304210432. Obviously, the date data is in front of it, and the long string behind it has a lot of meaning: the current number of seconds, the merchant ID (which can also be the rest of your business data), the machine ID, a random code, and so on.

Introduction to each part:

  1. The first part is the millisecond value of the current time. 999 Max, so it’s 10 places
  2. The second part is: serviceType indicates the serviceType. Such as order number, operation number, consumption number and so on. The maximum is 30, which is good enough. Accounted for five
  3. The third part is shortParam, which indicates the user-defined short parameter. You can place category parameters such as order type, operation type, and so on. A maximum of 30 is definitely enough. Accounted for five
  4. The fourth part is: longParam, ditto. Users can generally place ID parameters, such as user ID, merchant ID, and so on. The maximum support is 999.9 million. Most of them are enough, 30 of them
  5. The fifth part: the rest of the number to random number, random generation of a number, occupy the rest of the number. There are usually at least 15 bits left (this part of the number is floating), so it is sufficient to support 2 to the 15th power of concurrency
  6. Finally, add the date and time (year, month, day, hour, minute, second) before the long value above

This is A brother prepared based on A bit operation of serial number generation tool, has been used in the production environment. Considering the source code is longer (a file, a total of 200 lines or so, without any other dependence) will not be posted, if there is a need, please go to the public number background reply serial generator free access.

✍ summary

In practical work, it is not recommended to use the bit operator if it is just for the calculation of numbers. Only in some special scenarios, using the bit operation to do will give you a better feeling, such as:

  • N Multi-state control requires scalability. For example, whether the database is in state or not
  • There is an extreme demand for efficiency. Such as the JDK
  • The scene fits perfectly. For example, Jackson’s Feature pin value

Avoid by all means to dazzle (zhuang) technology (BI) and use, show skills cool, drop pit crematorium; The boy is still young. I hope you’re careful. In most cases, it is more important that code be readable by humans than by machines.

✔
  • It’s time for Fastjson to say goodbye
  • 1. Get to know Jackson — the best JSON library in the world
  • 2. Holy shit, Jackson wrote JSON like this
  • 3. Knowing this, Fang dared to say on his resume that he could write JSON with Jackson
  • 4. How are JSON strings parsed? JsonParser
  • It’s just a JsonFactory. It’s interesting. I didn’t expect this
  • 20 not confused, ObjectMapper use is no longer confused

♥ Concern A brother ♥

Author A brother (YourBatman)
Personal site www.yourbatman.cn
E-mail [email protected]
WeChat fsx641385712
Active platform
The public, BAT’s Utopia (ID: BAT-utopia)
Knowledge of the planet BAT’s Utopia
Daily Article recommendations Daily Article recommendations