What is the most efficient way of finding the index of the left/right-most unset bit in Java?

Question

Let's assume that we have int x = 371, that is in binary format 101110011. I want to find the index of the left-most unset bit (in this case 7), and the index of the right-most unset bit (in this case 2). What is the most efficient way of doing it?

Here's what I have:

public class BitOperatons {

    public static int setBit(int x, int i) {
        int y = x | (1 << i);
        return y;
    }

    public static boolean isBitSet(int x, int i) {
        int y = setBit(0, i);
        return y == (x & y);
    }    

    public static int findLeftMostSetBit(int x) {
        for (int i = 31; i >= 0; i--) {
            if (isBitSet(x, i))
                return i;
        }
        return -1;
    }

    public static int findRightMostUnsetBit(int x) {
        for (int i = 0; i <= 31; i++) {
            if (! isBitSet(x, i))
                return i;
        }
        return -1;
    }

    public static int findLeftMostUnsetBit(int x) {
        int k = findLeftMostSetBit(x);
        for (int i = k; i >= 0; i--) {
            if (! isBitSet(x, i))
                return i;
        }
        return -1;
    }

    public static1+ void main(String[] args) {
        int x = 
            (1 << 0) |
            (1 << 1) |
            (1 << 4) |
            (1 << 5) |
            (1 << 6) |
            (1 << 8);
        System.out.println(findLeftMostUnsetBit(x));
        System.out.println(findRightMostUnsetBit(x));
    }

}

If I'm not wrong, my current implementation takes linear time. Can we do better?

Answer 1

Below it's the source code of Integer.numberOfLeadingZeros. As pointed it's taken from HD (Hacker's Delight by Henry S. Warren, Jr)

The main idea is using binary search instead of iterating the bits, one by one. Please, check the book if you are interested in bit twiddling. It's a wonderful piece of art.

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

There are methods available in the Integer class.

Integer.numberOfTrailingZeros(Integer.lowestOneBit(~yourValue)) would do it for the lowest one unset bit, for the highest it is a bit trickier as we first have to determine the highest set bit.

int leadingZeroBits = Integer.numberOfLeadingZeros(Integer.highestOneBit(yourValue));
result = Integer.
       numberOfTrailingZeros(Integer.highestOneBit((~yourValue)<<leadingZeroBits)
      -leadingZeroBits;`

Should do it for the highest unset bit.

And this may be faster than linear time as processors often have machine instructions to determine fast the leading/trailing zero bit (but not sure if the vm utilize them EDIT: I am now sure ;-).

EDIT: It seems they added the use of asm intrinsics for leading/trailing zeros in 1.6.0_18, ID 6823354