An operation

Bitwise operations operate directly on the binary bits of an integer in memory.

@[toc]

A, meaning,

  • Bit operation efficiency is high, in the gate circuit implementation, bit operation efficiency is much higher than the efficiency of addition, subtraction, multiplication and division.

  • In addition to our understanding of the source code is also very helpful, for example, Java HashMap has such a section of source code, source code analysis click here

Two, what is the main bit operation

Operators including and (&), or (|), exclusive or (^), not (~) and left (< <), moves to the right (> >), unsigned right shift (> > >)

2.1. The and operator (&)

Compare each bit with (&), both bits are 1, resulting in 1, or 0 otherwise

If I have 4 and 7 then how do I do this?

First we need to convert two decimal numbers to binary

4:0000 0100

7:0000, 0111

3.2, or operator (|)

Or (|) each comparison, the two have a is 1, the result is 1

5 | 9, for example

5:0000, 0101

9:0000, 1001

2.3 xOR operator (^)

The xor (^) bits are compared. The same bits are 0 and the different bits are 1

7 ^ 15, for example

7： 0000 0111

15:0000 1111

2.4. Non-operator (~)

Compare each bit, invert the bit (sign bit also invert)

Rule of operation: if the bit is 0, the result is 1, if the bit is 1, the result is 0.

Such as: ~ 37

In Java, all data is represented in the form of complement. If there is no special explanation, the default data type in Java is int. The length of int data type is 8 bits, and one bit is 4 bytes, which is 32 bytes, 32 bits.

-37 to binary is 100101.

After completion, the value is 00000000 00000000 00000000 00100101

The inverse is: 11111111 11111111 11111111 11011010

Since the high order is 1, the source code is negative, and the complement of negative is the reverse of the source code of its absolute value, and the end is added with 1.

Here do not understand can refer to the original code, inverse code, complement code

Therefore, we can restore the complement of the binary number: first, subtract 1 from the end to get the inverse code: 11111111 11111111 11111111 11011001 Second, invert the bits to get the original code:

00000000 00000000 00000000 00100110 in this case, the binary source code is 38

So minus 37 is minus 38.

2.5. Left shift Operation (<<)

To move to the left is to move all the bits to the left by a few places

For example: 12 << 2 means 12 moves two places to the left

The binary of 12 is: 0000 1100

And you can see from this diagram, all the bits are moved two to the left, and then you fill in the two left bits with zeros, and you get rid of the two left bits, and you get 00110000 which is 48

Let’s do the same for 12<<3 and we get 96

8<<4 is 128Copy the code

So this gives us a fast algorithm M << n which is actually M << n = M times 2n

2.6 Right shift Operator (>>)

This is basically the same thing as the left shift operation

Example: 12 >> 2

We can see that the right shift is the same as the left shift, but it’s a little bit different, but the difference is that we complement positive and negative numbers differently, negative numbers complement 1, positive numbers complement 0

Let’s do another -8 of -8>>2

So just to summarize, for negative numbers or positive numbers, it’s the same thing when you shift them, but when you fill up, you fill up if the highest digit is 0, you fill up if the highest digit is 1

M >> n = M / 2^**n

2.7 unsigned right shift (>>>)

It moves bits in the same way as the right shift operator, except that when you fill bits, either 0 or 1, you fill 0

>>> Analysis in HashMap

Public class test {public static void main(String[] args) {cap=5; int result=tableSizeFor(cap); //8 System.out.println(result); } static int tableSizeFor(int cap) { int n = cap - 1; // >>> : Unsigned move right. Both positive and negative values complement 0. n |= n >>> 1; // 00000100 | 00000010 = 00000110 6 n |= n >>> 2; // 00000110 | 00000001 = 00000111 7 n |= n >>> 4; // 00000111 | 00000000 = 00000111 7 n |= n >>> 8; // 00000111 | 00000000 = 00000111 7 n |= n >>> 16; // 00000111 | 00000000 = 00000111 7 return n + 1; // 00001000 =8 // 0000000111 = 2 00001000}}Copy the code

Here n | = n > > > | 1 is n = n (n > > > 1)

This function implements the algorithm to change a number to the nearest 2 to the n power. For details refer to the code above