¿Cuál es la forma más eficiente de encontrar el índice del bit unset izquierdo/derecho en Java?

Question

Supongamos que tenemos int x = 371, que está en formato binario 101110011. Quiero encontrar el índice del bit no ajustado más a la izquierda (en este caso 7) y el índice del bit no ajustado a la derecha (en este caso 2). ¿Cuál es la forma más eficiente de hacerlo?

Esto es lo que tengo:

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)); 
    } 

} 

Si no estoy equivocado, mi implementación actual requiere tiempo lineal. ¿Podemos hacerlo mejor?

Answer 1

Existen métodos disponibles en la clase Integer.

Integer.numberOfTrailingZeros(Integer.lowestOneBit(~yourValue)) lo haríamos por el más bajo de un bit no ajustado, para el más alto es un poco más complicado ya que primero tenemos que determinar el bit más alto establecido.

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

Debería hacerlo para el bit más alto no ajustado.

Y esto puede ser más rápido que el tiempo lineal ya que los procesadores a menudo tienen instrucciones de la máquina para determinar rápidamente el bit cero inicial/final (pero no estoy seguro si el vm los utiliza EDITAR: Ahora estoy seguro ;-).

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

Answer 2

Debajo de ella está el código fuente de Integer.numberOfLeadingZeros. Como está apuntado, está tomado de HD (Hacker's Delight por Henry S. Warren, Jr)

La idea principal es usar la búsqueda binaria en lugar de iterar los bits, uno por uno. Por favor, revise el libro si le interesan los trucos. Es una maravillosa obra de arte.

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; 
}