Finding the highest order 1 in a Java primitive

Question

I need to find the highest order 1 in some longs, ints and shorts in Java. For example, if I had a char that looked like 00110101 , I need a method that will return 2 (the highest order index is 1).

Now I know that you can do this using a for loop, for example:

 for(int i=0; i<8; i++) if((x & 1<<i) != 0) return i; return -1; 

but it is slower than I want. I know that modern processors have instructions that do this on a chip, so I want to know how I can make a call, and not have an explicit loop.

EDIT: bonus points if you can just return the indices of all of them in the primitive.

Thanks.

Answer 1

Integer.numberOfLeadingZeros(i) + 1

This method uses the good divide and conquer approach copied here for your review:

 public static int numberOfLeadingZeros(int i) { // HD, Figure 5-6 if (i == 0) return 32; int n = 1; if (i >>> 16 == 0) { n += 16; i <<= 16; } if (i >>> 24 == 0) { n += 8; i <<= 8; } if (i >>> 28 == 0) { n += 4; i <<= 4; } if (i >>> 30 == 0) { n += 2; i <<= 2; } n -= i >>> 31; return n; } 

Answer 2

The Tweedling Hacks Bit page contains many bit hacks. One of them is the search for the index of the highest order bit .

Answer 3

I do not know if it is faster. But he does not have a loop.

 if(i==0) return -1; highest=0; if (i & 0xffff0000) { highest+=16; i>>=16; } if (i & 0xff00) { highest+=8; i>>=8; } if (i & 0xf0) { highest+=4; i>>=4; } if (i & 0xC) { highest+=2; i>>=2; } if (i & 0x2) { highest+=1; } return highest; 

Answer 4

I do not know how to get into the CPU instruction, but I know that it will be much faster if you expand the loop and use explicit bit masking.

Also, char is not 8 bits ... I think you could mean bytes.

Answer 5

As far as I can tell, Pentium and friends don't have instructions ready for this. Therefore, you need to make the right algorithm.

The key to quickly completing your answer is using binary search. Are you looking at long with 64 bits? 6 comparisons will give you the highest bit every time.

The code works with a large ugly tree of 64 if statements, but only a part of them will be executed, so the execution time is good.

If you need some sample code, I can do it. But I would rather not do that.

Answer 6

Java compiles into platform-independent bytecode; you cannot expect support for CPU instructions. Otherwise, your code or Integer.highestOneBit () should be as fast as possible.

Answer 7

Is it something like this you after?

 System.out.println("00110101".indexOf("1"));