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

This article will explain in detail what is the role of the Integer.highestOneBit(int i) method. The content of the article is of high quality, so Xiaobian shares it with you as a reference. I hope that after reading this article, you will have a certain understanding of relevant knowledge.

There is a method in the Integer class that you can pass in a number and it will return a power of two or less. This method is highestOneBit(int i).

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

System.out.println(Integer.highestOneBit(15)); //outputs 8System.out.println(Integer.highestOneBit(16)); //outputs 16System.out.println(Integer.highestOneBit(17)); //outputs 16

The implementation code of this method is also very small:

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);}

Next, let's analyze the logic of this code in detail.

First, for the function of this method: given a number, find a power of two less than or equal to that number.

If we want to do this ourselves, we need to know how to tell if a number is a power of two.

Seriously, I can't think of any good way to tell. The only thing I can think of is that a number, if converted to a binary representation, has a rule: if a number is a power of two, then its binary representation has only one bit with 1 and all other bits are zeros. For example: decimal 6, binary representation: 0000 0110 decimal 8, binary representation: 0000 1000 decimal 9, binary representation: 0000 1001 So, we can use the binary representation of a number to determine whether the number is a power of 2. How does the key code work? Go through every bit? Yes, but not good. What then? Let's go back and take a closer look at how Integer is implemented.

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);}

We find that there is no traversal in this code, only bit operation and subtraction, which means that its implementation idea is completely different from our own implementation idea. Its idea is: Given a number, through a series of operations, we get a number less than or equal to a power of 2.

That is, if you give a number 18, you will get 16 after the operation.

18 in binary notation: 0001 0010

The desired result (16) is: 0001 0000

Then the process of this operation is nothing more than clearing all the bits except the highest bit 1 in the binary number corresponding to 18, then we get the result we want.

So how do we do this with bitwise operations?

Let's take the binary number 0001 0010 corresponding to 18 as an example: first shift 0001 0010 to the right by one bit to get 0000 1001, and then OR with itself: get 0001 1011.

Then shift 0001 1011 to the right by 2 bits to get 0000 0110, and then OR with itself: get 0001 1111.

Then shift 0001 1111 to the right by 4 bits to get 0000 0001, and then OR with itself: get 0001 1111.

Then shift 0001 1111 to the right 8 bits to get 0000 0000, and then OR with itself: get 0001 1111.

Then shift 0001 1111 to the right 16 bits to get 0000 0000, and then OR with itself: get 0001 1111.

0001 1111 is shifted unsigned to the right by 1 bit to obtain 0000 1111.

For unsigned right shift, see my previous article.

Finally, shock with 0001 1111 - 0000 1111 = 0001 0000! We got the results we wanted.

In fact, this process can be abstracted as follows: Now there is a binary data, 0001***, we don't care about the low value, we move it to the right and perform OR operation.

First shift 0001*** 1 to the right by 1 bit to get 00001***, and then OR with itself: get 00011***.

Then shift 00011** 2 bits to the right to obtain 000011 *, and then OR with itself: obtain 0001111*.

Then shift 0001111* 4 bits to the right to obtain 0000001, and then OR with itself: obtain 0001111.

There is no need to calculate later. Here we can actually find a rule: the purpose of the right shift and OR operation is to make the low bits of a certain number become 1, and then subtract the result after the right shift of the result by one bit, which is equivalent to clearing the low bits of the original number. We get the results we want.

At this point, can only sigh JDK author for the use of bit operations has reached a superb realm.

What is the role of Integer.highestOneBit(int i) method to share here, I hope the above content can be of some help to everyone, you can learn more knowledge. If you think the article is good, you can share it so that more people can see it.

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.