Finding 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 (index of highest order 1).

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

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

but this is way slower than what I want to do. I know modern CPUs have instructions that do this on chip, so I want to know how I can make a call to that rather than having an explicit loop.

EDIT: Bonus points if you can just return the indices of all of the ones in the primitive.

Thanks.

Answer 1

Integer.numberOfLeadingZeros(i) + 1

That method uses a nice 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 page "Bit Twiddling Hacks" contains lots of bit hacks. One is how to find the index of the highest order bit.