There is a method in the Integer class that you can pass in a number and it will return the largest power of 2 that is less than or equal to that number. That method is highestOneBit(int I).

In addition, I have compiled the interview questions for 20 years, including Spring, concurrency, database, Redis, distributed, Dubbo, JVM, microservices and other aspects of the summary, if you need to get:Tencent document

1. Method logic analysis

For example, in the following Demo, note the method input and return values:

System.out.println(Integer.highestOneBit(15));  / / output 8
System.out.println(Integer.highestOneBit(16));  16 / / output
System.out.println(Integer.highestOneBit(17));  16 / / output
Copy the code

This method also requires very little code to implement:

public static int highestOneBit(int i) {
	// HD, Figure 3-1
	i |= (i >>  1);
	i |= (i >>  2);
	i |= (i >>  4);
	i |= (i >>  8);
	i |= (i >> 16);
	return i - (i >>> 1);
}
Copy the code

Next, let’s examine the logic of this piece of code in detail.

  • First, for what this method does: Given a number, find a power of two less than or equal to that number.

  • If we’re going to do it ourselves, we need to know how to tell if a number is a power of two.

  • Seriously, I can’t think of a good way to do that. The only thing I can think of is a number that, when translated into binary representation, has a rule: if a number is a power of two, then the binary representation has only one 1 bit and all the other bits are zeros.

For example, in decimal 6, the value is 0000 0110 in binary 8, 0000 1000 in decimal 9, 0000 1001 in binary

So, we can use the binary representation of a number to determine whether it is a power of two. How is the key code implemented? Go through every bit, okay? Yes, but it’s not good. So what? Why don’t we go back and take a closer look at how Integer is implemented?

Second, the implementation principle of Integer itself

public static int highestOneBit(int i) {
	// HD, Figure 3-1
	i |= (i >>  1);
	i |= (i >>  2);
	i |= (i >>  4);
	i |= (i >>  8);
	i |= (i >> 16);
	return i - (i >>> 1);
}
Copy the code

We find that there is no traversal in this code, only bitwise operations and a subtraction, which means that it is implemented in a completely different way than our own implementation, which is: given a number, through a series of operations, to get a number less than or equal to a power of 2.

That is, if you are given a number 18, you have to do the operation to get 16. 18 in binary: 0001 0010 The desired result (16) is: 0001 0000

So all we need to do is clear all bits of the binary number 18, except for the highest bit 1, and we get the result we want.

Third, how to implement this process through bit operation?

Take the binary number 0001 0010 for example: move 0001 0010 to the right by 1 bit to get 0000 1001, and then apply the or to itself to get 0001 1011.

Then move 0001 1011 2 bits to the right to get 0000 0110, and then perform or with itself to get 0001 1111.

Then move 0001 1111 4 bits to the right to get 0000 0001, and then perform or with itself to get 0001 1111.

Move 0001 1111 8 bits to the right to get 0000 0000, and then apply or to itself to get 0001 1111.

Move 0001 1111 16 bits to the right to get 0000 0000, and then apply or to itself to get 0001 1111.

Move 0001 1111 unsigned one bit to the right to get 0000 1111.

For unsigned right shift, see this article:The article links

0001 1111-0000 1111 = 0001 0000 We got what we wanted.

The process can be abstracted as follows: we now have a binary, 0001****, and we don’t care about the low value, we shift it to the right and perform or.

First move 0001**** 1 bit to the right to get 00001***, and then perform or operation with itself: get 00011***.

Then move 00011*** 2 bits to the right to get 0000011*, and then perform or operation with itself to get 0001111*.

Then move 0001111* 4 bits to the right to get 00000001, and then operate or with itself to get 00011111.

There is no need to calculate further, here we can actually find a rule: the purpose of the right shift and or operation is to make the low point of a number become 1, and then subtract the result of the result of the right shift one, it is equivalent to clearing the low point of the original number. Even if we get the results we want.

At this point, can only sigh JDK authors for the use of bit operations have reached the realm of excellence.