Shulou(Shulou.com)06/03 Report--

The purpose of this article is to share with you the content of sample analysis of bit operations and common binary systems in Java. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

How many systems are common?

Binary (Binary)

The value range is 0 ~ 1, full 2 into 1.

Start with 0b or 0B

Bit bit is the smallest memory unit of a computer, and one bit occupies one binary bit, that is, 0 or 1.

1 byte byte with 8 bit occupies 8 binary bits

Int integer 4 bytes occupy 32 binary bits

The left half of the binary is high, and the right half is low.

The highest bit in binary is 0 for positive number, and the highest bit is 1 for negative number

The binary source code is inverted to get the inverse code, the inverse code complement 1 gets the complement code, and the negative number is represented by the complement code.

Octal (Octal)

Values range from 0 to 7, full 8 into 1

Start with the number 0

Decimal (Decimal)

Values range from 0 to 9, full 10 into 1

Daily Arabic numerals are decimal

Hexadecimal (Hexadecimal)

Value range 0-9 and Amurf, full 16 into 1

Start with 0x or 0X. Amurf here is case-insensitive.

Java eight bitwise operations?

Bitwise and (&)

If it's all 1, it's 1.

Bitwise or (|)

If you have one, you get one.

Bitwise XOR (^)

Different get 1, the same get 0

Bitwise inverse (~)

Take the opposite, that is, 1 becomes 0, 0 becomes 1

Move left bitwise ()

If you move a few bits to the right, the low position will be truncated, the positive high position will be filled with a few zeros, and the negative high position will be filled with a few 1s.

Move bitwise unsigned right (>)

If you move a few bits to the right, the low position will be truncated, and the positive and negative high position will be filled with a few zeros.

Bitwise unsigned left shift ((unsigned right shift) two bit operations

Static final int hash (Object key) {int h; return (key = = null)? 0: (h = key.hashCode ()) ^ (h > 16);}

Where key is the string "name", String overrides the hashCode () method that calculates the hashCode value of the string. The source code is as follows:

The calculated hashCode value is 3373707.

The second step

Calculate the hash value based on the hashCode value

(h = key.hashCode ()) ^ (h > 16) that is (3373707) ^ (3373707 > 16)

3373707 binary expression

0000000001100110111101010001011

H > 16 binary expression

00000000000000000000000000110011

According to the principle of ^ XOR operation, one is obtained differently, and the same zero gets 3373707 ^ (3373707 > 16). The binary result is:

0000000001100110111101010111000

Binary online conversion: http://tools.jb51.net/transcoding/hexconvert

That is, the hash value of key is calculated to get 3373752, and the hash value after the breakpoint happens to be the same value.

The third step

Calculate the array index subscript in which the element (key/value) will eventually be placed based on the hash value

Formula: I = (n-1) & hash

It's used here & bitwise and operation (if both are 1, you get 1)

Formula (n-1) & the secret of hash is that n represents the size of the array in HashMap, and it happens to be 1610, 32, and 64. The power of 2, which is actually equivalent to taking the module hash% n, and the calculated array index subscript value is the same, and it can also guarantee that the array subscript will not cross the bounds.

However, HashMap does not use% modulus here, because the hash value is an int integer, that is, a decimal value. Using% modulus will first convert the memory data into decimal before operation, which has more performance overhead, so the efficiency is relatively low.

The% module is used at the bottom of HashTable, and the hash value is bitwise and calculated with hexadecimal 0x7FFFFFFF in order to ensure that the hash value is always positive.

Some friends may ask, use% module calculation, then why is HashTable still in use here? what I want to say is that it can also be optimized, but HashTable itself focuses on synchronized thread safety, so it does not consider optimizing% module as bit operation.

The fourth step

Finally, create a new node based on the element (key/value) and save it to the specified array index subscript location

Node newNode (int hash, K key, V value, Node next) {return newNode (hash, key, value, next);} finale: why does the underlying source code of HashMap use so many bits?

With regard to the use of bit operation, when introducing the third step, the paper also mentions the problem of HashMap calculating array subscript using% modulus and bit operation. The secret of using bit operation is to read data directly from memory for calculation, and there is no need to convert to decimal system. If using% mode, it needs to be converted to decimal system first, which has performance overhead and low efficiency.

In addition to the bitwise XOR, > unsigned right shift, & bitwise and bitwise operations mentioned in the article, the bottom layer of HashMap is actually used in HashMap's expansion mechanism resize ().

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.