This is the 10th day of my participation in Gwen Challenge

Original: Telami’s Blog, welcome to share, reprint please reserve source.

In a HashMap of 1.8, there is an algorithm whose function is to return a number greater than the nearest integer power of 2 (regardless of the maximum capacity) of the input parameter

    /** * Returns a power of two size for the given target capacity. */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0)?1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
Copy the code

I also read some other people’s analysis on the Internet and sorted it out as follows:

n |= n >>> 1; Is equivalent to the n = n | (n > > > 1);

Let’s say cap is equal to 65;

    int n = cap - 1  // that is, n = 64 (1000000 binary)
    n |= n >>> 1;    / / that is n = n | (n > > > 1) = 1000000 | 0100000 = 1100000
    n |= n >>> 2;    / / that is n = n | (n > > > 2) = 1100000 | 0011000 = 1111000
    n |= n >>> 4;    / / that is n = n | (n > > > 4) = 1111000 | 0001111 = 1111111
Copy the code

The last step is a nested ternary operation which returns 1 if n is less than 0, otherwise it continues to determine if n exceeds the maximum capacity, and returns n + 1 which is n= 128 compared to our input value –> The nearest power of 2 greater than 65 is 128

In fact, excluding the above specific example, the whole process can be summarized as follows:

  • Let’s assume that the binary of n is 01xxx… XXX. Then,

  • Move n 1 bit to the right: 001XX… XXX, or: 011XX… xxx

  • For n, move 2 to the right: 00011… XXX, or: 01111… xxx

  • We already have four ones in front of us, so we move four more to the right and we get eight ones

  • Similarly, if you have eight ones, moving eight to the right will definitely make the next eight ones.

  • In summary, the algorithm makes all bits after the highest 1 become 1.

  • And then n plus 1, you get 2 to the whole power.

So that’s pretty clear. Why in the first place

-int n = cap - 1;

The purpose of reassigning cap-1 to n is to find a target value greater than or equal to the original value. For example, the value is 1000 in binary and 8 in decimal. If you don’t subtract 1 from it, you get the answer 10000, which is 16. Obviously not the result. If you subtract 1 from the binary to 111, you get the original value of 1000, or 8.

Bit operations are quite efficient.