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.highestOneBit(i); this would return 5 if you pass 00110101b into it.

if you've accidentally flipped the order of bits in your example, and you want a method that returns 2, then it is Integer.lowestOneBit(i);

Answer 2

I don't know about hitting a CPU instruction, but I do know that this will be a lot faster if you unroll the loop and use explicit bit masking.

Also, a char is not 8 bits... I think you might have meant a byte.

Answer 3

The page "Bit Twiddling Hacks" contains lots of bit hacks. One is how to find the index of the highest order bit.

Answer 4

As far as I can tell, the Pentium and friends don't have an instruction ready-made for this. So the thing to do is to use a decent algorithm.

The key to getting your answer quickly is to use a binary search. You're looking at a long with 64 bits? 6 comparisons will give you your highest bit, every time.

The code works out to a big ugly tree of 64 if statements, but only a fraction of those will ever be executed, so runtime is good.

If you need sample code, I can do that. But I'd rather not.

Answer 5

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 6

I have no idea if this is faster. But it has no 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 7

Java being compiled into platform-independent bytecode, you cannot expect support for CPU instructions. Otherwise your code or Integer.highestOneBit() should be as fast as it gets.

Answer 8

Is it something like this you're after?

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