What is the most efficient way to find the index in the left / right block without changes in Java?

Question

Suppose we have int x = 371 , that is, in binary format 101110011 . I want to find the index of the most unrestored bit (in this case 7) and the index of the messiest bit (in this case 2). What is the most efficient way to do this?

Here is 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 mistaken, my current implementation takes linear time. Can we do better?

Answer 1

There are methods available in the Integer class.

Integer.numberOfTrailingZeros(Integer.lowestOneBit(~yourValue)) would do this for the low order, but for the highest level it is a bit more complicated, since we must first determine the most significant bit.

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

Must do this for the highest non-conforming bit.

And this can be faster than linear time, as processors often have machine instructions for quickly determining the leading / trailing zero bits (but are not sure if vm uses their EDIT: now I'm sure ;-).

EDIT : They seem to have added using asm intrinsics for leading / trailing zeros in 1.6.0_18, ID 6823354

Answer 2

Below is the source code of Integer.numberOfLeadingZeros. As stated, this is taken from HD (Hacker Delight by Henry S. Warren, Jr)

The basic idea is to use binary search instead of repeating bits, one by one. Please check out the book if you are interested in bit screening. This is a wonderful work 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; }