Encontrar el orden más alto 1 en una primitiva Java

Question

Necesito encontrar la orden más alta 1 en algunos largos, ints y cortos en Java. Por ejemplo, si tuviera un carácter que se parecía al 00110101, necesito un método que arroje 2 (índice del orden más alto 1).

Ahora, sé que usted puede hacer esto utilizando un bucle como:

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

pero esto es mucho más lento que lo que yo quiero hacer. Sé que las CPU modernas tienen instrucciones que hacen esto en un chip, así que quiero saber cómo puedo hacer una llamada a eso en lugar de tener un bucle explícito.

EDITAR: puntos de bonificación si puede simplemente devolver los índices de todos los que están en la primitiva.

Gracias.

Answer 1

Integer.numberOfLeadingZeros(i) + 1

Ese método utiliza un acercamiento agradable divide y vencerás, copiado aquí para su revisión:

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

No sé si tocar una instrucción de CPU, pero sé que esto será mucho más rápido si desenrolla el bucle y usa enmascaramiento de bits explícito.

Además, un char no es de 8 bits ... Creo que podría haber significado un byte.

Answer 3

La página "Bit Twiddling Hacks" contiene muchos bits de bits. Una es cómo encontrar el index of the highest order bit.

Answer 4

Por lo que puedo decir, el Pentium y sus amigos no tienen una instrucción preparada para esto. Entonces, lo que hay que hacer es usar un algoritmo decente.

La clave para obtener una respuesta rápida es utilizar una búsqueda binaria. ¿Está buscando un long con 64 bits? 6 comparaciones le darán su bit más alto, todas las veces.

El código se resuelve en un gran árbol feo de 64 sentencias if, pero solo se ejecutará una pequeña parte de ellas, por lo que el tiempo de ejecución es bueno.

Si necesita un código de muestra, puedo hacerlo. Pero prefiero no.

Answer 5

tengo ni idea de si esto es más rápido. Pero no tiene bucle.

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 6

Java se compila en bytecode de plataforma independiente, no se puede esperar el soporte para las instrucciones de la CPU. De lo contrario, su código o Integer.highestOneBit() debería ser lo más rápido posible.

Answer 7

¿Es esto algo que estás buscando?

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